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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
//! A Trait for Finite Field Arithmetic for Fp^2 with modulus x^2 + 1.
//!
//! # Warning
//!
//! This library, and hence this trait are currently only configured to work with the finite field
//! Fp^2, a degree two extension of Fp with modulus x^2 + 1 (hence we require p = 3 mod 4). This is
//! the finite field most used in isogeny-based cryptography, for which this library has been
//! developed for. Accomodating other finite fields to work with this trait is possible and can be
//! done in the future
use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
use std::fmt::Display;
/// A trait for finite field arithmetic for the field Fp^2 with modulus x^2 + 1.
pub trait Fq:
Copy
+ Neg<Output = Self>
+ Add<Output = Self>
+ AddAssign
+ Sub<Output = Self>
+ SubAssign
+ Mul<Output = Self>
+ MulAssign
+ Div<Output = Self>
+ DivAssign
+ Display
{
/// The length of the encoded representation of the finite field element.
const ENCODED_LENGTH: usize;
/// Predefined constant element representing the value 0 + 0*i.
const ZERO: Self;
/// Predefined constant element representing the value 1 + 0*i.
const ONE: Self;
/// Predefined constant element representing the value 2 + 0*i.
const TWO: Self;
/// Predefined constant element representing the value 3 + 0*i.
const THREE: Self;
/// Predefined constant element representing the value 4 + 0*i.
const FOUR: Self;
/// Predefined constant element representing the value -1 + 0*i.
const MINUS_ONE: Self;
/// Predefined constant element representing the value 0 + i such that
/// i^2 = -1, a fourth-root of unity.
const ZETA: Self;
/// Predefined constant element representing the value 0 - i such that
/// i^2 = -1, a fourth-root of unity.
const MINUS_ZETA: Self;
/// Return the value x + i*0 for a given integer x of type `i32`.
fn from_i32(x: i32) -> Self;
/// Return the value x + i*0 for a given integer x of type `u32`.
fn from_u32(x: u32) -> Self;
/// Return the value x + i*0 for a given integer x of type `i64`.
fn from_i64(x: i64) -> Self;
/// Return the value x + i*0 for a given integer x of type `u64`.
fn from_u64(x: u64) -> Self;
/// Return the value x0 + i*x1 for a given two integers of type `i32`.
fn from_i32_pair(x0: i32, x1: i32) -> Self;
/// Return the value x0 + i*x1 for a given two integers of type `u32`.
fn from_u32_pair(x0: u32, x1: u32) -> Self;
/// Return the value x0 + i*x1 for a given two integers of type `i64`.
fn from_i64_pair(x0: i64, x1: i64) -> Self;
/// Return the value x0 + i*x1 for a given two integers of type `u64`.
fn from_u64_pair(x0: u64, x1: u64) -> Self;
/// Set the "real" component of self to an integer of type `i32` in place.
fn set_x0_small(&mut self, x: i32);
/// Set the "imaginary" component of self to an integer of type `i32` in place.
fn set_x1_small(&mut self, x: i32);
/// Return `0xFFFFFFFF` if this value is zero, or `0x00000000` otherwise.
fn is_zero(self) -> u32;
/// Return `0xFFFFFFFF` if this value is equal to rhs, or `0x00000000`
/// otherwise.
fn equals(self, rhs: &Self) -> u32;
/// Negate this value.
fn set_neg(&mut self);
/// Halve this value.
fn set_half(&mut self);
/// Double this value.
fn set_mul2(&mut self);
/// Triple this value.
fn set_mul3(&mut self);
/// Quadruple this value.
fn set_mul4(&mut self);
/// Multiply this value by 8
fn set_mul8(&mut self);
/// Compute the half of this value.
fn half(self) -> Self;
/// Compute the sum of this value with itself.
fn mul2(self) -> Self;
/// Compute the triple of this value.
fn mul3(self) -> Self;
/// Compute the quadruple of this value.
fn mul4(self) -> Self;
/// Compute 8 times this value.
fn mul8(self) -> Self;
/// Negate the imaginary pary of this value
fn set_conjugate(&mut self);
/// Multiply this value by a small signed integer.
fn set_mul_small(&mut self, k: i32);
/// Replace this value with its square.
fn set_square(&mut self);
/// Replace this value with its inverse.
fn set_invert(&mut self);
/// Raise this value to the power `e`. Exponent `e` is encoded in
/// unsigned little-endian convention over exactly `ebitlen` bits.
fn set_pow(&mut self, e: &[u8], ebitlen: usize);
/// Raise this value to the power e. Exponent e is encoded in
/// unsigned little-endian convention, over exactly `ebitlen` bits,
/// and starting at the bit offset eoff.
fn set_pow_ext(&mut self, e: &[u8], eoff: usize, ebitlen: usize);
/// Raise this value to the power `e`. The exponent length (in bits)
/// MUST be at most `ebitlen`. This is constant-time for both the
/// base value (`self`) and the exponent (`e`); the exponent maximum
/// size (`ebitlen`) is considered non-secret.
fn set_pow_u64(&mut self, e: u64, ebitlen: usize);
/// Raise this value to the power `e`. The exponent is considered
/// non-secret.
fn set_pow_u64_vartime(&mut self, e: u64);
/// Compute the complex conjugate of the value a + i*b, i.e. a - i*b.
fn conjugate(self) -> Self;
/// Compute the product of this value by a small (unsigned) integer `k`.
fn mul_small(self, k: i32) -> Self;
/// Compute the square of this value.
fn square(self) -> Self;
/// Compute the inverse of this value
fn invert(self) -> Self;
/// Return this value to the power `e` (as a new element). Exponent `e`
/// is encoded in unsigned little-endian convention over exactly
/// `ebitlen` bits.
fn pow(self, e: &[u8], ebitlen: usize) -> Self;
/// Return this value to the power `e` (as a new element). Exponent `e`
/// is encoded in unsigned little-endian convention over exactly
/// `ebitlen` bits, and starting at the bit offset eoff.
fn pow_ext(self, e: &[u8], eoff: usize, ebitlen: usize) -> Self;
/// Return this value to the power `e`. The exponent length (in bits)
/// MUST be at most `ebitlen`. This is constant-time for both the
/// base value (`self`) and the exponent (`e`); the exponent maximum
/// size (`ebitlen`) is considered non-secret.
fn pow_u64(&mut self, e: u64, ebitlen: usize) -> Self;
/// Return this value to the power e. The exponent is considered
/// non-secret.
fn pow_u64_vartime(&mut self, e: u64) -> Self;
/// Set this value to its square root. Returned value is `0xFFFFFFFF` if
/// the operation succeeded (value was indeed a quadratic residue), or
/// `0x00000000` otherwise. On success, the chosen root is the one whose
/// least significant bit (as an integer in `[0..p-1]`) is zero. On
/// failure, this value is set to zero.
fn set_sqrt(&mut self) -> u32;
/// Set this value to its fourth root. Returned value is `0xFFFFFFFF` if
/// the operation succeeded (value was indeed some element to the power of four), or
/// `0x00000000` otherwise. On success, the chosen root is the one whose
/// least significant bit (as an integer in `[0..p-1]`) is zero. On
/// failure, this value is set to zero.
fn set_fourth_root(&mut self) -> u32;
/// Compute the square root of this value. If this value is indeed a
/// quadratic residue, then this returns `(x, 0xFFFFFFFF)`, with `x` being
/// the (unique) square root of this value whose least significant bit
/// is zero (when normalized to an integer in `[0..p-1]`). If this value
/// is not a quadratic residue, then this returns (zero, `0x00000000`).
fn sqrt(self) -> (Self, u32);
/// Compute the fourth root of this value. If this value is indeed some
/// element to the power of four, then this returns `(x, 0xFFFFFFFF)`, with `x` being
/// the (unique) fourth root of this value whose least significant bit
/// is zero (when normalized to an integer in `[0..p-1]`). If this value
/// is not some element to the power of four, then this returns (zero, `0x00000000`).
fn fourth_root(self) -> (Self, u32);
/// Legendre symbol on this value. Return value is:
/// - 0 if this value is zero
/// - +1 if this value is a non-zero quadratic residue
/// - -1 if this value is not a quadratic residue
fn legendre(self) -> i32;
/// Precompute two vectors of values used to optimally solve the dlog
/// for elements of order 2^n exactly.
///
/// Explicitly, this involves computing:
/// - A table dlog_table of indicies corresponding to where to split
/// the dlog recursively of type Vec<usize>
/// - A table of Fp2 elements `gpp[j] = g^(2^dlog_table[j])` of type
/// of type `Vec<Self>`
///
/// Note that the first value (`gpp[0]`) is `g` itself, and the last one must
/// be `-1` (otherwise, `g` does not have order exactly 2^e).
fn precompute_dlp_tables(self, n: usize) -> (Vec<usize>, Vec<Self>, u32);
/// Find integer `v` (modulo 2^e) such that `x = self^v`. If self
/// has order exactly 2^e, and there is a solution v, then this
/// function returns (v, `0xFFFFFFFF`). If self does not have order
/// exactly 2^e (including if `self^(2^(e-1)) = 1`, i.e. the order of
/// self is a strict divisor or 2^e), or if there is no solution,
/// then this function returns `(0, 0)`.
///
/// Optionally include precomputed values from the method precompute_dlp_tables
/// otherwise these are computed at runtime.
fn solve_dlp_2e(
self,
x: &Self,
e: usize,
precomputed_tables: Option<(&Vec<usize>, &Vec<Self>)>,
) -> (Vec<u8>, u32);
/// Given `n` elements, computes the inverse of all elements in-place at a cost
/// of one inversion and 3*(n - 1) multiplications using Montgomery's trick
fn batch_invert(xx: &mut [Self]);
/// Return `a` or `b`, if `ctl` is `0x00000000` or `0xFFFFFFFF`, respectively.
/// `ctl` MUST be either `0x00000000` or `0xFFFFFFFF`.
/// The value of `ctl` MUST be either `0x00000000` or `0xFFFFFFFF`.
fn set_select(&mut self, a: &Self, b: &Self, ctl: u32);
/// Set this value to `rhs` if `ctl` is `0xFFFFFFFF`; leave it unchanged if
/// `ctl` is `0x00000000`.
/// The value of `ctl` MUST be either `0x00000000` or `0xFFFFFFFF`.
fn set_cond(&mut self, rhs: &Self, ctl: u32);
/// Negate this value if `ctl` is `0xFFFFFFFF`; leave it unchanged if
/// `ctl` is `0x00000000`.
/// The value of `ctl` MUST be either `0x00000000` or `0xFFFFFFFF`.
fn set_condneg(&mut self, ctl: u32);
/// Return `a` or `b`, if `ctl` is `0x00000000` or `0xFFFFFFFF`, respectively.
/// `ctl` MUST be either `0x00000000` or `0xFFFFFFFF`.
/// The value of `ctl` MUST be either `0x00000000` or `0xFFFFFFFF`.
fn select(a: &Self, b: &Self, ctl: u32) -> Self;
/// Exchange the values of `a` and `b` is `ctl` is `0xFFFFFFFF`; leave both
/// values unchanged if `ctl` is `0x00000000`.
/// The value of `ctl` MUST be either `0x00000000` or `0xFFFFFFFF`.
fn condswap(a: &mut Self, b: &mut Self, ctl: u32);
/// Encode this value into bytes. Encoding uses little-endian, has
/// a fixed size (for a given field), and is canonical.
fn encode(self) -> [u8; Self::ENCODED_LENGTH];
/// Decode the provided bytes into a field element. Returned values
/// are the element and `0xFFFFFFFF` on success, or the zero element and
/// `0x00000000` on failure. A failure is reported if the source slice
/// does not have exactly the canonical encoding length of a field
/// element (`Self::ENCODED_LENGTH`), or if the source encodes
/// an integer which is not in the `[0..(p-1)]` range.
fn decode(buf: &[u8]) -> (Self, u32);
/// Decode the provided bytes into a field element. The source slice
/// can have arbitrary length; the bytes are interpreted with the
/// unsigned little-endian convention (no sign bit), with the first half
/// of the bytes corresponding to x0 and the latter half to x1. For each
/// resulting integer, the result is reduced modulo the field modulus p.
/// By definition, this function does not enforce canonicality of the source
/// value.
fn decode_reduce(buf: &[u8]) -> Self;
/// Set this structure to a random field element (indistinguishable
/// from uniform generation).
fn set_rand<R: ::rand_core::CryptoRng + ::rand_core::RngCore>(&mut self, rng: &mut R);
/// Return a new random field element (indistinguishable from
/// uniform generation).
fn rand<R: ::rand_core::CryptoRng + ::rand_core::RngCore>(rng: &mut R) -> Self;
/// Get the "hash" of the value. For x = a + i*b, this is:
/// `(hashcode(a) << 1) | (hashcode(b) & 1)`
/// i.e. bit `0` is bit `0` of `b`, and bits 1..63 are bits 0..62 of `a`
/// (both in Montgomery representation).
fn hashcode(self) -> u64;
}