ark_ff/fields/models/
fp12_2over3over2.rs

1use ark_std::Zero;
2
3use super::quadratic_extension::*;
4use crate::{
5    fields::{fp6_3over2::*, Field, Fp2, Fp2Config as Fp2ConfigTrait},
6    CyclotomicMultSubgroup,
7};
8use core::{
9    marker::PhantomData,
10    ops::{AddAssign, Not, SubAssign},
11};
12
13type Fp2Config<P> = <<P as Fp12Config>::Fp6Config as Fp6Config>::Fp2Config;
14
15pub trait Fp12Config: 'static + Send + Sync + Copy {
16    type Fp6Config: Fp6Config;
17
18    /// This *must* equal (0, 1, 0);
19    /// see [[DESD06, Section 6.1]](https://eprint.iacr.org/2006/471.pdf).
20    const NONRESIDUE: Fp6<Self::Fp6Config>;
21
22    /// Coefficients for the Frobenius automorphism.
23    const FROBENIUS_COEFF_FP12_C1: &'static [Fp2<Fp2Config<Self>>];
24
25    /// Multiply by quadratic nonresidue v.
26    #[inline(always)]
27    fn mul_fp6_by_nonresidue_in_place(fe: &mut Fp6<Self::Fp6Config>) -> &mut Fp6<Self::Fp6Config> {
28        // see [[DESD06, Section 6.1]](https://eprint.iacr.org/2006/471.pdf).
29        let old_c1 = fe.c1;
30        fe.c1 = fe.c0;
31        fe.c0 = fe.c2;
32        Self::Fp6Config::mul_fp2_by_nonresidue_in_place(&mut fe.c0);
33        fe.c2 = old_c1;
34        fe
35    }
36}
37
38pub struct Fp12ConfigWrapper<P: Fp12Config>(PhantomData<P>);
39
40impl<P: Fp12Config> QuadExtConfig for Fp12ConfigWrapper<P> {
41    type BasePrimeField = <Fp2Config<P> as Fp2ConfigTrait>::Fp;
42    type BaseField = Fp6<P::Fp6Config>;
43    type FrobCoeff = Fp2<Fp2Config<P>>;
44
45    const DEGREE_OVER_BASE_PRIME_FIELD: usize = 12;
46
47    const NONRESIDUE: Self::BaseField = P::NONRESIDUE;
48
49    const FROBENIUS_COEFF_C1: &'static [Self::FrobCoeff] = P::FROBENIUS_COEFF_FP12_C1;
50
51    #[inline(always)]
52    fn mul_base_field_by_nonresidue_in_place(fe: &mut Self::BaseField) -> &mut Self::BaseField {
53        P::mul_fp6_by_nonresidue_in_place(fe)
54    }
55
56    fn mul_base_field_by_frob_coeff(fe: &mut Self::BaseField, power: usize) {
57        fe.mul_assign_by_fp2(Self::FROBENIUS_COEFF_C1[power % Self::DEGREE_OVER_BASE_PRIME_FIELD]);
58    }
59}
60
61pub type Fp12<P> = QuadExtField<Fp12ConfigWrapper<P>>;
62
63impl<P: Fp12Config> Fp12<P> {
64    pub fn mul_by_fp(&mut self, element: &<Self as Field>::BasePrimeField) {
65        self.c0.mul_by_fp(element);
66        self.c1.mul_by_fp(element);
67    }
68
69    pub fn mul_by_034(
70        &mut self,
71        c0: &Fp2<Fp2Config<P>>,
72        c3: &Fp2<Fp2Config<P>>,
73        c4: &Fp2<Fp2Config<P>>,
74    ) {
75        let a0 = self.c0.c0 * c0;
76        let a1 = self.c0.c1 * c0;
77        let a2 = self.c0.c2 * c0;
78        let a = Fp6::new(a0, a1, a2);
79        let mut b = self.c1;
80        b.mul_by_01(c3, c4);
81
82        let c0 = *c0 + c3;
83        let c1 = c4;
84        let mut e = self.c0 + &self.c1;
85        e.mul_by_01(&c0, c1);
86        self.c1 = e - &(a + &b);
87        self.c0 = b;
88        P::mul_fp6_by_nonresidue_in_place(&mut self.c0);
89        self.c0 += &a;
90    }
91
92    pub fn mul_by_014(
93        &mut self,
94        c0: &Fp2<Fp2Config<P>>,
95        c1: &Fp2<Fp2Config<P>>,
96        c4: &Fp2<Fp2Config<P>>,
97    ) {
98        let mut aa = self.c0;
99        aa.mul_by_01(c0, c1);
100        let mut bb = self.c1;
101        bb.mul_by_1(c4);
102        let mut o = *c1;
103        o.add_assign(c4);
104        self.c1.add_assign(&self.c0);
105        self.c1.mul_by_01(c0, &o);
106        self.c1.sub_assign(&aa);
107        self.c1.sub_assign(&bb);
108        self.c0 = bb;
109        P::mul_fp6_by_nonresidue_in_place(&mut self.c0);
110        self.c0.add_assign(&aa);
111    }
112}
113
114pub const fn characteristic_square_mod_6_is_one(characteristic: &[u64]) -> bool {
115    // char mod 6 = (a_0 + 2**64 * a_1 + ...) mod 6
116    //            = a_0 mod 6 + (2**64 * a_1 mod 6) + (...) mod 6
117    //            = a_0 mod 6 + (4 * a_1 mod 6) + (4 * ...) mod 6
118    let mut char_mod_6 = 0u64;
119    crate::const_for!((i in 0..(characteristic.len())) {
120        char_mod_6 += if i == 0 {
121            characteristic[i] % 6
122        } else {
123            (4 * (characteristic[i] % 6)) % 6
124        };
125    });
126    (char_mod_6 * char_mod_6) % 6 == 1
127}
128
129impl<P: Fp12Config> CyclotomicMultSubgroup for Fp12<P> {
130    const INVERSE_IS_FAST: bool = true;
131
132    fn cyclotomic_inverse_in_place(&mut self) -> Option<&mut Self> {
133        self.is_zero().not().then(|| self.conjugate_in_place())
134    }
135
136    fn cyclotomic_square_in_place(&mut self) -> &mut Self {
137        // Faster Squaring in the Cyclotomic Subgroup of Sixth Degree Extensions
138        // - Robert Granger and Michael Scott
139        //
140        if characteristic_square_mod_6_is_one(Self::characteristic()) {
141            let fp2_nr = <P::Fp6Config as Fp6Config>::mul_fp2_by_nonresidue;
142
143            let r0 = &self.c0.c0;
144            let r4 = &self.c0.c1;
145            let r3 = &self.c0.c2;
146            let r2 = &self.c1.c0;
147            let r1 = &self.c1.c1;
148            let r5 = &self.c1.c2;
149
150            // t0 + t1*y = (z0 + z1*y)^2 = a^2
151            let mut tmp = *r0 * r1;
152            let t0 = (*r0 + r1) * &(fp2_nr(*r1) + r0) - &tmp - &fp2_nr(tmp);
153            let t1 = tmp.double();
154
155            // t2 + t3*y = (z2 + z3*y)^2 = b^2
156            tmp = *r2 * r3;
157            let t2 = (*r2 + r3) * &(fp2_nr(*r3) + r2) - &tmp - &fp2_nr(tmp);
158            let t3 = tmp.double();
159
160            // t4 + t5*y = (z4 + z5*y)^2 = c^2
161            tmp = *r4 * r5;
162            let t4 = (*r4 + r5) * &(fp2_nr(*r5) + r4) - &tmp - &fp2_nr(tmp);
163            let t5 = tmp.double();
164
165            let z0 = &mut self.c0.c0;
166            let z4 = &mut self.c0.c1;
167            let z3 = &mut self.c0.c2;
168            let z2 = &mut self.c1.c0;
169            let z1 = &mut self.c1.c1;
170            let z5 = &mut self.c1.c2;
171
172            // for A
173
174            // z0 = 3 * t0 - 2 * z0
175            *z0 = t0 - &*z0;
176            z0.double_in_place();
177            *z0 += &t0;
178
179            // z1 = 3 * t1 + 2 * z1
180            *z1 = t1 + &*z1;
181            z1.double_in_place();
182            *z1 += &t1;
183
184            // for B
185
186            // z2 = 3 * (xi * t5) + 2 * z2
187            tmp = fp2_nr(t5);
188            *z2 += tmp;
189            z2.double_in_place();
190            *z2 += &tmp;
191
192            // z3 = 3 * t4 - 2 * z3
193            *z3 = t4 - &*z3;
194            z3.double_in_place();
195            *z3 += &t4;
196
197            // for C
198
199            // z4 = 3 * t2 - 2 * z4
200            *z4 = t2 - &*z4;
201            z4.double_in_place();
202            *z4 += &t2;
203
204            // z5 = 3 * t3 + 2 * z5
205            *z5 += t3;
206            z5.double_in_place();
207            *z5 += &t3;
208            self
209        } else {
210            self.square_in_place()
211        }
212    }
213}
214
215#[cfg(test)]
216mod test {
217    #[test]
218    fn test_characteristic_square_mod_6_is_one() {
219        use super::*;
220        assert!(!characteristic_square_mod_6_is_one(&[36]));
221        assert!(characteristic_square_mod_6_is_one(&[37]));
222        assert!(!characteristic_square_mod_6_is_one(&[38]));
223        assert!(!characteristic_square_mod_6_is_one(&[39]));
224        assert!(!characteristic_square_mod_6_is_one(&[40]));
225        assert!(characteristic_square_mod_6_is_one(&[41]));
226
227        assert!(!characteristic_square_mod_6_is_one(&[36, 36]));
228        assert!(!characteristic_square_mod_6_is_one(&[36, 37]));
229        assert!(!characteristic_square_mod_6_is_one(&[36, 38]));
230        assert!(!characteristic_square_mod_6_is_one(&[36, 39]));
231        assert!(!characteristic_square_mod_6_is_one(&[36, 40]));
232        assert!(!characteristic_square_mod_6_is_one(&[36, 41]));
233
234        assert!(!characteristic_square_mod_6_is_one(&[36, 41]));
235        assert!(!characteristic_square_mod_6_is_one(&[37, 41]));
236        assert!(!characteristic_square_mod_6_is_one(&[38, 41]));
237        assert!(characteristic_square_mod_6_is_one(&[39, 41]));
238        assert!(!characteristic_square_mod_6_is_one(&[40, 41]));
239        assert!(characteristic_square_mod_6_is_one(&[41, 41]));
240        assert!(characteristic_square_mod_6_is_one(&[1, u64::MAX]));
241    }
242}
ark_ff/fields/models/fp12_2over3over2.rs

ark_ff/fields/models/
fp12_2over3over2.rs
