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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
#include <gmp.h>
#include <stddef.h>
#include <setjmp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define BIGINT_LIBRARY "GMP"
typedef mpz_t z_t;
static z_t _0, _1, _a, _b;
static FILE *_fbuf;
static gmp_randstate_t _randstate;
static inline void
zsetup(jmp_buf env)
{
static char buf[1000];
(void) env;
mpz_init_set_ui(_0, 0);
mpz_init_set_ui(_1, 1);
mpz_init(_a);
mpz_init(_b);
_fbuf = fmemopen(buf, sizeof(buf), "r+");
gmp_randinit_mt(_randstate);
}
static inline void
zunsetup(void)
{
mpz_clear(_0);
mpz_clear(_1);
mpz_clear(_a);
mpz_clear(_b);
fclose(_fbuf);
gmp_randclear(_randstate);
}
#define FAST_RANDOM 0
#define SECURE_RANDOM 0
#define DEFAULT_RANDOM 0
#define FASTEST_RANDOM 0
#define LIBC_RAND_RANDOM 0
#define LIBC_RANDOM_RANDOM 0
#define LIBC_RAND48_RANDOM 0
#define QUASIUNIFORM 0
#define UNIFORM 1
#define MODUNIFORM 2
#define zperror(x) ((void)0)
#define zinit mpz_init
#define zfree mpz_clear
#define zset mpz_set
#define zneg mpz_neg
#define zabs mpz_abs
#define zadd_unsigned(r, a, b) (zabs(_a, a), zabs(_b, b), mpz_add(r, _a, _b))
#define zsub_unsigned(r, a, b) (zabs(_a, a), zabs(_b, b), mpz_sub(r, _a, _b))
#define zadd mpz_add
#define zsub mpz_sub
#define zand mpz_and
#define zor mpz_ior
#define zxor mpz_xor
#define zbtest mpz_tstbit
#define zeven mpz_even_p /* Note, must not have side effects. */
#define zodd mpz_odd_p /* Note, must not have side effects. */
#define zeven_nonzero zeven
#define zodd_nonzero zodd
#define zzero(a) (!mpz_sgn(a))
#define zsignum mpz_sgn
#define zbits(a) mpz_sizeinbase(a, 2)
#define zlsb(a) mpz_scan1(a, 0)
#define zswap mpz_swap
#define zlsh mpz_mul_2exp
#define zrsh mpz_tdiv_q_2exp
#define ztrunc mpz_tdiv_r_2exp
#define zcmpmag mpz_cmpabs
#define zcmp mpz_cmp
#define zcmpi(a, b) (zseti(_b, b), zcmp(a, _b))
#define zcmpu(a, b) (zsetu(_b, b), zcmp(a, _b))
#define zgcd mpz_gcd
#define zmul mpz_mul
#define zsqr(r, a) mpz_mul(r, a, a)
#define zmodmul(r, a, b, m) (zmul(r, a, b), zmod(r, r, m))
#define zmodsqr(r, a, m) (zsqr(r, a), zmod(r, r, m))
#define zpow(r, a, b) mpz_pow_ui(r, a, mpz_get_ui(b))
#define zpowu mpz_pow_ui
#define zmodpow mpz_powm
#define zmodpowu mpz_powm_ui
#define zsets(a, s) mpz_set_str(a, s, 10)
#define zstr_length(a, b) (mpz_sizeinbase(a, 10) + (zsignum(a) < 0))
#define zstr(a, s, n) (mpz_get_str(s, 10, a))
#define zptest(w, a, t) mpz_probab_prime_p(a, t) /* Note, the witness is not returned. */
#define zdiv mpz_tdiv_q
#define zmod mpz_tdiv_r
#define zdivmod mpz_tdiv_qr
static inline void
zsetu(z_t r, unsigned long long int val)
{
uint32_t high = (uint32_t)(val >> 32);
uint32_t low = (uint32_t)val;
if (high) {
mpz_set_ui(r, high);
mpz_set_ui(_a, low);
zlsh(r, r, 32);
zadd(r, r, _a);
} else {
mpz_set_ui(r, low);
}
}
static inline void
zseti(z_t r, long long int val)
{
if (val >= 0) {
zsetu(r, (unsigned long long int)val);
} else {
zsetu(r, (unsigned long long int)-val);
zneg(r, r);
}
}
static inline void
znot(z_t r, z_t a)
{
size_t bits = zbits(a);
mpz_set_ui(_b, 0);
mpz_setbit(_b, bits);
zsub(_b, _b, _1);
zxor(r, a, _b);
zneg(r, r);
}
static inline void
zsplit(z_t high, z_t low, z_t a, size_t brk)
{
if (low == a) {
zrsh(high, a, brk);
ztrunc(low, a, brk);
} else {
ztrunc(low, a, brk);
zrsh(high, a, brk);
}
}
static inline void
zbset(z_t r, z_t a, size_t bit, int mode)
{
if (r != a)
zset(r, a);
if (mode > 0)
mpz_setbit(r, bit);
else if (mode == 0)
mpz_clrbit(r, bit);
else
mpz_combit(r, bit);
}
static inline size_t
zsave(z_t a, void *buffer)
{
size_t n = mpz_out_raw(_fbuf, a);
(void)buffer;
fseek(_fbuf, -(long)n, SEEK_CUR);
return n;
}
static inline size_t
zload(z_t a, const void *buffer)
{
size_t n = mpz_inp_raw(a, _fbuf);
(void)buffer;
fseek(_fbuf, -(long)n, SEEK_CUR);
return n;
}
static inline void
zrand(z_t r, int dev, int dist, z_t n)
{
size_t bits;
(void) dev;
if (zzero(n)) {
mpz_set_ui(r, 0);
return;
}
if (zsignum(n) < 0) {
return;
}
switch (dist) {
case QUASIUNIFORM:
bits = zbits(n);
mpz_urandomb(r, _randstate, bits);
zadd(r, r, _1);
zmul(r, r, n);
zrsh(r, r, bits);
break;
case UNIFORM: /* Note, n is exclusive in this implementation. */
mpz_urandomm(r, _randstate, n);
break;
case MODUNIFORM:
bits = zbits(n);
mpz_urandomb(r, _randstate, bits);
if (zcmp(r, n) > 0)
zsub(r, r, n);
break;
default:
abort();
}
}
|
