summaryrefslogtreecommitdiffstats
path: root/libtommath/bn_mp_jacobi.c
diff options
context:
space:
mode:
Diffstat (limited to 'libtommath/bn_mp_jacobi.c')
-rw-r--r--libtommath/bn_mp_jacobi.c44
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$ */