plonky2_field/
secp256k1_scalar.rs

1use alloc::vec::Vec;
2use core::fmt::{self, Debug, Display, Formatter};
3use core::hash::{Hash, Hasher};
4use core::iter::{Product, Sum};
5use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
6
7use itertools::Itertools;
8use num::bigint::BigUint;
9use num::{Integer, One};
10use serde::{Deserialize, Serialize};
11
12use crate::types::{Field, PrimeField, Sample};
13
14/// The base field of the secp256k1 elliptic curve.
15///
16/// Its order is
17/// ```ignore
18/// P = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
19///   = 115792089237316195423570985008687907852837564279074904382605163141518161494337
20///   = 2**256 - 432420386565659656852420866394968145599
21/// ```
22#[derive(Copy, Clone, Serialize, Deserialize)]
23pub struct Secp256K1Scalar(pub [u64; 4]);
24
25fn biguint_from_array(arr: [u64; 4]) -> BigUint {
26    BigUint::from_slice(&[
27        arr[0] as u32,
28        (arr[0] >> 32) as u32,
29        arr[1] as u32,
30        (arr[1] >> 32) as u32,
31        arr[2] as u32,
32        (arr[2] >> 32) as u32,
33        arr[3] as u32,
34        (arr[3] >> 32) as u32,
35    ])
36}
37
38impl Default for Secp256K1Scalar {
39    fn default() -> Self {
40        Self::ZERO
41    }
42}
43
44impl PartialEq for Secp256K1Scalar {
45    fn eq(&self, other: &Self) -> bool {
46        self.to_canonical_biguint() == other.to_canonical_biguint()
47    }
48}
49
50impl Eq for Secp256K1Scalar {}
51
52impl Hash for Secp256K1Scalar {
53    fn hash<H: Hasher>(&self, state: &mut H) {
54        self.to_canonical_biguint().hash(state)
55    }
56}
57
58impl Display for Secp256K1Scalar {
59    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
60        Display::fmt(&self.to_canonical_biguint(), f)
61    }
62}
63
64impl Debug for Secp256K1Scalar {
65    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
66        Debug::fmt(&self.to_canonical_biguint(), f)
67    }
68}
69
70impl Sample for Secp256K1Scalar {
71    #[inline]
72    fn sample<R>(rng: &mut R) -> Self
73    where
74        R: rand::RngCore + ?Sized,
75    {
76        use num::bigint::RandBigInt;
77        Self::from_noncanonical_biguint(rng.gen_biguint_below(&Self::order()))
78    }
79}
80
81impl Field for Secp256K1Scalar {
82    const ZERO: Self = Self([0; 4]);
83    const ONE: Self = Self([1, 0, 0, 0]);
84    const TWO: Self = Self([2, 0, 0, 0]);
85    const NEG_ONE: Self = Self([
86        0xBFD25E8CD0364140,
87        0xBAAEDCE6AF48A03B,
88        0xFFFFFFFFFFFFFFFE,
89        0xFFFFFFFFFFFFFFFF,
90    ]);
91
92    const TWO_ADICITY: usize = 6;
93    const CHARACTERISTIC_TWO_ADICITY: usize = Self::TWO_ADICITY;
94
95    // Sage: `g = GF(p).multiplicative_generator()`
96    const MULTIPLICATIVE_GROUP_GENERATOR: Self = Self([7, 0, 0, 0]);
97
98    // Sage: `g_2 = power_mod(g, (p - 1) // 2^6), p)`
99    // 5480320495727936603795231718619559942670027629901634955707709633242980176626
100    const POWER_OF_TWO_GENERATOR: Self = Self([
101        0x992f4b5402b052f2,
102        0x98BDEAB680756045,
103        0xDF9879A3FBC483A8,
104        0xC1DC060E7A91986,
105    ]);
106
107    const BITS: usize = 256;
108
109    fn order() -> BigUint {
110        BigUint::from_slice(&[
111            0xD0364141, 0xBFD25E8C, 0xAF48A03B, 0xBAAEDCE6, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF,
112            0xFFFFFFFF,
113        ])
114    }
115    fn characteristic() -> BigUint {
116        Self::order()
117    }
118
119    fn try_inverse(&self) -> Option<Self> {
120        if self.is_zero() {
121            return None;
122        }
123
124        // Fermat's Little Theorem
125        Some(self.exp_biguint(&(Self::order() - BigUint::one() - BigUint::one())))
126    }
127
128    fn from_noncanonical_biguint(val: BigUint) -> Self {
129        Self(
130            val.to_u64_digits()
131                .into_iter()
132                .pad_using(4, |_| 0)
133                .collect::<Vec<_>>()[..]
134                .try_into()
135                .expect("error converting to u64 array"),
136        )
137    }
138
139    #[inline]
140    fn from_canonical_u64(n: u64) -> Self {
141        Self([n, 0, 0, 0])
142    }
143
144    #[inline]
145    fn from_noncanonical_u128(n: u128) -> Self {
146        Self([n as u64, (n >> 64) as u64, 0, 0])
147    }
148
149    #[inline]
150    fn from_noncanonical_u96(n: (u64, u32)) -> Self {
151        Self([n.0, n.1 as u64, 0, 0])
152    }
153
154    fn from_noncanonical_i64(n: i64) -> Self {
155        let f = Self::from_canonical_u64(n.unsigned_abs());
156        if n < 0 {
157            -f
158        } else {
159            f
160        }
161    }
162
163    fn from_noncanonical_u64(n: u64) -> Self {
164        Self::from_canonical_u64(n)
165    }
166}
167
168impl PrimeField for Secp256K1Scalar {
169    fn to_canonical_biguint(&self) -> BigUint {
170        let mut result = biguint_from_array(self.0);
171        if result >= Self::order() {
172            result -= Self::order();
173        }
174        result
175    }
176}
177
178impl Neg for Secp256K1Scalar {
179    type Output = Self;
180
181    #[inline]
182    fn neg(self) -> Self {
183        if self.is_zero() {
184            Self::ZERO
185        } else {
186            Self::from_noncanonical_biguint(Self::order() - self.to_canonical_biguint())
187        }
188    }
189}
190
191impl Add for Secp256K1Scalar {
192    type Output = Self;
193
194    #[inline]
195    fn add(self, rhs: Self) -> Self {
196        let mut result = self.to_canonical_biguint() + rhs.to_canonical_biguint();
197        if result >= Self::order() {
198            result -= Self::order();
199        }
200        Self::from_noncanonical_biguint(result)
201    }
202}
203
204impl AddAssign for Secp256K1Scalar {
205    #[inline]
206    fn add_assign(&mut self, rhs: Self) {
207        *self = *self + rhs;
208    }
209}
210
211impl Sum for Secp256K1Scalar {
212    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
213        iter.fold(Self::ZERO, |acc, x| acc + x)
214    }
215}
216
217impl Sub for Secp256K1Scalar {
218    type Output = Self;
219
220    #[inline]
221    #[allow(clippy::suspicious_arithmetic_impl)]
222    fn sub(self, rhs: Self) -> Self {
223        self + -rhs
224    }
225}
226
227impl SubAssign for Secp256K1Scalar {
228    #[inline]
229    fn sub_assign(&mut self, rhs: Self) {
230        *self = *self - rhs;
231    }
232}
233
234impl Mul for Secp256K1Scalar {
235    type Output = Self;
236
237    #[inline]
238    fn mul(self, rhs: Self) -> Self {
239        Self::from_noncanonical_biguint(
240            (self.to_canonical_biguint() * rhs.to_canonical_biguint()).mod_floor(&Self::order()),
241        )
242    }
243}
244
245impl MulAssign for Secp256K1Scalar {
246    #[inline]
247    fn mul_assign(&mut self, rhs: Self) {
248        *self = *self * rhs;
249    }
250}
251
252impl Product for Secp256K1Scalar {
253    #[inline]
254    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
255        iter.reduce(|acc, x| acc * x).unwrap_or(Self::ONE)
256    }
257}
258
259impl Div for Secp256K1Scalar {
260    type Output = Self;
261
262    #[allow(clippy::suspicious_arithmetic_impl)]
263    fn div(self, rhs: Self) -> Self::Output {
264        self * rhs.inverse()
265    }
266}
267
268impl DivAssign for Secp256K1Scalar {
269    fn div_assign(&mut self, rhs: Self) {
270        *self = *self / rhs;
271    }
272}
273
274#[cfg(test)]
275mod tests {
276    use crate::test_field_arithmetic;
277
278    test_field_arithmetic!(crate::secp256k1_scalar::Secp256K1Scalar);
279}
plonky2_field/secp256k1_scalar.rs

plonky2_field/
secp256k1_scalar.rs
