3 * $Id: mp-jacobi.c,v 1.3 2000/07/20 17:14:34 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.3 2000/07/20 17:14:34 mdw
34 * Simplify by using @mp_odd@.
36 * Revision 1.2 1999/12/10 23:19:02 mdw
37 * Improve error-checking.
39 * Revision 1.1 1999/11/22 20:50:37 mdw
40 * Add support for computing Jacobi symbols.
44 /*----- Header files ------------------------------------------------------*/
48 /*----- Main code ---------------------------------------------------------*/
50 /* --- @mp_jacobi@ --- *
52 * Arguments: @mp *a@ = an integer less than @n@
53 * @mp *n@ = an odd integer
55 * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
57 * Use: Computes the Jacobi symbol. If @n@ is prime, this is the
58 * Legendre symbol and is equal to 1 if and only if @a@ is a
59 * quadratic residue mod @n@. The result is zero if and only if
60 * @a@ and @n@ have a common factor greater than one.
63 int mp_jacobi(mp
*a
, mp
*n
)
67 /* --- Take copies of the arguments --- */
72 /* --- Main recursive mess, flattened out into something nice --- */
78 /* --- Some simple special cases --- */
86 /* --- Main case with powers of two --- */
90 if ((e
& 1) && (nn
== 3 || nn
== 5))
92 if (MP_LEN(a
) == 1 && a
->v
[0] == 1)
94 if ((nn
& 3) == 3 && (a
->v
[0] & 3) == 3)
97 /* --- Reduce and swap --- */
100 { mp
*t
= n
; n
= a
; a
= t
; }
103 /* --- Wrap everything up --- */
111 /*----- Test rig ----------------------------------------------------------*/
115 #include <mLib/testrig.h>
117 static int verify(dstr
*v
)
119 mp
*a
= *(mp
**)v
[0].buf
;
120 mp
*n
= *(mp
**)v
[1].buf
;
121 int s
= *(int *)v
[2].buf
;
122 int j
= mp_jacobi(a
, n
);
126 fputs("\n*** fail", stderr
);
127 fputs("a = ", stderr
); mp_writefile(a
, stderr
, 10); fputc('\n', stderr
);
128 fputs("n = ", stderr
); mp_writefile(n
, stderr
, 10); fputc('\n', stderr
);
129 fprintf(stderr
, "s = %i\n", s
);
130 fprintf(stderr
, "j = %i\n", j
);
136 assert(mparena_count(MPARENA_GLOBAL
) == 0);
140 static test_chunk tests
[] = {
141 { "jacobi", verify
, { &type_mp
, &type_mp
, &type_int
, 0 } },
145 int main(int argc
, char *argv
[])
148 test_run(argc
, argv
, tests
, SRCDIR
"/tests/mp");
154 /*----- That's all, folks -------------------------------------------------*/