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

ark_ff/fields/models/
fp12_2over3over2.rs
