annotate bn_mp_jacobi.c @ 139:cc04b085e7dd libtommath

Pristine compilation works.
author Matt Johnston <matt@ucc.asn.au>
date Fri, 17 Dec 2004 06:27:22 +0000
parents 22d5cf7d4b1a
children d29b64170cf0
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 * LibTomMath is a library that provides multiple-precision
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 * integer arithmetic as well as number theoretic functionality.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 * The library was designed directly after the MPI library by
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 * Michael Fromberger but has been written from scratch with
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 * additional optimizations in place.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 * The library is free for all purposes without any express
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 * guarantee it works.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 #include <tommath.h>
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 /* computes the jacobi c = (a | n) (or Legendre if n is prime)
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 * HAC pp. 73 Algorithm 2.149
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 int mp_jacobi (mp_int * a, mp_int * p, int *c)
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 mp_int a1, p1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 int k, s, r, res;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24 mp_digit residue;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26 /* if p <= 0 return MP_VAL */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 if (mp_cmp_d(p, 0) != MP_GT) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28 return MP_VAL;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31 /* step 1. if a == 0, return 0 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 if (mp_iszero (a) == 1) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 *c = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 return MP_OKAY;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37 /* step 2. if a == 1, return 1 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38 if (mp_cmp_d (a, 1) == MP_EQ) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 *c = 1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40 return MP_OKAY;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43 /* default */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44 s = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46 /* step 3. write a = a1 * 2**k */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47 if ((res = mp_init_copy (&a1, a)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 return res;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 if ((res = mp_init (&p1)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 goto __A1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55 /* divide out larger power of two */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 k = mp_cnt_lsb(&a1);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57 if ((res = mp_div_2d(&a1, k, &a1, NULL)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58 goto __P1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
60
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61 /* step 4. if e is even set s=1 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 if ((k & 1) == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63 s = 1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64 } else {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
65 /* else set s=1 if p = 1/7 (mod 8) or s=-1 if p = 3/5 (mod 8) */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
66 residue = p->dp[0] & 7;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
67
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
68 if (residue == 1 || residue == 7) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
69 s = 1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
70 } else if (residue == 3 || residue == 5) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
71 s = -1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
72 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
74
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
75 /* step 5. if p == 3 (mod 4) *and* a1 == 3 (mod 4) then s = -s */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76 if ( ((p->dp[0] & 3) == 3) && ((a1.dp[0] & 3) == 3)) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
77 s = -s;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80 /* if a1 == 1 we're done */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
81 if (mp_cmp_d (&a1, 1) == MP_EQ) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82 *c = s;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
83 } else {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
84 /* n1 = n mod a1 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
85 if ((res = mp_mod (p, &a1, &p1)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
86 goto __P1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
87 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
88 if ((res = mp_jacobi (&p1, &a1, &r)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
89 goto __P1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
90 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
91 *c = s * r;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
92 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
93
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
94 /* done */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
95 res = MP_OKAY;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
96 __P1:mp_clear (&p1);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
97 __A1:mp_clear (&a1);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
98 return res;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
99 }