3 Contributed to the GNU project by Niels Möller.
5 Copyright 2010 Free Software Foundation, Inc.
7 This file is part of the GNU MP Library.
9 The GNU MP Library is free software; you can redistribute it and/or modify
10 it under the terms of the GNU Lesser General Public License as published by
11 the Free Software Foundation; either version 3 of the License, or (at your
12 option) any later version.
14 The GNU MP Library is distributed in the hope that it will be useful, but
15 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
16 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
17 License for more details.
19 You should have received a copy of the GNU Lesser General Public License
20 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
22 /* Generate the lookup table needed for fast left-to-right computation
23 of the Jacobi symbol. */
33 } decode_table[13] = {
41 /* 7 */ { 3, 3 }, /* d = 1 */
46 /* 12 */ { 3, 3 }, /* d = 0 */
49 #define JACOBI_A(bits) (decode_table[(bits)>>1].a)
50 #define JACOBI_B(bits) (decode_table[(bits)>>1].b)
52 #define JACOBI_E(bits) ((bits) & 1)
53 #define JACOBI_D(bits) (((bits)>>1) == 7) /* Gives 0 for don't care states. */
56 encode (unsigned a, unsigned b, unsigned d)
63 assert ( (a | b ) & 1);
68 for (i = 0; i < 12; i++)
69 if (decode_table[i].a == a
70 && decode_table[i].b == b)
77 main (int argc, char **argv)
81 for (bits = 0; bits < 208; bits++)
83 unsigned e, a, b, d_old, d, q;
85 if (bits && !(bits & 0xf))
91 e = JACOBI_E (bits >> 3);
92 a = JACOBI_A (bits >> 3);
93 b = JACOBI_B (bits >> 3);
94 d_old = JACOBI_D (bits >> 3);
96 if (d != d_old && a == 3 && b == 3)
102 e ^= (q & (a >> 1)) ^ (q >> 1);
108 e ^= (q & (b >> 1)) ^ (q >> 1);
112 printf("%2d,", (encode (a, b, d) << 1) | e);