Mercurial > dropbear

comparison libtommath/bn_mp_karatsuba_mul.c @ 435:337c45621e81

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge of 'a9b0496634cdd25647b65e585cc3240f3fa699ee' and 'c22be8b8f570b48e9662dac32c7b3e7148a42206'
author Matt Johnston <matt@ucc.asn.au>
date Thu, 22 Feb 2007 14:53:49 +0000
parents 5ff8218bcee9
children 60fc6476e044
comparison
equal deleted inserted replaced
434:0aaaf68e97dc 435:337c45621e81
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * The library is free for all purposes without any express
13 * guarantee it works. 13 * guarantee it works.
14 * 14 *
15 * Tom St Denis, [email protected], http://math.libtomcrypt.org 15 * Tom St Denis, [email protected], http://math.libtomcrypt.com
16 */ 16 */
17 17
18 /* c = |a| * |b| using Karatsuba Multiplication using 18 /* c = |a| * |b| using Karatsuba Multiplication using
19 * three half size multiplications 19 * three half size multiplications
20 * 20 *
24 * 24 *
25 * a = a1 * B**n + a0 25 * a = a1 * B**n + a0
26 * b = b1 * B**n + b0 26 * b = b1 * B**n + b0
27 * 27 *
28 * Then, a * b => 28 * Then, a * b =>
29 a1b1 * B**2n + ((a1 - a0)(b1 - b0) + a0b0 + a1b1) * B + a0b0 29 a1b1 * B**2n + ((a1 + a0)(b1 + b0) - (a0b0 + a1b1)) * B + a0b0
30 * 30 *
31 * Note that a1b1 and a0b0 are used twice and only need to be 31 * Note that a1b1 and a0b0 are used twice and only need to be
32 * computed once. So in total three half size (half # of 32 * computed once. So in total three half size (half # of
33 * digit) multiplications are performed, a0b0, a1b1 and 33 * digit) multiplications are performed, a0b0, a1b1 and
34 * (a1-b1)(a0-b0) 34 * (a1+b1)(a0+b0)
35 * 35 *
36 * Note that a multiplication of half the digits requires 36 * Note that a multiplication of half the digits requires
37 * 1/4th the number of single precision multiplications so in 37 * 1/4th the number of single precision multiplications so in
38 * total after one call 25% of the single precision multiplications 38 * total after one call 25% of the single precision multiplications
39 * are saved. Note also that the call to mp_mul can end up back 39 * are saved. Note also that the call to mp_mul can end up back
120 if (mp_mul (&x0, &y0, &x0y0) != MP_OKAY) 120 if (mp_mul (&x0, &y0, &x0y0) != MP_OKAY)
121 goto X1Y1; /* x0y0 = x0*y0 */ 121 goto X1Y1; /* x0y0 = x0*y0 */
122 if (mp_mul (&x1, &y1, &x1y1) != MP_OKAY) 122 if (mp_mul (&x1, &y1, &x1y1) != MP_OKAY)
123 goto X1Y1; /* x1y1 = x1*y1 */ 123 goto X1Y1; /* x1y1 = x1*y1 */
124 124
125 /* now calc x1-x0 and y1-y0 */ 125 /* now calc x1+x0 and y1+y0 */
126 if (mp_sub (&x1, &x0, &t1) != MP_OKAY) 126 if (s_mp_add (&x1, &x0, &t1) != MP_OKAY)
127 goto X1Y1; /* t1 = x1 - x0 */ 127 goto X1Y1; /* t1 = x1 - x0 */
128 if (mp_sub (&y1, &y0, &x0) != MP_OKAY) 128 if (s_mp_add (&y1, &y0, &x0) != MP_OKAY)
129 goto X1Y1; /* t2 = y1 - y0 */ 129 goto X1Y1; /* t2 = y1 - y0 */
130 if (mp_mul (&t1, &x0, &t1) != MP_OKAY) 130 if (mp_mul (&t1, &x0, &t1) != MP_OKAY)
131 goto X1Y1; /* t1 = (x1 - x0) * (y1 - y0) */ 131 goto X1Y1; /* t1 = (x1 + x0) * (y1 + y0) */
132 132
133 /* add x0y0 */ 133 /* add x0y0 */
134 if (mp_add (&x0y0, &x1y1, &x0) != MP_OKAY) 134 if (mp_add (&x0y0, &x1y1, &x0) != MP_OKAY)
135 goto X1Y1; /* t2 = x0y0 + x1y1 */ 135 goto X1Y1; /* t2 = x0y0 + x1y1 */
136 if (mp_sub (&x0, &t1, &t1) != MP_OKAY) 136 if (s_mp_sub (&t1, &x0, &t1) != MP_OKAY)
137 goto X1Y1; /* t1 = x0y0 + x1y1 - (x1-x0)*(y1-y0) */ 137 goto X1Y1; /* t1 = (x1+x0)*(y1+y0) - (x1y1 + x0y0) */
138 138
139 /* shift by B */ 139 /* shift by B */
140 if (mp_lshd (&t1, B) != MP_OKAY) 140 if (mp_lshd (&t1, B) != MP_OKAY)
141 goto X1Y1; /* t1 = (x0y0 + x1y1 - (x1-x0)*(y1-y0))<<B */ 141 goto X1Y1; /* t1 = (x0y0 + x1y1 - (x1-x0)*(y1-y0))<<B */
142 if (mp_lshd (&x1y1, B * 2) != MP_OKAY) 142 if (mp_lshd (&x1y1, B * 2) != MP_OKAY)
159 X0:mp_clear (&x0); 159 X0:mp_clear (&x0);
160 ERR: 160 ERR:
161 return err; 161 return err;
162 } 162 }
163 #endif 163 #endif
164
165 /* $Source: /cvs/libtom/libtommath/bn_mp_karatsuba_mul.c,v $ */
166 /* $Revision: 1.5 $ */
167 /* $Date: 2006/03/31 14:18:44 $ */