diff options
author | William Joye <wjoye@cfa.harvard.edu> | 2017-10-17 19:50:58 (GMT) |
---|---|---|
committer | William Joye <wjoye@cfa.harvard.edu> | 2017-10-17 19:50:58 (GMT) |
commit | 9b7a6c3507ea3383c60aaecb29f873c9b590ccca (patch) | |
tree | 82ce31ebd8f46803d969034f5aa3db8d7974493c /tcl8.6/libtommath/bn_mp_jacobi.c | |
parent | 87fca7325b97005eb44dcf3e198277640af66115 (diff) | |
download | blt-9b7a6c3507ea3383c60aaecb29f873c9b590ccca.zip blt-9b7a6c3507ea3383c60aaecb29f873c9b590ccca.tar.gz blt-9b7a6c3507ea3383c60aaecb29f873c9b590ccca.tar.bz2 |
rm tcl/tk 8.6.7
Diffstat (limited to 'tcl8.6/libtommath/bn_mp_jacobi.c')
-rw-r--r-- | tcl8.6/libtommath/bn_mp_jacobi.c | 101 |
1 files changed, 0 insertions, 101 deletions
diff --git a/tcl8.6/libtommath/bn_mp_jacobi.c b/tcl8.6/libtommath/bn_mp_jacobi.c deleted file mode 100644 index 1644698..0000000 --- a/tcl8.6/libtommath/bn_mp_jacobi.c +++ /dev/null @@ -1,101 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_JACOBI_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com - */ - -/* computes the jacobi c = (a | n) (or Legendre if n is prime) - * HAC pp. 73 Algorithm 2.149 - */ -int mp_jacobi (mp_int * a, mp_int * p, 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) { - return MP_VAL; - } - - /* step 1. if a == 0, return 0 */ - if (mp_iszero (a) == 1) { - *c = 0; - return MP_OKAY; - } - - /* step 2. if a == 1, return 1 */ - if (mp_cmp_d (a, 1) == MP_EQ) { - *c = 1; - return MP_OKAY; - } - - /* default */ - s = 0; - - /* step 3. write a = a1 * 2**k */ - if ((res = mp_init_copy (&a1, a)) != MP_OKAY) { - return res; - } - - if ((res = mp_init (&p1)) != MP_OKAY) { - goto LBL_A1; - } - - /* divide out larger power of two */ - k = mp_cnt_lsb(&a1); - if ((res = mp_div_2d(&a1, k, &a1, NULL)) != MP_OKAY) { - goto LBL_P1; - } - - /* step 4. if e is even set s=1 */ - if ((k & 1) == 0) { - 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; - - if (residue == 1 || residue == 7) { - s = 1; - } 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)) { - s = -s; - } - - /* if a1 == 1 we're done */ - if (mp_cmp_d (&a1, 1) == MP_EQ) { - *c = s; - } else { - /* n1 = n mod a1 */ - if ((res = mp_mod (p, &a1, &p1)) != MP_OKAY) { - goto LBL_P1; - } - if ((res = mp_jacobi (&p1, &a1, &r)) != MP_OKAY) { - goto LBL_P1; - } - *c = s * r; - } - - /* done */ - res = MP_OKAY; -LBL_P1:mp_clear (&p1); -LBL_A1:mp_clear (&a1); - return res; -} -#endif |