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
|
#include <tommath.h>
#include <stddef.h>
#include <setjmp.h>
#include <stdint.h>
#include <stdio.h>
#define BIGINT_LIBRARY "libtommath"
typedef mp_int z_t[1];
static z_t _0, _1, _a, _b;
static int _tmp;
static void
zsetup(jmp_buf env)
{
(void) env;
mp_init_set_int(_0, 0);
mp_init_set_int(_1, 1);
mp_init(_a);
mp_init(_b);
}
static void
zunsetup(void)
{
mp_clear(_0);
mp_clear(_1);
mp_clear(_a);
mp_clear(_b);
}
#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(a) mp_init(a)
#define zfree(a) mp_clear(a)
#define zset(r, a) mp_copy(a, r)
#define zneg(r, a) mp_neg(a, r)
#define zabs(r, a) mp_abs(a, r)
#define zadd_unsigned(r, a, b) (mp_abs(a, _a), mp_abs(b, _b), mp_add(_a, _b, r))
#define zsub_unsigned(r, a, b) (mp_abs(a, _a), mp_abs(b, _b), mp_sub(_a, _b, r))
#define zadd(r, a, b) mp_add(a, b, r)
#define zsub(r, a, b) mp_sub(a, b, r)
#define zand(r, a, b) mp_and(a, b, r)
#define zor(r, a, b) mp_or(a, b, r)
#define zxor(r, a, b) mp_xor(a, b, r)
#define zeven(a) mp_iseven(a)
#define zodd(a) mp_isodd(a)
#define zeven_nonzero(a) mp_iseven(a)
#define zodd_nonzero(a) mp_isodd(a)
#define zzero(a) mp_iszero(a)
#define zsignum(a) mp_cmp(a, _0)
#define zbits(a) mp_count_bits(a)
#define zlsb(a) mp_cnt_lsb(a)
#define zswap(a, b) mp_exch(a, b)
#define zlsh(r, a, b) mp_mul_2d(a, b, r)
#define zrsh(r, a, b) mp_div_2d(a, b, r, 0)
#define ztrunc(r, a, b) mp_mod_2d(a, b, r)
#define zcmpmag(a, b) mp_cmp_mag(a, b)
#define zcmp(a, b) mp_cmp(a, b)
#define zcmpi(a, b) (zseti(_b, b), mp_cmp(a, _b))
#define zcmpu(a, b) (zsetu(_b, b), mp_cmp(a, _b))
#define zgcd(r, a, b) mp_gcd(a, b, r)
#define zmul(r, a, b) mp_mul(a, b, r)
#define zsqr(r, a) mp_sqr(a, r)
#define zmodmul(r, a, b, m) mp_mulmod(a, b, m, r)
#define zmodsqr(r, a, m) mp_sqrmod(a, m, r)
#define zpow(r, a, b) mp_expt_d(a, (mp_digit)mp_get_int(b), r)
#define zpowu(r, a, b) mp_expt_d(a, b, r)
#define zmodpow(r, a, b, m) mp_exptmod(a, b, m, r)
#define zmodpowu(r, a, b, m) (mp_set_int(_b, b), mp_exptmod(a, _b, m, r))
#define zsets(a, s) mp_read_radix(a, s, 10)
#define zstr_length(a, b) (mp_radix_size(a, b, &_tmp), _tmp)
#define zstr(a, s) mp_toradix(a, s, 10)
#define zptest(w, a, t) (mp_prime_is_prime(a, t, &_tmp), _tmp) /* Note, the witness is not returned. */
#define zload(a, s) mp_read_signed_bin(a, (unsigned char *)s, _tmp)
#define zdiv(r, a, b) mp_div(a, b, r, 0)
#define zmod(r, a, b) mp_mod(a, b, r)
#define zdivmod(q, r, a, b) mp_div(a, b, q, r)
static int
zsave(z_t a, char *buf)
{
_tmp = buf ? mp_signed_bin_size(a) : mp_to_signed_bin(a, (unsigned char *)buf);
return _tmp;
}
static 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) {
mp_set_int(r, high);
mp_set_int(_a, low);
mp_lshd(r, 32);
zadd(r, r, _a);
} else {
mp_set_int(r, low);
}
}
static 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 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 void
znot(z_t r, z_t a)
{
mp_2expt(_a, (int)zbits(a));
mp_sub_d(_a, 1, _a);
zand(r, a, _a);
zneg(r, r);
}
static int
zbtest(z_t a, size_t bit)
{
mp_2expt(_b, (int)bit);
zand(_b, a, _b);
return !zzero(_b);
}
static void
zbset(z_t r, z_t a, size_t bit, int mode)
{
if (mode > 0) {
mp_2expt(_b, (int)bit);
zor(r, a, _b);
} else if (mode < 0 || zbtest(a, bit)) {
mp_2expt(_b, (int)bit);
zxor(r, a, _b);
}
}
static void
zrand(z_t r, int dev, int dist, z_t n)
{
static int gave_up = 0;
int bits;
(void) dev;
if (zzero(n)) {
mp_zero(r);
return;
}
if (zsignum(n) < 0) {
return;
}
bits = zbits(n);
switch (dist) {
case QUASIUNIFORM:
mp_rand(r, bits);
zadd(r, r, _1);
zmul(r, r, n);
zrsh(r, r, bits);
break;
case UNIFORM:
if (!gave_up) {
gave_up = 1;
printf("I'm sorry, this is too difficult, I give up.\n");
}
break;
case MODUNIFORM:
mp_rand(r, bits);
if (zcmp(r, n) > 0)
zsub(r, r, n);
break;
default:
abort();
}
}
|
