ark_r1cs_std/fields/
fp12.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
use crate::fields::{fp2::Fp2Var, fp6_3over2::Fp6Var, quadratic_extension::*, FieldVar};
use ark_ff::{
    fields::{fp12_2over3over2::*, Field},
    fp6_3over2::Fp6Config,
    QuadExtConfig,
};
use ark_relations::r1cs::SynthesisError;

/// A degree-12 extension field constructed as the tower of a
/// quadratic extension over a cubic extension over a quadratic extension field.
/// This is the R1CS equivalent of `ark_ff::fp12_2over3over2::Fp12<P>`.
pub type Fp12Var<P> = QuadExtVar<Fp6Var<<P as Fp12Config>::Fp6Config>, Fp12ConfigWrapper<P>>;

type Fp2Config<P> = <<P as Fp12Config>::Fp6Config as Fp6Config>::Fp2Config;

impl<P: Fp12Config> QuadExtVarConfig<Fp6Var<P::Fp6Config>> for Fp12ConfigWrapper<P> {
    fn mul_base_field_var_by_frob_coeff(fe: &mut Fp6Var<P::Fp6Config>, power: usize) {
        fe.c0 *= Self::FROBENIUS_COEFF_C1[power % Self::DEGREE_OVER_BASE_PRIME_FIELD];
        fe.c1 *= Self::FROBENIUS_COEFF_C1[power % Self::DEGREE_OVER_BASE_PRIME_FIELD];
        fe.c2 *= Self::FROBENIUS_COEFF_C1[power % Self::DEGREE_OVER_BASE_PRIME_FIELD];
    }
}

impl<P: Fp12Config> Fp12Var<P> {
    /// Multiplies by a sparse element of the form `(c0 = (c0, c1, 0), c1 = (0,
    /// d1, 0))`.
    #[inline]
    pub fn mul_by_014(
        &self,
        c0: &Fp2Var<Fp2Config<P>>,
        c1: &Fp2Var<Fp2Config<P>>,
        d1: &Fp2Var<Fp2Config<P>>,
    ) -> Result<Self, SynthesisError> {
        let v0 = self.c0.mul_by_c0_c1_0(&c0, &c1)?;
        let v1 = self.c1.mul_by_0_c1_0(&d1)?;
        let new_c0 = Self::mul_base_field_by_nonresidue(&v1)? + &v0;

        let new_c1 = (&self.c0 + &self.c1).mul_by_c0_c1_0(&c0, &(c1 + d1))? - &v0 - &v1;
        Ok(Self::new(new_c0, new_c1))
    }

    /// Multiplies by a sparse element of the form `(c0 = (c0, 0, 0), c1 = (d0,
    /// d1, 0))`.
    #[inline]
    pub fn mul_by_034(
        &self,
        c0: &Fp2Var<Fp2Config<P>>,
        d0: &Fp2Var<Fp2Config<P>>,
        d1: &Fp2Var<Fp2Config<P>>,
    ) -> Result<Self, SynthesisError> {
        let a0 = &self.c0.c0 * c0;
        let a1 = &self.c0.c1 * c0;
        let a2 = &self.c0.c2 * c0;
        let a = Fp6Var::new(a0, a1, a2);
        let b = self.c1.mul_by_c0_c1_0(&d0, &d1)?;

        let c0 = c0 + d0;
        let c1 = d1;
        let e = (&self.c0 + &self.c1).mul_by_c0_c1_0(&c0, &c1)?;
        let new_c1 = e - (&a + &b);
        let new_c0 = Self::mul_base_field_by_nonresidue(&b)? + &a;

        Ok(Self::new(new_c0, new_c1))
    }

    /// Squares `self` when `self` is in the cyclotomic subgroup.
    pub fn cyclotomic_square(&self) -> Result<Self, SynthesisError> {
        if characteristic_square_mod_6_is_one(Fp12::<P>::characteristic()) {
            let fp2_nr = <P::Fp6Config as Fp6Config>::NONRESIDUE;

            let z0 = &self.c0.c0;
            let z4 = &self.c0.c1;
            let z3 = &self.c0.c2;
            let z2 = &self.c1.c0;
            let z1 = &self.c1.c1;
            let z5 = &self.c1.c2;

            // t0 + t1*y = (z0 + z1*y)^2 = a^2
            let tmp = z0 * z1;
            let t0 = {
                let tmp1 = z0 + z1;
                let tmp2 = z1 * fp2_nr + z0;
                let tmp4 = &tmp * fp2_nr + &tmp;
                tmp1 * tmp2 - tmp4
            };
            let t1 = tmp.double()?;

            // t2 + t3*y = (z2 + z3*y)^2 = b^2
            let tmp = z2 * z3;
            let t2 = {
                // (z2 + &z3) * &(z2 + &(fp2_nr * &z3)) - &tmp - &(tmp * &fp2_nr);
                let tmp1 = z2 + z3;
                let tmp2 = z3 * fp2_nr + z2;
                let tmp4 = &tmp * fp2_nr + &tmp;
                tmp1 * tmp2 - tmp4
            };
            let t3 = tmp.double()?;

            // t4 + t5*y = (z4 + z5*y)^2 = c^2
            let tmp = z4 * z5;
            let t4 = {
                // (z4 + &z5) * &(z4 + &(fp2_nr * &z5)) - &tmp - &(tmp * &fp2_nr);
                let tmp1 = z4 + z5;
                let tmp2 = (z5 * fp2_nr) + z4;
                let tmp4 = (&tmp * fp2_nr) + &tmp;
                (tmp1 * tmp2) - tmp4
            };
            let t5 = tmp.double()?;

            // for A

            // z0 = 3 * t0 - 2 * z0
            let c0_c0 = (&t0 - z0).double()? + &t0;

            // z1 = 3 * t1 + 2 * z1
            let c1_c1 = (&t1 + z1).double()? + &t1;

            // for B

            // z2 = 3 * (xi * t5) + 2 * z2
            let c1_c0 = {
                let tmp = &t5 * fp2_nr;
                (z2 + &tmp).double()? + &tmp
            };

            // z3 = 3 * t4 - 2 * z3
            let c0_c2 = (&t4 - z3).double()? + &t4;

            // for C

            // z4 = 3 * t2 - 2 * z4
            let c0_c1 = (&t2 - z4).double()? + &t2;

            // z5 = 3 * t3 + 2 * z5
            let c1_c2 = (&t3 + z5).double()? + &t3;
            let c0 = Fp6Var::new(c0_c0, c0_c1, c0_c2);
            let c1 = Fp6Var::new(c1_c0, c1_c1, c1_c2);

            Ok(Self::new(c0, c1))
        } else {
            self.square()
        }
    }

    /// Like `Self::cyclotomic_exp`, but additionally uses cyclotomic squaring.
    pub fn optimized_cyclotomic_exp(
        &self,
        exponent: impl AsRef<[u64]>,
    ) -> Result<Self, SynthesisError> {
        use ark_ff::biginteger::arithmetic::find_naf;
        let mut res = Self::one();
        let self_inverse = self.unitary_inverse()?;

        let mut found_nonzero = false;
        let naf = find_naf(exponent.as_ref());

        for &value in naf.iter().rev() {
            if found_nonzero {
                res = res.cyclotomic_square()?;
            }

            if value != 0 {
                found_nonzero = true;

                if value > 0 {
                    res *= self;
                } else {
                    res *= &self_inverse;
                }
            }
        }

        Ok(res)
    }
}