substrate_bn/fields/
fq2.rs

Help
1use core::ops::{Add, Mul, Neg, Sub};
2use rand::Rng;
3use crate::fields::{const_fq, FieldElement, Fq};
4use crate::arith::{U256, U512};
5
6#[inline]
7fn fq_non_residue() -> Fq {
8    // (q - 1) is a quadratic nonresidue in Fq
9    // 21888242871839275222246405745257275088696311157297823662689037894645226208582
10    const_fq([
11        0x68c3488912edefaa,
12        0x8d087f6872aabf4f,
13        0x51e1a24709081231,
14        0x2259d6b14729c0fa,
15    ])
16}
17
18#[inline]
19pub fn fq2_nonresidue() -> Fq2 {
20    Fq2::new(
21        const_fq([
22            0xf60647ce410d7ff7,
23            0x2f3d6f4dd31bd011,
24            0x2943337e3940c6d1,
25            0x1d9598e8a7e39857,
26        ]),
27        const_fq([
28            0xd35d438dc58f0d9d,
29            0x0a78eb28f5c70b3d,
30            0x666ea36f7879462c,
31            0x0e0a77c19a07df2f,
32        ]),
33    )
34}
35
36#[derive(Copy, Clone, Debug, PartialEq, Eq)]
37#[repr(C)]
38pub struct Fq2 {
39    c0: Fq,
40    c1: Fq,
41}
42
43impl Fq2 {
44    pub fn new(c0: Fq, c1: Fq) -> Self {
45        Fq2 { c0: c0, c1: c1 }
46    }
47
48    pub fn scale(&self, by: Fq) -> Self {
49        Fq2 {
50            c0: self.c0 * by,
51            c1: self.c1 * by,
52        }
53    }
54
55    pub fn mul_by_nonresidue(&self) -> Self {
56        *self * fq2_nonresidue()
57    }
58
59    pub fn frobenius_map(&self, power: usize) -> Self {
60        if power % 2 == 0 {
61            *self
62        } else {
63            Fq2 {
64                c0: self.c0,
65                c1: self.c1 * fq_non_residue(),
66            }
67        }
68    }
69
70    pub fn real(&self) -> &Fq {
71        &self.c0
72    }
73
74    pub fn imaginary(&self) -> &Fq {
75        &self.c1
76    }
77}
78
79impl FieldElement for Fq2 {
80    fn zero() -> Self {
81        Fq2 {
82            c0: Fq::zero(),
83            c1: Fq::zero(),
84        }
85    }
86
87    fn one() -> Self {
88        Fq2 {
89            c0: Fq::one(),
90            c1: Fq::zero(),
91        }
92    }
93
94    fn random<R: Rng>(rng: &mut R) -> Self {
95        Fq2 {
96            c0: Fq::random(rng),
97            c1: Fq::random(rng),
98        }
99    }
100
101    fn is_zero(&self) -> bool {
102        self.c0.is_zero() && self.c1.is_zero()
103    }
104
105    fn squared(&self) -> Self {
106        // Devegili OhEig Scott Dahab
107        //     Multiplication and Squaring on Pairing-Friendly Fields.pdf
108        //     Section 3 (Complex squaring)
109
110        let ab = self.c0 * self.c1;
111
112        Fq2 {
113            c0: (self.c1 * fq_non_residue() + self.c0) * (self.c0 + self.c1) - ab
114                - ab * fq_non_residue(),
115            c1: ab + ab,
116        }
117    }
118
119    fn inverse(self) -> Option<Self> {
120        // "High-Speed Software Implementation of the Optimal Ate Pairing
121        // over Barreto–Naehrig Curves"; Algorithm 8
122
123        match (self.c0.squared() - (self.c1.squared() * fq_non_residue())).inverse() {
124            Some(t) => Some(Fq2 {
125                c0: self.c0 * t,
126                c1: -(self.c1 * t),
127            }),
128            None => None,
129        }
130    }
131}
132
133impl Mul for Fq2 {
134    type Output = Fq2;
135
136    fn mul(self, other: Fq2) -> Fq2 {
137        // Devegili OhEig Scott Dahab
138        //     Multiplication and Squaring on Pairing-Friendly Fields.pdf
139        //     Section 3 (Karatsuba)
140
141        let aa = self.c0 * other.c0;
142        let bb = self.c1 * other.c1;
143
144        Fq2 {
145            c0: bb * fq_non_residue() + aa,
146            c1: (self.c0 + self.c1) * (other.c0 + other.c1) - aa - bb,
147        }
148    }
149}
150
151impl Sub for Fq2 {
152    type Output = Fq2;
153
154    fn sub(self, other: Fq2) -> Fq2 {
155        Fq2 {
156            c0: self.c0 - other.c0,
157            c1: self.c1 - other.c1,
158        }
159    }
160}
161
162impl Add for Fq2 {
163    type Output = Fq2;
164
165    fn add(self, other: Fq2) -> Fq2 {
166        Fq2 {
167            c0: self.c0 + other.c0,
168            c1: self.c1 + other.c1,
169        }
170    }
171}
172
173impl Neg for Fq2 {
174    type Output = Fq2;
175
176    fn neg(self) -> Fq2 {
177        Fq2 {
178            c0: -self.c0,
179            c1: -self.c1,
180        }
181    }
182}
183
184lazy_static::lazy_static! {
185    static ref FQ: U256 = U256::from([
186        0x3c208c16d87cfd47,
187        0x97816a916871ca8d,
188        0xb85045b68181585d,
189        0x30644e72e131a029
190    ]);
191
192    static ref FQ_MINUS3_DIV4: Fq =
193        Fq::new(3.into()).expect("3 is a valid field element and static; qed").neg() *
194        Fq::new(4.into()).expect("4 is a valid field element and static; qed").inverse()
195        .expect("4 has inverse in Fq and is static; qed");
196
197    static ref FQ_MINUS1_DIV2: Fq =
198        Fq::new(1.into()).expect("1 is a valid field element and static; qed").neg() *
199        Fq::new(2.into()).expect("2 is a valid field element and static; qed").inverse()
200            .expect("2 has inverse in Fq and is static; qed");
201}
202
203impl Fq2 {
204    pub fn i() -> Fq2 {
205        Fq2::new(Fq::zero(), Fq::one())
206    }
207
208    pub fn sqrt(&self) -> Option<Self> {
209        let a1 = self.pow::<U256>((*FQ_MINUS3_DIV4).into());
210        let a1a = a1 * *self;
211        let alpha = a1 * a1a;
212        let a0 = alpha.pow(*FQ) * alpha;
213
214        if a0 == Fq2::one().neg() {
215            return None;
216        }
217
218        if alpha == Fq2::one().neg() {
219            Some(Self::i() * a1a)
220        } else {
221            let b = (alpha + Fq2::one()).pow::<U256>((*FQ_MINUS1_DIV2).into());
222            Some(b * a1a)
223        }
224    }
225
226    pub fn to_u512(&self) -> U512 {
227        let c0: U256 = (*self.real()).into();
228        let c1: U256 = (*self.imaginary()).into();
229
230        U512::new(&c1, &c0, &FQ)
231    }
232}
233
234
235#[test]
236fn sqrt_fq2() {
237    // from zcash test_proof.cpp
238    let x1 = Fq2::new(
239        Fq::from_str("12844195307879678418043983815760255909500142247603239203345049921980497041944").unwrap(),
240        Fq::from_str("7476417578426924565731404322659619974551724117137577781074613937423560117731").unwrap(),
241    );
242
243    let x2 = Fq2::new(
244        Fq::from_str("3345897230485723946872934576923485762803457692345760237495682347502347589474").unwrap(),
245        Fq::from_str("1234912378405347958234756902345768290345762348957605678245967234857634857676").unwrap(),
246    );
247
248    assert_eq!(x2.sqrt().unwrap(), x1);
249
250    // i is sqrt(-1)
251    assert_eq!(
252        Fq2::one().neg().sqrt().unwrap(),
253        Fq2::i(),
254    );
255
256    // no sqrt for (1 + 2i)
257    assert!(
258        Fq2::new(Fq::from_str("1").unwrap(), Fq::from_str("2").unwrap()).sqrt().is_none()
259    );
260}
substrate_bn/fields/fq2.rs

substrate_bn/fields/
fq2.rs
