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 /*----- Header files ------------------------------------------------------*/
34 /*----- Main code ---------------------------------------------------------*/
36 /* --- @mp_jacobi@ --- *
38 * Arguments: @mp *a@ = an integer less than @n@
39 * @mp *n@ = an odd integer
41 * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
43 * Use: Computes the Jacobi symbol. If @n@ is prime, this is the
44 * Legendre symbol and is equal to 1 if and only if @a@ is a
45 * quadratic residue mod @n@. The result is zero if and only if
46 * @a@ and @n@ have a common factor greater than one.
49 int mp_jacobi(mp
*a
, mp
*n
)
55 /* --- Take copies of the arguments --- */
60 /* --- Main recursive mess, flattened out into something nice --- */
66 /* --- Some simple special cases --- */
74 /* --- Main case with powers of two --- */
78 if ((e
& 1) && (nn
== 3 || nn
== 5))
80 if (MP_LEN(a
) == 1 && a
->v
[0] == 1)
82 if ((nn
& 3) == 3 && (a
->v
[0] & 3) == 3)
85 /* --- Reduce and swap --- */
88 { mp
*t
= n
; n
= a
; a
= t
; }
91 /* --- Wrap everything up --- */
99 /*----- Test rig ----------------------------------------------------------*/
103 #include <mLib/testrig.h>
105 static int verify(dstr
*v
)
107 mp
*a
= *(mp
**)v
[0].buf
;
108 mp
*n
= *(mp
**)v
[1].buf
;
109 int s
= *(int *)v
[2].buf
;
110 int j
= mp_jacobi(a
, n
);
114 fputs("\n*** fail", stderr
);
115 fputs("a = ", stderr
); mp_writefile(a
, stderr
, 10); fputc('\n', stderr
);
116 fputs("n = ", stderr
); mp_writefile(n
, stderr
, 10); fputc('\n', stderr
);
117 fprintf(stderr
, "s = %i\n", s
);
118 fprintf(stderr
, "j = %i\n", j
);
124 assert(mparena_count(MPARENA_GLOBAL
) == 0);
128 static test_chunk tests
[] = {
129 { "jacobi", verify
, { &type_mp
, &type_mp
, &type_int
, 0 } },
133 int main(int argc
, char *argv
[])
136 test_run(argc
, argv
, tests
, SRCDIR
"/tests/mp");
142 /*----- That's all, folks -------------------------------------------------*/