1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
/* gen-jacobi.c
Contributed to the GNU project by Niels Möller.
Copyright 2010 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
The GNU MP Library is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 3 of the License, or (at your
option) any later version.
The GNU MP Library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
License for more details.
You should have received a copy of the GNU Lesser General Public License
along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
/* Generate the lookup table needed for fast left-to-right computation
of the Jacobi symbol. */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
static const struct
{
unsigned char a;
unsigned char b;
} decode_table[13] = {
/* 0 */ { 0, 1 },
/* 1 */ { 0, 3 },
/* 2 */ { 1, 1 },
/* 3 */ { 1, 3 },
/* 4 */ { 2, 1 },
/* 5 */ { 2, 3 },
/* 6 */ { 3, 1 },
/* 7 */ { 3, 3 }, /* d = 1 */
/* 8 */ { 1, 0 },
/* 9 */ { 1, 2 },
/* 10 */ { 3, 0 },
/* 11 */ { 3, 2 },
/* 12 */ { 3, 3 }, /* d = 0 */
};
#define JACOBI_A(bits) (decode_table[(bits)>>1].a)
#define JACOBI_B(bits) (decode_table[(bits)>>1].b)
#define JACOBI_E(bits) ((bits) & 1)
#define JACOBI_D(bits) (((bits)>>1) == 7) /* Gives 0 for don't care states. */
static unsigned
encode (unsigned a, unsigned b, unsigned d)
{
unsigned i;
assert (d < 2);
assert (a < 4);
assert (b < 4);
assert ( (a | b ) & 1);
if (a == 3 && b == 3)
return d ? 7 : 12;
for (i = 0; i < 12; i++)
if (decode_table[i].a == a
&& decode_table[i].b == b)
return i;
abort ();
}
int
main (int argc, char **argv)
{
unsigned bits;
for (bits = 0; bits < 208; bits++)
{
unsigned e, a, b, d_old, d, q;
if (bits && !(bits & 0xf))
printf("\n");
q = bits & 3;
d = (bits >> 2) & 1;
e = JACOBI_E (bits >> 3);
a = JACOBI_A (bits >> 3);
b = JACOBI_B (bits >> 3);
d_old = JACOBI_D (bits >> 3);
if (d != d_old && a == 3 && b == 3)
e ^= 1;
if (d == 1)
{
if (b == 2)
e ^= (q & (a >> 1)) ^ (q >> 1);
a = (a - q * b) & 3;
}
else
{
if (a == 2)
e ^= (q & (b >> 1)) ^ (q >> 1);
b = (b - q * a) & 3;
}
printf("%2d,", (encode (a, b, d) << 1) | e);
}
printf("\n");
return 0;
}
|
