ark_ff/fields/models/
fp12_2over3over2.rs

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

ark_ff/fields/models/
fp12_2over3over2.rs
