3 * $Id: mp-jacobi.c,v 1.1 1999/11/22 20:50:37 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.1 1999/11/22 20:50:37 mdw
34 * Add support for computing Jacobi symbols.
38 /*----- Header files ------------------------------------------------------*/
42 /*----- Main code ---------------------------------------------------------*/
44 /* --- @mp_jacobi@ --- *
46 * Arguments: @mp *a@ = an integer less than @n@
47 * @mp *n@ = an odd integer
49 * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
51 * Use: Computes the Jacobi symbol. If @n@ is prime, this is the
52 * Legendre symbol and is equal to 1 if and only if @a@ is a
53 * quadratic residue mod @n@. The result is zero if and only if
54 * @a@ and @n@ have a common factor greater than one.
57 int mp_jacobi(mp
*a
, mp
*n
)
61 /* --- Take copies of the arguments --- */
66 /* --- Main recursive mess, flattened out into something nice --- */
70 /* --- Some simple special cases --- */
79 /* --- Find the power-of-two factor in @a@ --- */
86 /* --- Scan for a set bit --- */
90 while (MP_STEP(&sc
) && !MP_BIT(&sc
))
93 /* --- Do the shift --- */
98 /* --- Maybe adjust the sign of @s@ --- */
101 if ((e
& 1) && (nn
== 3 || nn
== 5))
104 if (MP_LEN(a
) == 1 && a
->v
[0] == 1)
107 if ((nn
& 3) == 3 && (a
->v
[0] & 3) == 3)
111 /* --- Reduce and swap --- */
114 { mp
*t
= n
; n
= a
; a
= t
; }
117 /* --- Wrap everything up --- */
125 /*----- Test rig ----------------------------------------------------------*/
129 #include <mLib/testrig.h>
131 static int verify(dstr
*v
)
133 mp
*a
= *(mp
**)v
[0].buf
;
134 mp
*n
= *(mp
**)v
[1].buf
;
135 int s
= *(int *)v
[2].buf
;
136 int j
= mp_jacobi(a
, n
);
140 fputs("\n*** fail", stderr
);
141 fputs("a = ", stderr
); mp_writefile(a
, stderr
, 10); fputc('\n', stderr
);
142 fputs("n = ", stderr
); mp_writefile(n
, stderr
, 10); fputc('\n', stderr
);
143 fprintf(stderr
, "s = %i\n", s
);
144 fprintf(stderr
, "j = %i\n", j
);
153 static test_chunk tests
[] = {
154 { "jacobi", verify
, { &type_mp
, &type_mp
, &type_int
, 0 } },
158 int main(int argc
, char *argv
[])
161 test_run(argc
, argv
, tests
, SRCDIR
"/tests/mp");
167 /*----- That's all, folks -------------------------------------------------*/