import libtommath 1.0

1 files changed, 28 insertions, 16 deletions

diff --git a/libtommath/bn_mp_jacobi.c b/libtommath/bn_mp_jacobi.c
index 07a9d65..3c114e3 100644
--- a/libtommath/bn_mp_jacobi.c
+++ b/libtommath/bn_mp_jacobi.c
@@ -1,4 +1,4 @@
-#include <tommath.h>
+#include <tommath_private.h>
 #ifdef BN_MP_JACOBI_C
 /* LibTomMath, multiple-precision integer library -- Tom St Denis
  *
@@ -12,27 +12,39 @@
  * The library is free for all purposes without any express
  * guarantee it works.
  *
- * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
+ * Tom St Denis, tstdenis82@gmail.com, http://libtom.org
  */
 
 /* computes the jacobi c = (a | n) (or Legendre if n is prime)
  * HAC pp. 73 Algorithm 2.149
+ * HAC is wrong here, as the special case of (0 | 1) is not
+ * handled correctly.
  */
-int mp_jacobi (mp_int * a, mp_int * p, int *c)
+int mp_jacobi (mp_int * a, mp_int * n, int *c)
 {
   mp_int  a1, p1;
   int     k, s, r, res;
   mp_digit residue;
 
-  /* if p <= 0 return MP_VAL */
-  if (mp_cmp_d(p, 0) != MP_GT) {
+  /* if a < 0 return MP_VAL */
+  if (mp_isneg(a) == MP_YES) {
      return MP_VAL;
   }
 
-  /* step 1.  if a == 0, return 0 */
-  if (mp_iszero (a) == 1) {
-    *c = 0;
-    return MP_OKAY;
+  /* if n <= 0 return MP_VAL */
+  if (mp_cmp_d(n, 0) != MP_GT) {
+     return MP_VAL;
+  }
+
+  /* step 1. handle case of a == 0 */
+  if (mp_iszero (a) == MP_YES) {
+     /* special case of a == 0 and n == 1 */
+     if (mp_cmp_d (n, 1) == MP_EQ) {
+       *c = 1;
+     } else {
+       *c = 0;
+     }
+     return MP_OKAY;
   }
 
   /* step 2.  if a == 1, return 1 */
@@ -64,17 +76,17 @@ int mp_jacobi (mp_int * a, mp_int * p, int *c)
     s = 1;
   } else {
     /* else set s=1 if p = 1/7 (mod 8) or s=-1 if p = 3/5 (mod 8) */
-    residue = p->dp[0] & 7;
+    residue = n->dp[0] & 7;
 
-    if (residue == 1 || residue == 7) {
+    if ((residue == 1) || (residue == 7)) {
       s = 1;
-    } else if (residue == 3 || residue == 5) {
+    } else if ((residue == 3) || (residue == 5)) {
       s = -1;
     }
   }
 
   /* step 5.  if p == 3 (mod 4) *and* a1 == 3 (mod 4) then s = -s */
-  if ( ((p->dp[0] & 3) == 3) && ((a1.dp[0] & 3) == 3)) {
+  if ( ((n->dp[0] & 3) == 3) && ((a1.dp[0] & 3) == 3)) {
     s = -s;
   }
 
@@ -83,7 +95,7 @@ int mp_jacobi (mp_int * a, mp_int * p, int *c)
     *c = s;
   } else {
     /* n1 = n mod a1 */
-    if ((res = mp_mod (p, &a1, &p1)) != MP_OKAY) {
+    if ((res = mp_mod (n, &a1, &p1)) != MP_OKAY) {
       goto LBL_P1;
     }
     if ((res = mp_jacobi (&p1, &a1, &r)) != MP_OKAY) {
@@ -101,5 +113,5 @@ LBL_A1:mp_clear (&a1);
 #endif
 
 /* $Source$ */
-/* $Revision: 0.41 $ */
-/* $Date: 2007-04-18 09:58:18 +0000 $ */
+/* $Revision$ */
+/* $Date$ */