summaryrefslogtreecommitdiffstats
path: root/libtommath/bn_mp_karatsuba_mul.c
diff options
context:
space:
mode:
authorKevin B Kenny <kennykb@acm.org>2005-09-26 16:31:55 (GMT)
committerKevin B Kenny <kennykb@acm.org>2005-09-26 16:31:55 (GMT)
commit6285bbd18905331a696ae8d31942482672261433 (patch)
tree4ec07aa4ad5cdf752c1df248b9a54a4dd6cfb167 /libtommath/bn_mp_karatsuba_mul.c
parent12cea33504df70df1758c94a2302e367e3855e43 (diff)
downloadtcl-6285bbd18905331a696ae8d31942482672261433.zip
tcl-6285bbd18905331a696ae8d31942482672261433.tar.gz
tcl-6285bbd18905331a696ae8d31942482672261433.tar.bz2
Import of libtommath 0.36
Diffstat (limited to 'libtommath/bn_mp_karatsuba_mul.c')
-rw-r--r--libtommath/bn_mp_karatsuba_mul.c20
1 files changed, 12 insertions, 8 deletions
diff --git a/libtommath/bn_mp_karatsuba_mul.c b/libtommath/bn_mp_karatsuba_mul.c
index daa78c7..a1ff713 100644
--- a/libtommath/bn_mp_karatsuba_mul.c
+++ b/libtommath/bn_mp_karatsuba_mul.c
@@ -26,12 +26,12 @@
* b = b1 * B**n + b0
*
* Then, a * b =>
- a1b1 * B**2n + ((a1 - a0)(b1 - b0) + a0b0 + a1b1) * B + a0b0
+ a1b1 * B**2n + ((a1 + a0)(b1 + b0) - (a0b0 + a1b1)) * B + a0b0
*
* Note that a1b1 and a0b0 are used twice and only need to be
* computed once. So in total three half size (half # of
* digit) multiplications are performed, a0b0, a1b1 and
- * (a1-b1)(a0-b0)
+ * (a1+b1)(a0+b0)
*
* Note that a multiplication of half the digits requires
* 1/4th the number of single precision multiplications so in
@@ -122,19 +122,19 @@ int mp_karatsuba_mul (mp_int * a, mp_int * b, mp_int * c)
if (mp_mul (&x1, &y1, &x1y1) != MP_OKAY)
goto X1Y1; /* x1y1 = x1*y1 */
- /* now calc x1-x0 and y1-y0 */
- if (mp_sub (&x1, &x0, &t1) != MP_OKAY)
+ /* now calc x1+x0 and y1+y0 */
+ if (s_mp_add (&x1, &x0, &t1) != MP_OKAY)
goto X1Y1; /* t1 = x1 - x0 */
- if (mp_sub (&y1, &y0, &x0) != MP_OKAY)
+ if (s_mp_add (&y1, &y0, &x0) != MP_OKAY)
goto X1Y1; /* t2 = y1 - y0 */
if (mp_mul (&t1, &x0, &t1) != MP_OKAY)
- goto X1Y1; /* t1 = (x1 - x0) * (y1 - y0) */
+ goto X1Y1; /* t1 = (x1 + x0) * (y1 + y0) */
/* add x0y0 */
if (mp_add (&x0y0, &x1y1, &x0) != MP_OKAY)
goto X1Y1; /* t2 = x0y0 + x1y1 */
- if (mp_sub (&x0, &t1, &t1) != MP_OKAY)
- goto X1Y1; /* t1 = x0y0 + x1y1 - (x1-x0)*(y1-y0) */
+ if (s_mp_sub (&t1, &x0, &t1) != MP_OKAY)
+ goto X1Y1; /* t1 = (x1+x0)*(y1+y0) - (x1y1 + x0y0) */
/* shift by B */
if (mp_lshd (&t1, B) != MP_OKAY)
@@ -161,3 +161,7 @@ ERR:
return err;
}
#endif
+
+/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_karatsuba_mul.c,v $ */
+/* $Revision: 1.1.1.2 $ */
+/* $Date: 2005/09/26 16:31:56 $ */