pasta_curves/fields/
fq.rs

Help
1use core::fmt;
2use core::ops::{Add, Mul, Neg, Sub};
3
4use ff::{Field, FromUniformBytes, PrimeField, WithSmallOrderMulGroup};
5use rand::RngCore;
6use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
7
8#[cfg(feature = "sqrt-table")]
9use lazy_static::lazy_static;
10
11#[cfg(feature = "bits")]
12use ff::{FieldBits, PrimeFieldBits};
13
14use crate::arithmetic::{adc, mac, sbb, SqrtTableHelpers};
15
16#[cfg(feature = "sqrt-table")]
17use crate::arithmetic::SqrtTables;
18
19/// This represents an element of $\mathbb{F}_q$ where
20///
21/// `q = 0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001`
22///
23/// is the base field of the Vesta curve.
24// The internal representation of this type is four 64-bit unsigned
25// integers in little-endian order. `Fq` values are always in
26// Montgomery form; i.e., Fq(a) = aR mod q, with R = 2^256.
27#[derive(Clone, Copy, Eq)]
28#[repr(transparent)]
29pub struct Fq(pub(crate) [u64; 4]);
30
31impl fmt::Debug for Fq {
32    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
33        let tmp = self.to_repr();
34        write!(f, "0x")?;
35        for &b in tmp.iter().rev() {
36            write!(f, "{:02x}", b)?;
37        }
38        Ok(())
39    }
40}
41
42impl From<bool> for Fq {
43    fn from(bit: bool) -> Fq {
44        if bit {
45            Fq::one()
46        } else {
47            Fq::zero()
48        }
49    }
50}
51
52impl From<u64> for Fq {
53    fn from(val: u64) -> Fq {
54        Fq([val, 0, 0, 0]) * R2
55    }
56}
57
58impl ConstantTimeEq for Fq {
59    fn ct_eq(&self, other: &Self) -> Choice {
60        self.0[0].ct_eq(&other.0[0])
61            & self.0[1].ct_eq(&other.0[1])
62            & self.0[2].ct_eq(&other.0[2])
63            & self.0[3].ct_eq(&other.0[3])
64    }
65}
66
67impl PartialEq for Fq {
68    #[inline]
69    fn eq(&self, other: &Self) -> bool {
70        self.ct_eq(other).unwrap_u8() == 1
71    }
72}
73
74impl core::cmp::Ord for Fq {
75    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
76        let left = self.to_repr();
77        let right = other.to_repr();
78        left.iter()
79            .zip(right.iter())
80            .rev()
81            .find_map(|(left_byte, right_byte)| match left_byte.cmp(right_byte) {
82                core::cmp::Ordering::Equal => None,
83                res => Some(res),
84            })
85            .unwrap_or(core::cmp::Ordering::Equal)
86    }
87}
88
89impl core::cmp::PartialOrd for Fq {
90    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
91        Some(self.cmp(other))
92    }
93}
94
95impl ConditionallySelectable for Fq {
96    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
97        Fq([
98            u64::conditional_select(&a.0[0], &b.0[0], choice),
99            u64::conditional_select(&a.0[1], &b.0[1], choice),
100            u64::conditional_select(&a.0[2], &b.0[2], choice),
101            u64::conditional_select(&a.0[3], &b.0[3], choice),
102        ])
103    }
104}
105
106/// Constant representing the modulus
107/// q = 0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001
108const MODULUS: Fq = Fq([
109    0x8c46eb2100000001,
110    0x224698fc0994a8dd,
111    0x0,
112    0x4000000000000000,
113]);
114
115/// The modulus as u32 limbs.
116#[cfg(not(target_pointer_width = "64"))]
117const MODULUS_LIMBS_32: [u32; 8] = [
118    0x0000_0001,
119    0x8c46_eb21,
120    0x0994_a8dd,
121    0x2246_98fc,
122    0x0000_0000,
123    0x0000_0000,
124    0x0000_0000,
125    0x4000_0000,
126];
127
128impl<'a> Neg for &'a Fq {
129    type Output = Fq;
130
131    #[inline]
132    fn neg(self) -> Fq {
133        self.neg()
134    }
135}
136
137impl Neg for Fq {
138    type Output = Fq;
139
140    #[inline]
141    fn neg(self) -> Fq {
142        -&self
143    }
144}
145
146impl<'a, 'b> Sub<&'b Fq> for &'a Fq {
147    type Output = Fq;
148
149    #[inline]
150    fn sub(self, rhs: &'b Fq) -> Fq {
151        self.sub(rhs)
152    }
153}
154
155impl<'a, 'b> Add<&'b Fq> for &'a Fq {
156    type Output = Fq;
157
158    #[inline]
159    fn add(self, rhs: &'b Fq) -> Fq {
160        self.add(rhs)
161    }
162}
163
164impl<'a, 'b> Mul<&'b Fq> for &'a Fq {
165    type Output = Fq;
166
167    #[inline]
168    fn mul(self, rhs: &'b Fq) -> Fq {
169        self.mul(rhs)
170    }
171}
172
173impl_binops_additive!(Fq, Fq);
174impl_binops_multiplicative!(Fq, Fq);
175
176impl<T: ::core::borrow::Borrow<Fq>> ::core::iter::Sum<T> for Fq {
177    fn sum<I: Iterator<Item = T>>(iter: I) -> Self {
178        iter.fold(Self::ZERO, |acc, item| acc + item.borrow())
179    }
180}
181
182impl<T: ::core::borrow::Borrow<Fq>> ::core::iter::Product<T> for Fq {
183    fn product<I: Iterator<Item = T>>(iter: I) -> Self {
184        iter.fold(Self::ONE, |acc, item| acc * item.borrow())
185    }
186}
187
188/// INV = -(q^{-1} mod 2^64) mod 2^64
189const INV: u64 = 0x8c46eb20ffffffff;
190
191/// R = 2^256 mod q
192const R: Fq = Fq([
193    0x5b2b3e9cfffffffd,
194    0x992c350be3420567,
195    0xffffffffffffffff,
196    0x3fffffffffffffff,
197]);
198
199/// R^2 = 2^512 mod q
200const R2: Fq = Fq([
201    0xfc9678ff0000000f,
202    0x67bb433d891a16e3,
203    0x7fae231004ccf590,
204    0x096d41af7ccfdaa9,
205]);
206
207/// R^3 = 2^768 mod q
208const R3: Fq = Fq([
209    0x008b421c249dae4c,
210    0xe13bda50dba41326,
211    0x88fececb8e15cb63,
212    0x07dd97a06e6792c8,
213]);
214
215/// `GENERATOR = 5 mod q` is a generator of the `q - 1` order multiplicative
216/// subgroup, or in other words a primitive root of the field.
217const GENERATOR: Fq = Fq::from_raw([
218    0x0000_0000_0000_0005,
219    0x0000_0000_0000_0000,
220    0x0000_0000_0000_0000,
221    0x0000_0000_0000_0000,
222]);
223
224const S: u32 = 32;
225
226/// GENERATOR^t where t * 2^s + 1 = q
227/// with t odd. In other words, this
228/// is a 2^s root of unity.
229const ROOT_OF_UNITY: Fq = Fq::from_raw([
230    0xa70e2c1102b6d05f,
231    0x9bb97ea3c106f049,
232    0x9e5c4dfd492ae26e,
233    0x2de6a9b8746d3f58,
234]);
235
236/// GENERATOR^{2^s} where t * 2^s + 1 = q
237/// with t odd. In other words, this
238/// is a t root of unity.
239const DELTA: Fq = Fq::from_raw([
240    0x8494392472d1683c,
241    0xe3ac3376541d1140,
242    0x06f0a88e7f7949f8,
243    0x2237d54423724166,
244]);
245
246/// `(t - 1) // 2` where t * 2^s + 1 = p with t odd.
247#[cfg(any(test, not(feature = "sqrt-table")))]
248const T_MINUS1_OVER2: [u64; 4] = [
249    0x04ca_546e_c623_7590,
250    0x0000_0000_1123_4c7e,
251    0x0000_0000_0000_0000,
252    0x0000_0000_2000_0000,
253];
254
255impl Default for Fq {
256    #[inline]
257    fn default() -> Self {
258        Self::zero()
259    }
260}
261
262impl Fq {
263    /// Returns zero, the additive identity.
264    #[inline]
265    pub const fn zero() -> Fq {
266        Fq([0, 0, 0, 0])
267    }
268
269    /// Returns one, the multiplicative identity.
270    #[inline]
271    pub const fn one() -> Fq {
272        R
273    }
274
275    /// Doubles this field element.
276    #[inline]
277    pub const fn double(&self) -> Fq {
278        // TODO: This can be achieved more efficiently with a bitshift.
279        self.add(self)
280    }
281
282    fn from_u512(limbs: [u64; 8]) -> Fq {
283        // We reduce an arbitrary 512-bit number by decomposing it into two 256-bit digits
284        // with the higher bits multiplied by 2^256. Thus, we perform two reductions
285        //
286        // 1. the lower bits are multiplied by R^2, as normal
287        // 2. the upper bits are multiplied by R^2 * 2^256 = R^3
288        //
289        // and computing their sum in the field. It remains to see that arbitrary 256-bit
290        // numbers can be placed into Montgomery form safely using the reduction. The
291        // reduction works so long as the product is less than R=2^256 multiplied by
292        // the modulus. This holds because for any `c` smaller than the modulus, we have
293        // that (2^256 - 1)*c is an acceptable product for the reduction. Therefore, the
294        // reduction always works so long as `c` is in the field; in this case it is either the
295        // constant `R2` or `R3`.
296        let d0 = Fq([limbs[0], limbs[1], limbs[2], limbs[3]]);
297        let d1 = Fq([limbs[4], limbs[5], limbs[6], limbs[7]]);
298        // Convert to Montgomery form
299        d0 * R2 + d1 * R3
300    }
301
302    /// Converts from an integer represented in little endian
303    /// into its (congruent) `Fq` representation.
304    pub const fn from_raw(val: [u64; 4]) -> Self {
305        (&Fq(val)).mul(&R2)
306    }
307
308    /// Squares this element.
309    #[cfg_attr(not(feature = "uninline-portable"), inline)]
310    pub const fn square(&self) -> Fq {
311        let (r1, carry) = mac(0, self.0[0], self.0[1], 0);
312        let (r2, carry) = mac(0, self.0[0], self.0[2], carry);
313        let (r3, r4) = mac(0, self.0[0], self.0[3], carry);
314
315        let (r3, carry) = mac(r3, self.0[1], self.0[2], 0);
316        let (r4, r5) = mac(r4, self.0[1], self.0[3], carry);
317
318        let (r5, r6) = mac(r5, self.0[2], self.0[3], 0);
319
320        let r7 = r6 >> 63;
321        let r6 = (r6 << 1) | (r5 >> 63);
322        let r5 = (r5 << 1) | (r4 >> 63);
323        let r4 = (r4 << 1) | (r3 >> 63);
324        let r3 = (r3 << 1) | (r2 >> 63);
325        let r2 = (r2 << 1) | (r1 >> 63);
326        let r1 = r1 << 1;
327
328        let (r0, carry) = mac(0, self.0[0], self.0[0], 0);
329        let (r1, carry) = adc(0, r1, carry);
330        let (r2, carry) = mac(r2, self.0[1], self.0[1], carry);
331        let (r3, carry) = adc(0, r3, carry);
332        let (r4, carry) = mac(r4, self.0[2], self.0[2], carry);
333        let (r5, carry) = adc(0, r5, carry);
334        let (r6, carry) = mac(r6, self.0[3], self.0[3], carry);
335        let (r7, _) = adc(0, r7, carry);
336
337        Fq::montgomery_reduce(r0, r1, r2, r3, r4, r5, r6, r7)
338    }
339
340    #[allow(clippy::too_many_arguments)]
341    #[cfg_attr(not(feature = "uninline-portable"), inline(always))]
342    const fn montgomery_reduce(
343        r0: u64,
344        r1: u64,
345        r2: u64,
346        r3: u64,
347        r4: u64,
348        r5: u64,
349        r6: u64,
350        r7: u64,
351    ) -> Self {
352        // The Montgomery reduction here is based on Algorithm 14.32 in
353        // Handbook of Applied Cryptography
354        // <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>.
355
356        let k = r0.wrapping_mul(INV);
357        let (_, carry) = mac(r0, k, MODULUS.0[0], 0);
358        let (r1, carry) = mac(r1, k, MODULUS.0[1], carry);
359        let (r2, carry) = mac(r2, k, MODULUS.0[2], carry);
360        let (r3, carry) = mac(r3, k, MODULUS.0[3], carry);
361        let (r4, carry2) = adc(r4, 0, carry);
362
363        let k = r1.wrapping_mul(INV);
364        let (_, carry) = mac(r1, k, MODULUS.0[0], 0);
365        let (r2, carry) = mac(r2, k, MODULUS.0[1], carry);
366        let (r3, carry) = mac(r3, k, MODULUS.0[2], carry);
367        let (r4, carry) = mac(r4, k, MODULUS.0[3], carry);
368        let (r5, carry2) = adc(r5, carry2, carry);
369
370        let k = r2.wrapping_mul(INV);
371        let (_, carry) = mac(r2, k, MODULUS.0[0], 0);
372        let (r3, carry) = mac(r3, k, MODULUS.0[1], carry);
373        let (r4, carry) = mac(r4, k, MODULUS.0[2], carry);
374        let (r5, carry) = mac(r5, k, MODULUS.0[3], carry);
375        let (r6, carry2) = adc(r6, carry2, carry);
376
377        let k = r3.wrapping_mul(INV);
378        let (_, carry) = mac(r3, k, MODULUS.0[0], 0);
379        let (r4, carry) = mac(r4, k, MODULUS.0[1], carry);
380        let (r5, carry) = mac(r5, k, MODULUS.0[2], carry);
381        let (r6, carry) = mac(r6, k, MODULUS.0[3], carry);
382        let (r7, _) = adc(r7, carry2, carry);
383
384        // Result may be within MODULUS of the correct value
385        (&Fq([r4, r5, r6, r7])).sub(&MODULUS)
386    }
387
388    /// Multiplies `rhs` by `self`, returning the result.
389    #[cfg_attr(not(feature = "uninline-portable"), inline)]
390    pub const fn mul(&self, rhs: &Self) -> Self {
391        // Schoolbook multiplication
392
393        let (r0, carry) = mac(0, self.0[0], rhs.0[0], 0);
394        let (r1, carry) = mac(0, self.0[0], rhs.0[1], carry);
395        let (r2, carry) = mac(0, self.0[0], rhs.0[2], carry);
396        let (r3, r4) = mac(0, self.0[0], rhs.0[3], carry);
397
398        let (r1, carry) = mac(r1, self.0[1], rhs.0[0], 0);
399        let (r2, carry) = mac(r2, self.0[1], rhs.0[1], carry);
400        let (r3, carry) = mac(r3, self.0[1], rhs.0[2], carry);
401        let (r4, r5) = mac(r4, self.0[1], rhs.0[3], carry);
402
403        let (r2, carry) = mac(r2, self.0[2], rhs.0[0], 0);
404        let (r3, carry) = mac(r3, self.0[2], rhs.0[1], carry);
405        let (r4, carry) = mac(r4, self.0[2], rhs.0[2], carry);
406        let (r5, r6) = mac(r5, self.0[2], rhs.0[3], carry);
407
408        let (r3, carry) = mac(r3, self.0[3], rhs.0[0], 0);
409        let (r4, carry) = mac(r4, self.0[3], rhs.0[1], carry);
410        let (r5, carry) = mac(r5, self.0[3], rhs.0[2], carry);
411        let (r6, r7) = mac(r6, self.0[3], rhs.0[3], carry);
412
413        Fq::montgomery_reduce(r0, r1, r2, r3, r4, r5, r6, r7)
414    }
415
416    /// Subtracts `rhs` from `self`, returning the result.
417    #[cfg_attr(not(feature = "uninline-portable"), inline)]
418    pub const fn sub(&self, rhs: &Self) -> Self {
419        let (d0, borrow) = sbb(self.0[0], rhs.0[0], 0);
420        let (d1, borrow) = sbb(self.0[1], rhs.0[1], borrow);
421        let (d2, borrow) = sbb(self.0[2], rhs.0[2], borrow);
422        let (d3, borrow) = sbb(self.0[3], rhs.0[3], borrow);
423
424        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
425        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
426        let (d0, carry) = adc(d0, MODULUS.0[0] & borrow, 0);
427        let (d1, carry) = adc(d1, MODULUS.0[1] & borrow, carry);
428        let (d2, carry) = adc(d2, MODULUS.0[2] & borrow, carry);
429        let (d3, _) = adc(d3, MODULUS.0[3] & borrow, carry);
430
431        Fq([d0, d1, d2, d3])
432    }
433
434    /// Adds `rhs` to `self`, returning the result.
435    #[cfg_attr(not(feature = "uninline-portable"), inline)]
436    pub const fn add(&self, rhs: &Self) -> Self {
437        let (d0, carry) = adc(self.0[0], rhs.0[0], 0);
438        let (d1, carry) = adc(self.0[1], rhs.0[1], carry);
439        let (d2, carry) = adc(self.0[2], rhs.0[2], carry);
440        let (d3, _) = adc(self.0[3], rhs.0[3], carry);
441
442        // Attempt to subtract the modulus, to ensure the value
443        // is smaller than the modulus.
444        (&Fq([d0, d1, d2, d3])).sub(&MODULUS)
445    }
446
447    /// Negates `self`.
448    #[cfg_attr(not(feature = "uninline-portable"), inline)]
449    pub const fn neg(&self) -> Self {
450        // Subtract `self` from `MODULUS` to negate. Ignore the final
451        // borrow because it cannot underflow; self is guaranteed to
452        // be in the field.
453        let (d0, borrow) = sbb(MODULUS.0[0], self.0[0], 0);
454        let (d1, borrow) = sbb(MODULUS.0[1], self.0[1], borrow);
455        let (d2, borrow) = sbb(MODULUS.0[2], self.0[2], borrow);
456        let (d3, _) = sbb(MODULUS.0[3], self.0[3], borrow);
457
458        // `tmp` could be `MODULUS` if `self` was zero. Create a mask that is
459        // zero if `self` was zero, and `u64::max_value()` if self was nonzero.
460        let mask = (((self.0[0] | self.0[1] | self.0[2] | self.0[3]) == 0) as u64).wrapping_sub(1);
461
462        Fq([d0 & mask, d1 & mask, d2 & mask, d3 & mask])
463    }
464}
465
466impl From<Fq> for [u8; 32] {
467    fn from(value: Fq) -> [u8; 32] {
468        value.to_repr()
469    }
470}
471
472impl<'a> From<&'a Fq> for [u8; 32] {
473    fn from(value: &'a Fq) -> [u8; 32] {
474        value.to_repr()
475    }
476}
477
478impl ff::Field for Fq {
479    const ZERO: Self = Self::zero();
480    const ONE: Self = Self::one();
481
482    fn random(mut rng: impl RngCore) -> Self {
483        Self::from_u512([
484            rng.next_u64(),
485            rng.next_u64(),
486            rng.next_u64(),
487            rng.next_u64(),
488            rng.next_u64(),
489            rng.next_u64(),
490            rng.next_u64(),
491            rng.next_u64(),
492        ])
493    }
494
495    fn double(&self) -> Self {
496        self.double()
497    }
498
499    #[inline(always)]
500    fn square(&self) -> Self {
501        self.square()
502    }
503
504    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
505        #[cfg(feature = "sqrt-table")]
506        {
507            FQ_TABLES.sqrt_ratio(num, div)
508        }
509
510        #[cfg(not(feature = "sqrt-table"))]
511        ff::helpers::sqrt_ratio_generic(num, div)
512    }
513
514    #[cfg(feature = "sqrt-table")]
515    fn sqrt_alt(&self) -> (Choice, Self) {
516        FQ_TABLES.sqrt_alt(self)
517    }
518
519    /// Computes the square root of this element, if it exists.
520    fn sqrt(&self) -> CtOption<Self> {
521        #[cfg(feature = "sqrt-table")]
522        {
523            let (is_square, res) = FQ_TABLES.sqrt_alt(self);
524            CtOption::new(res, is_square)
525        }
526
527        #[cfg(not(feature = "sqrt-table"))]
528        ff::helpers::sqrt_tonelli_shanks(self, &T_MINUS1_OVER2)
529    }
530
531    /// Computes the multiplicative inverse of this element,
532    /// failing if the element is zero.
533    fn invert(&self) -> CtOption<Self> {
534        let tmp = self.pow_vartime(&[
535            0x8c46eb20ffffffff,
536            0x224698fc0994a8dd,
537            0x0,
538            0x4000000000000000,
539        ]);
540
541        CtOption::new(tmp, !self.ct_eq(&Self::zero()))
542    }
543
544    fn pow_vartime<S: AsRef<[u64]>>(&self, exp: S) -> Self {
545        let mut res = Self::one();
546        let mut found_one = false;
547        for e in exp.as_ref().iter().rev() {
548            for i in (0..64).rev() {
549                if found_one {
550                    res = res.square();
551                }
552
553                if ((*e >> i) & 1) == 1 {
554                    found_one = true;
555                    res *= self;
556                }
557            }
558        }
559        res
560    }
561}
562
563impl ff::PrimeField for Fq {
564    type Repr = [u8; 32];
565
566    const MODULUS: &'static str =
567        "0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001";
568    const NUM_BITS: u32 = 255;
569    const CAPACITY: u32 = 254;
570    const TWO_INV: Self = Fq::from_raw([
571        0xc623759080000001,
572        0x11234c7e04ca546e,
573        0x0000000000000000,
574        0x2000000000000000,
575    ]);
576    const MULTIPLICATIVE_GENERATOR: Self = GENERATOR;
577    const S: u32 = S;
578    const ROOT_OF_UNITY: Self = ROOT_OF_UNITY;
579    const ROOT_OF_UNITY_INV: Self = Fq::from_raw([
580        0x57eecda0a84b6836,
581        0x4ad38b9084b8a80c,
582        0xf4c8f353124086c1,
583        0x2235e1a7415bf936,
584    ]);
585    const DELTA: Self = DELTA;
586
587    fn from_u128(v: u128) -> Self {
588        Fq::from_raw([v as u64, (v >> 64) as u64, 0, 0])
589    }
590
591    fn from_repr(repr: Self::Repr) -> CtOption<Self> {
592        let mut tmp = Fq([0, 0, 0, 0]);
593
594        tmp.0[0] = u64::from_le_bytes(repr[0..8].try_into().unwrap());
595        tmp.0[1] = u64::from_le_bytes(repr[8..16].try_into().unwrap());
596        tmp.0[2] = u64::from_le_bytes(repr[16..24].try_into().unwrap());
597        tmp.0[3] = u64::from_le_bytes(repr[24..32].try_into().unwrap());
598
599        // Try to subtract the modulus
600        let (_, borrow) = sbb(tmp.0[0], MODULUS.0[0], 0);
601        let (_, borrow) = sbb(tmp.0[1], MODULUS.0[1], borrow);
602        let (_, borrow) = sbb(tmp.0[2], MODULUS.0[2], borrow);
603        let (_, borrow) = sbb(tmp.0[3], MODULUS.0[3], borrow);
604
605        // If the element is smaller than MODULUS then the
606        // subtraction will underflow, producing a borrow value
607        // of 0xffff...ffff. Otherwise, it'll be zero.
608        let is_some = (borrow as u8) & 1;
609
610        // Convert to Montgomery form by computing
611        // (a.R^0 * R^2) / R = a.R
612        tmp *= &R2;
613
614        CtOption::new(tmp, Choice::from(is_some))
615    }
616
617    fn to_repr(&self) -> Self::Repr {
618        // Turn into canonical form by computing
619        // (a.R) / R = a
620        let tmp = Fq::montgomery_reduce(self.0[0], self.0[1], self.0[2], self.0[3], 0, 0, 0, 0);
621
622        let mut res = [0; 32];
623        res[0..8].copy_from_slice(&tmp.0[0].to_le_bytes());
624        res[8..16].copy_from_slice(&tmp.0[1].to_le_bytes());
625        res[16..24].copy_from_slice(&tmp.0[2].to_le_bytes());
626        res[24..32].copy_from_slice(&tmp.0[3].to_le_bytes());
627
628        res
629    }
630
631    fn is_odd(&self) -> Choice {
632        Choice::from(self.to_repr()[0] & 1)
633    }
634}
635
636#[cfg(all(feature = "bits", not(target_pointer_width = "64")))]
637type ReprBits = [u32; 8];
638
639#[cfg(all(feature = "bits", target_pointer_width = "64"))]
640type ReprBits = [u64; 4];
641
642#[cfg(feature = "bits")]
643impl PrimeFieldBits for Fq {
644    type ReprBits = ReprBits;
645
646    fn to_le_bits(&self) -> FieldBits<Self::ReprBits> {
647        let bytes = self.to_repr();
648
649        #[cfg(not(target_pointer_width = "64"))]
650        let limbs = [
651            u32::from_le_bytes(bytes[0..4].try_into().unwrap()),
652            u32::from_le_bytes(bytes[4..8].try_into().unwrap()),
653            u32::from_le_bytes(bytes[8..12].try_into().unwrap()),
654            u32::from_le_bytes(bytes[12..16].try_into().unwrap()),
655            u32::from_le_bytes(bytes[16..20].try_into().unwrap()),
656            u32::from_le_bytes(bytes[20..24].try_into().unwrap()),
657            u32::from_le_bytes(bytes[24..28].try_into().unwrap()),
658            u32::from_le_bytes(bytes[28..32].try_into().unwrap()),
659        ];
660
661        #[cfg(target_pointer_width = "64")]
662        let limbs = [
663            u64::from_le_bytes(bytes[0..8].try_into().unwrap()),
664            u64::from_le_bytes(bytes[8..16].try_into().unwrap()),
665            u64::from_le_bytes(bytes[16..24].try_into().unwrap()),
666            u64::from_le_bytes(bytes[24..32].try_into().unwrap()),
667        ];
668
669        FieldBits::new(limbs)
670    }
671
672    fn char_le_bits() -> FieldBits<Self::ReprBits> {
673        #[cfg(not(target_pointer_width = "64"))]
674        {
675            FieldBits::new(MODULUS_LIMBS_32)
676        }
677
678        #[cfg(target_pointer_width = "64")]
679        FieldBits::new(MODULUS.0)
680    }
681}
682
683#[cfg(feature = "sqrt-table")]
684lazy_static! {
685    // The perfect hash parameters are found by `squareroottab.sage` in zcash/pasta.
686    #[cfg_attr(docsrs, doc(cfg(feature = "sqrt-table")))]
687    static ref FQ_TABLES: SqrtTables<Fq> = SqrtTables::new(0x116A9E, 1206);
688}
689
690impl SqrtTableHelpers for Fq {
691    fn pow_by_t_minus1_over2(&self) -> Self {
692        let sqr = |x: Fq, i: u32| (0..i).fold(x, |x, _| x.square());
693
694        let s10 = self.square();
695        let s11 = s10 * self;
696        let s111 = s11.square() * self;
697        let s1001 = s111 * s10;
698        let s1011 = s1001 * s10;
699        let s1101 = s1011 * s10;
700        let sa = sqr(*self, 129) * self;
701        let sb = sqr(sa, 7) * s1001;
702        let sc = sqr(sb, 7) * s1101;
703        let sd = sqr(sc, 4) * s11;
704        let se = sqr(sd, 6) * s111;
705        let sf = sqr(se, 3) * s111;
706        let sg = sqr(sf, 10) * s1001;
707        let sh = sqr(sg, 4) * s1001;
708        let si = sqr(sh, 5) * s1001;
709        let sj = sqr(si, 5) * s1001;
710        let sk = sqr(sj, 3) * s1001;
711        let sl = sqr(sk, 4) * s1011;
712        let sm = sqr(sl, 4) * s1011;
713        let sn = sqr(sm, 5) * s11;
714        let so = sqr(sn, 4) * self;
715        let sp = sqr(so, 5) * s11;
716        let sq = sqr(sp, 4) * s111;
717        let sr = sqr(sq, 5) * s1011;
718        let ss = sqr(sr, 3) * self;
719        sqr(ss, 4) // st
720    }
721
722    fn get_lower_32(&self) -> u32 {
723        // TODO: don't reduce, just hash the Montgomery form. (Requires rebuilding perfect hash table.)
724        let tmp = Fq::montgomery_reduce(self.0[0], self.0[1], self.0[2], self.0[3], 0, 0, 0, 0);
725
726        tmp.0[0] as u32
727    }
728}
729
730impl WithSmallOrderMulGroup<3> for Fq {
731    const ZETA: Self = Fq::from_raw([
732        0x2aa9d2e050aa0e4f,
733        0x0fed467d47c033af,
734        0x511db4d81cf70f5a,
735        0x06819a58283e528e,
736    ]);
737}
738
739impl FromUniformBytes<64> for Fq {
740    /// Converts a 512-bit little endian integer into
741    /// a `Fq` by reducing by the modulus.
742    fn from_uniform_bytes(bytes: &[u8; 64]) -> Fq {
743        Fq::from_u512([
744            u64::from_le_bytes(bytes[0..8].try_into().unwrap()),
745            u64::from_le_bytes(bytes[8..16].try_into().unwrap()),
746            u64::from_le_bytes(bytes[16..24].try_into().unwrap()),
747            u64::from_le_bytes(bytes[24..32].try_into().unwrap()),
748            u64::from_le_bytes(bytes[32..40].try_into().unwrap()),
749            u64::from_le_bytes(bytes[40..48].try_into().unwrap()),
750            u64::from_le_bytes(bytes[48..56].try_into().unwrap()),
751            u64::from_le_bytes(bytes[56..64].try_into().unwrap()),
752        ])
753    }
754}
755
756#[cfg(feature = "gpu")]
757impl ec_gpu::GpuName for Fq {
758    fn name() -> alloc::string::String {
759        ec_gpu::name!()
760    }
761}
762
763#[cfg(feature = "gpu")]
764impl ec_gpu::GpuField for Fq {
765    fn one() -> alloc::vec::Vec<u32> {
766        crate::fields::u64_to_u32(&R.0[..])
767    }
768
769    fn r2() -> alloc::vec::Vec<u32> {
770        crate::fields::u64_to_u32(&R2.0[..])
771    }
772
773    fn modulus() -> alloc::vec::Vec<u32> {
774        crate::fields::u64_to_u32(&MODULUS.0[..])
775    }
776}
777
778#[test]
779fn test_inv() {
780    // Compute -(r^{-1} mod 2^64) mod 2^64 by exponentiating
781    // by totient(2**64) - 1
782
783    let mut inv = 1u64;
784    for _ in 0..63 {
785        inv = inv.wrapping_mul(inv);
786        inv = inv.wrapping_mul(MODULUS.0[0]);
787    }
788    inv = inv.wrapping_neg();
789
790    assert_eq!(inv, INV);
791}
792
793#[test]
794fn test_sqrt() {
795    // NB: TWO_INV is standing in as a "random" field element
796    let v = (Fq::TWO_INV).square().sqrt().unwrap();
797    assert!(v == Fq::TWO_INV || (-v) == Fq::TWO_INV);
798}
799
800#[test]
801fn test_sqrt_32bit_overflow() {
802    assert!((Fq::from(5)).sqrt().is_none().unwrap_u8() == 1);
803}
804
805#[test]
806fn test_pow_by_t_minus1_over2() {
807    // NB: TWO_INV is standing in as a "random" field element
808    let v = (Fq::TWO_INV).pow_by_t_minus1_over2();
809    assert!(v == ff::Field::pow_vartime(&Fq::TWO_INV, &T_MINUS1_OVER2));
810}
811
812#[test]
813fn test_sqrt_ratio_and_alt() {
814    // (true, sqrt(num/div)), if num and div are nonzero and num/div is a square in the field
815    let num = (Fq::TWO_INV).square();
816    let div = Fq::from(25);
817    let div_inverse = div.invert().unwrap();
818    let expected = Fq::TWO_INV * Fq::from(5).invert().unwrap();
819    let (is_square, v) = Fq::sqrt_ratio(&num, &div);
820    assert!(bool::from(is_square));
821    assert!(v == expected || (-v) == expected);
822
823    let (is_square_alt, v_alt) = Fq::sqrt_alt(&(num * div_inverse));
824    assert!(bool::from(is_square_alt));
825    assert!(v_alt == v);
826
827    // (false, sqrt(ROOT_OF_UNITY * num/div)), if num and div are nonzero and num/div is a nonsquare in the field
828    let num = num * Fq::ROOT_OF_UNITY;
829    let expected = Fq::TWO_INV * Fq::ROOT_OF_UNITY * Fq::from(5).invert().unwrap();
830    let (is_square, v) = Fq::sqrt_ratio(&num, &div);
831    assert!(!bool::from(is_square));
832    assert!(v == expected || (-v) == expected);
833
834    let (is_square_alt, v_alt) = Fq::sqrt_alt(&(num * div_inverse));
835    assert!(!bool::from(is_square_alt));
836    assert!(v_alt == v);
837
838    // (true, 0), if num is zero
839    let num = Fq::zero();
840    let expected = Fq::zero();
841    let (is_square, v) = Fq::sqrt_ratio(&num, &div);
842    assert!(bool::from(is_square));
843    assert!(v == expected);
844
845    let (is_square_alt, v_alt) = Fq::sqrt_alt(&(num * div_inverse));
846    assert!(bool::from(is_square_alt));
847    assert!(v_alt == v);
848
849    // (false, 0), if num is nonzero and div is zero
850    let num = (Fq::TWO_INV).square();
851    let div = Fq::zero();
852    let expected = Fq::zero();
853    let (is_square, v) = Fq::sqrt_ratio(&num, &div);
854    assert!(!bool::from(is_square));
855    assert!(v == expected);
856}
857
858#[test]
859fn test_zeta() {
860    assert_eq!(
861        format!("{:?}", Fq::ZETA),
862        "0x06819a58283e528e511db4d81cf70f5a0fed467d47c033af2aa9d2e050aa0e4f"
863    );
864    let a = Fq::ZETA;
865    assert!(a != Fq::one());
866    let b = a * a;
867    assert!(b != Fq::one());
868    let c = b * a;
869    assert!(c == Fq::one());
870}
871
872#[test]
873fn test_root_of_unity() {
874    assert_eq!(
875        Fq::ROOT_OF_UNITY.pow_vartime(&[1 << Fq::S, 0, 0, 0]),
876        Fq::one()
877    );
878}
879
880#[test]
881fn test_inv_root_of_unity() {
882    assert_eq!(Fq::ROOT_OF_UNITY_INV, Fq::ROOT_OF_UNITY.invert().unwrap());
883}
884
885#[test]
886fn test_inv_2() {
887    assert_eq!(Fq::TWO_INV, Fq::from(2).invert().unwrap());
888}
889
890#[test]
891fn test_delta() {
892    assert_eq!(Fq::DELTA, GENERATOR.pow(&[1u64 << Fq::S, 0, 0, 0]));
893    assert_eq!(
894        Fq::DELTA,
895        Fq::MULTIPLICATIVE_GENERATOR.pow(&[1u64 << Fq::S, 0, 0, 0])
896    );
897}
898
899#[cfg(not(target_pointer_width = "64"))]
900#[test]
901fn consistent_modulus_limbs() {
902    for (a, &b) in MODULUS
903        .0
904        .iter()
905        .flat_map(|&limb| {
906            Some(limb as u32)
907                .into_iter()
908                .chain(Some((limb >> 32) as u32))
909        })
910        .zip(MODULUS_LIMBS_32.iter())
911    {
912        assert_eq!(a, b);
913    }
914}
915
916#[test]
917fn test_from_u512() {
918    assert_eq!(
919        Fq::from_raw([
920            0xe22bd0d1b22cc43e,
921            0x6b84e5b52490a7c8,
922            0x264262941ac9e229,
923            0x27dcfdf361ce4254
924        ]),
925        Fq::from_u512([
926            0x64a80cce0b5a2369,
927            0x84f2ef0501bc783c,
928            0x696e5e63c86bbbde,
929            0x924072f52dc6cc62,
930            0x8288a507c8d61128,
931            0x3b2efb1ef697e3fe,
932            0x75a4998d06855f27,
933            0x52ea589e69712cc0
934        ])
935    );
936}
pasta_curves/fields/fq.rs

pasta_curves/fields/
fq.rs
