3 * $Id: mp-jacobi.c,v 1.4 2000/12/06 20:31:33 mdw Exp $
5 * Compute Jacobi symbol
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Revision history --------------------------------------------------*
32 * $Log: mp-jacobi.c,v $
33 * Revision 1.4 2000/12/06 20:31:33 mdw
34 * Add assertion to prevent crapness.
36 * Revision 1.3 2000/07/20 17:14:34 mdw
37 * Simplify by using @mp_odd@.
39 * Revision 1.2 1999/12/10 23:19:02 mdw
40 * Improve error-checking.
42 * Revision 1.1 1999/11/22 20:50:37 mdw
43 * Add support for computing Jacobi symbols.
47 /*----- Header files ------------------------------------------------------*/
51 /*----- Main code ---------------------------------------------------------*/
53 /* --- @mp_jacobi@ --- *
55 * Arguments: @mp *a@ = an integer less than @n@
56 * @mp *n@ = an odd integer
58 * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
60 * Use: Computes the Jacobi symbol. If @n@ is prime, this is the
61 * Legendre symbol and is equal to 1 if and only if @a@ is a
62 * quadratic residue mod @n@. The result is zero if and only if
63 * @a@ and @n@ have a common factor greater than one.
66 int mp_jacobi(mp
*a
, mp
*n
)
70 assert(((void)"n must be odd in mp_jacobi", MP_LEN(n
) && (n
->v
[0] & 1)));
72 /* --- Take copies of the arguments --- */
77 /* --- Main recursive mess, flattened out into something nice --- */
83 /* --- Some simple special cases --- */
91 /* --- Main case with powers of two --- */
95 if ((e
& 1) && (nn
== 3 || nn
== 5))
97 if (MP_LEN(a
) == 1 && a
->v
[0] == 1)
99 if ((nn
& 3) == 3 && (a
->v
[0] & 3) == 3)
102 /* --- Reduce and swap --- */
105 { mp
*t
= n
; n
= a
; a
= t
; }
108 /* --- Wrap everything up --- */
116 /*----- Test rig ----------------------------------------------------------*/
120 #include <mLib/testrig.h>
122 static int verify(dstr
*v
)
124 mp
*a
= *(mp
**)v
[0].buf
;
125 mp
*n
= *(mp
**)v
[1].buf
;
126 int s
= *(int *)v
[2].buf
;
127 int j
= mp_jacobi(a
, n
);
131 fputs("\n*** fail", stderr
);
132 fputs("a = ", stderr
); mp_writefile(a
, stderr
, 10); fputc('\n', stderr
);
133 fputs("n = ", stderr
); mp_writefile(n
, stderr
, 10); fputc('\n', stderr
);
134 fprintf(stderr
, "s = %i\n", s
);
135 fprintf(stderr
, "j = %i\n", j
);
141 assert(mparena_count(MPARENA_GLOBAL
) == 0);
145 static test_chunk tests
[] = {
146 { "jacobi", verify
, { &type_mp
, &type_mp
, &type_int
, 0 } },
150 int main(int argc
, char *argv
[])
153 test_run(argc
, argv
, tests
, SRCDIR
"/tests/mp");
159 /*----- That's all, folks -------------------------------------------------*/