1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <tommath.h> 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_MP_KARATSUBA_MUL_C 3f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* LibTomMath, multiple-precision integer library -- Tom St Denis 4f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 5f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LibTomMath is a library that provides multiple-precision 6f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * integer arithmetic as well as number theoretic functionality. 7f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 8f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library was designed directly after the MPI library by 9f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Michael Fromberger but has been written from scratch with 10f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * additional optimizations in place. 11f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 12f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library is free for all purposes without any express 13f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * guarantee it works. 14f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 15f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com 16f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 17f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 18f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* c = |a| * |b| using Karatsuba Multiplication using 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * three half size multiplications 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Let B represent the radix [e.g. 2**DIGIT_BIT] and 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * let n represent half of the number of digits in 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * the min(a,b) 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * a = a1 * B**n + a0 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * b = b1 * B**n + b0 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Then, a * b => 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project a1b1 * B**2n + ((a1 + a0)(b1 + b0) - (a0b0 + a1b1)) * B + a0b0 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Note that a1b1 and a0b0 are used twice and only need to be 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * computed once. So in total three half size (half # of 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * digit) multiplications are performed, a0b0, a1b1 and 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * (a1+b1)(a0+b0) 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Note that a multiplication of half the digits requires 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 1/4th the number of single precision multiplications so in 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * total after one call 25% of the single precision multiplications 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * are saved. Note also that the call to mp_mul can end up back 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * in this function if the a0, a1, b0, or b1 are above the threshold. 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * This is known as divide-and-conquer and leads to the famous 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * O(N**lg(3)) or O(N**1.584) work which is asymptopically lower than 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * the standard O(N**2) that the baseline/comba methods use. 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Generally though the overhead of this method doesn't pay off 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * until a certain size (N ~ 80) is reached. 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_karatsuba_mul (mp_int * a, mp_int * b, mp_int * c) 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int x0, x1, y0, y1, t1, x0y0, x1y1; 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int B, err; 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* default the return code to an error */ 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = MP_MEM; 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* min # of digits */ 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project B = MIN (a->used, b->used); 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now divide in two */ 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project B = B >> 1; 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* init copy all the temps */ 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_init_size (&x0, B) != MP_OKAY) 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto ERR; 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_init_size (&x1, a->used - B) != MP_OKAY) 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X0; 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_init_size (&y0, B) != MP_OKAY) 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1; 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_init_size (&y1, b->used - B) != MP_OKAY) 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto Y0; 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* init temps */ 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_init_size (&t1, B * 2) != MP_OKAY) 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto Y1; 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_init_size (&x0y0, B * 2) != MP_OKAY) 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto T1; 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_init_size (&x1y1, B * 2) != MP_OKAY) 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X0Y0; 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now shift the digits */ 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x0.used = y0.used = B; 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x1.used = a->used - B; 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project y1.used = b->used - B; 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project { 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project register int x; 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project register mp_digit *tmpa, *tmpb, *tmpx, *tmpy; 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* we copy the digits directly instead of using higher level functions 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * since we also need to shift the digits 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmpa = a->dp; 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmpb = b->dp; 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmpx = x0.dp; 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmpy = y0.dp; 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 0; x < B; x++) { 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project *tmpx++ = *tmpa++; 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project *tmpy++ = *tmpb++; 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmpx = x1.dp; 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = B; x < a->used; x++) { 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project *tmpx++ = *tmpa++; 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project tmpy = y1.dp; 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = B; x < b->used; x++) { 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project *tmpy++ = *tmpb++; 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* only need to clamp the lower words since by definition the 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * upper words x1/y1 must have a known number of digits 114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 115f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clamp (&x0); 116f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clamp (&y0); 117f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 118f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now calc the products x0y0 and x1y1 */ 119f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* after this x0 is no longer required, free temp [x0==t2]! */ 120f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_mul (&x0, &y0, &x0y0) != MP_OKAY) 121f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* x0y0 = x0*y0 */ 122f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_mul (&x1, &y1, &x1y1) != MP_OKAY) 123f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* x1y1 = x1*y1 */ 124f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 125f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now calc x1+x0 and y1+y0 */ 126f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (s_mp_add (&x1, &x0, &t1) != MP_OKAY) 127f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* t1 = x1 - x0 */ 128f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (s_mp_add (&y1, &y0, &x0) != MP_OKAY) 129f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* t2 = y1 - y0 */ 130f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_mul (&t1, &x0, &t1) != MP_OKAY) 131f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* t1 = (x1 + x0) * (y1 + y0) */ 132f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 133f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* add x0y0 */ 134f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_add (&x0y0, &x1y1, &x0) != MP_OKAY) 135f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* t2 = x0y0 + x1y1 */ 136f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (s_mp_sub (&t1, &x0, &t1) != MP_OKAY) 137f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* t1 = (x1+x0)*(y1+y0) - (x1y1 + x0y0) */ 138f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 139f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* shift by B */ 140f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_lshd (&t1, B) != MP_OKAY) 141f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* t1 = (x0y0 + x1y1 - (x1-x0)*(y1-y0))<<B */ 142f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_lshd (&x1y1, B * 2) != MP_OKAY) 143f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* x1y1 = x1y1 << 2*B */ 144f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 145f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_add (&x0y0, &t1, &t1) != MP_OKAY) 146f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* t1 = x0y0 + t1 */ 147f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_add (&t1, &x1y1, c) != MP_OKAY) 148f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto X1Y1; /* t1 = x0y0 + t1 + x1y1 */ 149f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 150f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* Algorithm succeeded set the return code to MP_OKAY */ 151f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = MP_OKAY; 152f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 153f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectX1Y1:mp_clear (&x1y1); 154f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectX0Y0:mp_clear (&x0y0); 155f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectT1:mp_clear (&t1); 156f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectY1:mp_clear (&y1); 157f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectY0:mp_clear (&y0); 158f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectX1:mp_clear (&x1); 159f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectX0:mp_clear (&x0); 160f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectERR: 161f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 162f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 163f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 164f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 165f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/bn_mp_karatsuba_mul.c,v $ */ 166f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.5 $ */ 167f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:44 $ */ 168