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
|
/* See LICENSE file for copyright and license details. */
/* Warning: libzahl is not thread-safe. */
#include <stddef.h>
#include <setjmp.h>
#include <stdint.h>
/* This structure should be considered opaque. */
typedef struct {
int sign;
size_t used;
size_t alloced;
uint32_t *chars;
} z_t[1];
enum zprimality { NONPRIME = 0, PROBABLY_PRIME, PRIME };
enum zranddev { FAST_RANDOM = 0, SECURE_RANDOM };
enum zranddist { QUASIUNIFORM = 0, UNIFORM };
/* The parameters in the functions below are numbers a, b, c, ... */
/* Library initialisation and destruction. */
void zsetup(jmp_buf); /* Prepare libzahl for use. */
void zunsetup(void); /* Free resources used by libzahl */
/* Memory functions. */
void zinit(z_t); /* Prepare a for use. */
void zfree(z_t); /* Free resources in a. */
void zswap(z_t, z_t); /* (a, b) := (b, a) */
size_t zsave(z_t, void *); /* Store a into b (if !!b), and return number of written bytes. */
size_t zload(z_t, const void *); /* Restore a from b, and return number of read bytes. */
/* Assignment functions. */
/* a := b */
void zset(z_t, z_t);
void zseti(z_t, long long int);
void zsetu(z_t, unsigned long long int);
/* Comparison functions. */
/* signum (a - b) */
int zcmp(z_t, z_t);
int zcmpi(z_t, long long int);
int zcmpu(z_t, unsigned long long int);
int zcmpmag(z_t, z_t); /* signum (|a| - |b|) */
/* Arithmetic functions. */
void zadd(z_t, z_t, z_t); /* a := b + c */
void zsub(z_t, z_t, z_t); /* a := b - c */
void zmul(z_t, z_t, z_t); /* a := b * c */
void zmodmul(z_t, z_t, z_t, z_t); /* a := (b * c) % d */
void zdiv(z_t, z_t, z_t); /* a := b / c */
void zdivmod(z_t, z_t, z_t, z_t); /* a := c / d, b = c % d */
void zmod(z_t, z_t, z_t); /* a := b % c */
void zsqr(z_t, z_t); /* a := b² */
void zneg(z_t, z_t); /* a := -b */
void zabs(z_t, z_t); /* a := |b| */
void zpow(z_t, z_t, z_t); /* a := b ↑ c */
void zmodpow(z_t, z_t, z_t, z_t); /* a := (b ↑ c) % d */
/* These are used internally and may be removed in a future version. */
void zadd_unsigned(z_t, z_t, z_t); /* a := |b| + |c|, b and c must not be the same reference. */
void zsub_unsigned(z_t, z_t, z_t); /* a := |b| - |c|, b and c must not be the same reference. */
void zsub_positive(z_t, z_t, z_t); /* a := |b| - |c|, assumes b ≥ c and that, and b is not c. */
/* Bitwise operations. */
void zand(z_t, z_t, z_t); /* a := b & c */
void zor(z_t, z_t, z_t); /* a := b | c */
void zxor(z_t, z_t, z_t); /* a := b ^ c */
void znot(z_t, z_t); /* a := ~b */
void zlsh(z_t, z_t, size_t); /* a := b << c */
void zrsh(z_t, z_t, size_t); /* a := b >> c */
int zbtest(z_t, size_t); /* (a >> b) & 1 */
void zsplit(z_t, z_t, z_t, size_t); /* a := c >> d, b := c - (a << d) */
size_t zbits(z_t); /* ⌊log₂ |a|⌋ + 1, 1 if a = 0 */
size_t zlsb(z_t); /* Index of first set bit, SIZE_MAX if none are set. */
/* Number theory. */
void zgcd(z_t, z_t, z_t); /* a := gcd(b, c) */
/* NONPRIME if b ∉ ℙ, PROBABLY_PRIME, if b ∈ ℙ with (1 − 4↑−c) certainty, 2 if PRIME ∈ ℙ.
* If NONPRIME is returned the witness of b's compositeness is stored in a unless a is NONPRIME. */
enum zprimality zptest(z_t, z_t, int);
/* Random number generation. */
/* Pick a randomly from [0, d] ∩ ℤ. */
void zrand(z_t, enum zranddev, enum zranddist, z_t);
/* String conversion. */
char *zstr(z_t, char *); /* Write a in decimal onto b. */
int zsets(z_t, const char *); /* a := b */
/* Length of a in radix b, assuming a > 0. */
size_t zstr_length_positive(z_t, unsigned long long int);
/* Inline functions. */
static inline int zeven(z_t a) { return !a->sign || !(a->chars[0] & 1); } /* Is a even? */
static inline int zodd(z_t a) { return a->sign && (a->chars[0] & 1); } /* Is a odd? */
static inline int zeven_nonzero(z_t a) { return !(a->chars[0] & 1); } /* Is a even? Assumes a ≠ 0. */
static inline int zodd_nonzero(z_t a) { return (a->chars[0] & 1); } /* Is a odd? Assumes a ≠ 0. */
static inline int zzero(z_t a) { return !a->sign; } /* Is a zero? */
static inline int zsignum(z_t a) { return a->sign; } /* a/|a|, 0 if a is zero */
|
