3 * $Id: mp-jacobi.c,v 1.2 1999/12/10 23:19:02 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.2 1999/12/10 23:19:02 mdw
34 * Improve error-checking.
36 * Revision 1.1 1999/11/22 20:50:37 mdw
37 * Add support for computing Jacobi symbols.
41 /*----- Header files ------------------------------------------------------*/
45 /*----- Main code ---------------------------------------------------------*/
47 /* --- @mp_jacobi@ --- *
49 * Arguments: @mp *a@ = an integer less than @n@
50 * @mp *n@ = an odd integer
52 * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
54 * Use: Computes the Jacobi symbol. If @n@ is prime, this is the
55 * Legendre symbol and is equal to 1 if and only if @a@ is a
56 * quadratic residue mod @n@. The result is zero if and only if
57 * @a@ and @n@ have a common factor greater than one.
60 int mp_jacobi(mp
*a
, mp
*n
)
64 /* --- Take copies of the arguments --- */
69 /* --- Main recursive mess, flattened out into something nice --- */
73 /* --- Some simple special cases --- */
82 /* --- Find the power-of-two factor in @a@ --- */
89 /* --- Scan for a set bit --- */
93 while (MP_STEP(&sc
) && !MP_BIT(&sc
))
96 /* --- Do the shift --- */
101 /* --- Maybe adjust the sign of @s@ --- */
104 if ((e
& 1) && (nn
== 3 || nn
== 5))
107 if (MP_LEN(a
) == 1 && a
->v
[0] == 1)
110 if ((nn
& 3) == 3 && (a
->v
[0] & 3) == 3)
114 /* --- Reduce and swap --- */
117 { mp
*t
= n
; n
= a
; a
= t
; }
120 /* --- Wrap everything up --- */
128 /*----- Test rig ----------------------------------------------------------*/
132 #include <mLib/testrig.h>
134 static int verify(dstr
*v
)
136 mp
*a
= *(mp
**)v
[0].buf
;
137 mp
*n
= *(mp
**)v
[1].buf
;
138 int s
= *(int *)v
[2].buf
;
139 int j
= mp_jacobi(a
, n
);
143 fputs("\n*** fail", stderr
);
144 fputs("a = ", stderr
); mp_writefile(a
, stderr
, 10); fputc('\n', stderr
);
145 fputs("n = ", stderr
); mp_writefile(n
, stderr
, 10); fputc('\n', stderr
);
146 fprintf(stderr
, "s = %i\n", s
);
147 fprintf(stderr
, "j = %i\n", j
);
153 assert(mparena_count(MPARENA_GLOBAL
) == 0);
157 static test_chunk tests
[] = {
158 { "jacobi", verify
, { &type_mp
, &type_mp
, &type_int
, 0 } },
162 int main(int argc
, char *argv
[])
165 test_run(argc
, argv
, tests
, SRCDIR
"/tests/mp");
171 /*----- That's all, folks -------------------------------------------------*/