lambdaworks_math/field/fields/
p448_goldilocks_prime_field.rs

1use crate::errors::CreationError;
2use crate::field::errors::FieldError;
3use crate::field::traits::{IsField, IsPrimeField};
4use crate::traits::ByteConversion;
5use crate::unsigned_integer::element::UnsignedInteger;
6
7#[derive(Debug, Clone, PartialEq, Eq)]
8pub struct P448GoldilocksPrimeField;
9pub type U448 = UnsignedInteger<7>;
10
11/// Goldilocks Prime p = 2^448 - 2^224 - 1
12pub const P448_GOLDILOCKS_PRIME_FIELD_ORDER: U448 =
13    U448::from_hex_unchecked("fffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffffffffffffffffffffffffffffffffffffffffffffffffffff");
14
15/// 448-bit unsigned integer represented as
16/// a size 8 `u64` array `limbs` of 56-bit words.
17/// The least significant word is in the left most position.
18#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Default)]
19pub struct U56x8 {
20    limbs: [u64; 8],
21}
22
23impl ByteConversion for U56x8 {
24    #[cfg(feature = "alloc")]
25    fn to_bytes_be(&self) -> alloc::vec::Vec<u8> {
26        unimplemented!()
27    }
28
29    #[cfg(feature = "alloc")]
30    fn to_bytes_le(&self) -> alloc::vec::Vec<u8> {
31        unimplemented!()
32    }
33
34    fn from_bytes_be(_bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError>
35    where
36        Self: Sized,
37    {
38        unimplemented!()
39    }
40
41    fn from_bytes_le(_bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError>
42    where
43        Self: Sized,
44    {
45        unimplemented!()
46    }
47}
48
49impl IsField for P448GoldilocksPrimeField {
50    type BaseType = U56x8;
51
52    fn add(a: &U56x8, b: &U56x8) -> U56x8 {
53        let mut limbs = [0u64; 8];
54        for (i, limb) in limbs.iter_mut().enumerate() {
55            *limb = a.limbs[i] + b.limbs[i];
56        }
57
58        let mut sum = U56x8 { limbs };
59        Self::weak_reduce(&mut sum);
60        sum
61    }
62
63    /// Implements fast Karatsuba Multiplication optimized for the
64    /// Godilocks Prime field. Taken from Mike Hamburg's implemenation:
65    /// https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/src/p448/arch_ref64/f_impl.c
66    fn mul(a: &U56x8, b: &U56x8) -> U56x8 {
67        let (a, b) = (&a.limbs, &b.limbs);
68        let mut c = [0u64; 8];
69
70        let mut accum0 = 0u128;
71        let mut accum1 = 0u128;
72        let mut accum2: u128;
73
74        let mask = (1u64 << 56) - 1;
75
76        let mut aa = [0u64; 4];
77        let mut bb = [0u64; 4];
78        let mut bbb = [0u64; 4];
79
80        for i in 0..4 {
81            aa[i] = a[i] + a[i + 4];
82            bb[i] = b[i] + b[i + 4];
83            bbb[i] = bb[i] + b[i + 4];
84        }
85
86        let widemul = |a: u64, b: u64| -> u128 { (a as u128) * (b as u128) };
87
88        for i in 0..4 {
89            accum2 = 0;
90
91            for j in 0..=i {
92                accum2 += widemul(a[j], b[i - j]);
93                accum1 += widemul(aa[j], bb[i - j]);
94                accum0 += widemul(a[j + 4], b[i - j + 4]);
95            }
96            for j in (i + 1)..4 {
97                accum2 += widemul(a[j], b[8 - (j - i)]);
98                accum1 += widemul(aa[j], bbb[4 - (j - i)]);
99                accum0 += widemul(a[j + 4], bb[4 - (j - i)]);
100            }
101
102            accum1 -= accum2;
103            accum0 += accum2;
104
105            c[i] = (accum0 as u64) & mask;
106            c[i + 4] = (accum1 as u64) & mask;
107
108            accum0 >>= 56;
109            accum1 >>= 56;
110        }
111
112        accum0 += accum1;
113        accum0 += c[4] as u128;
114        accum1 += c[0] as u128;
115        c[4] = (accum0 as u64) & mask;
116        c[0] = (accum1 as u64) & mask;
117
118        accum0 >>= 56;
119        accum1 >>= 56;
120
121        c[5] += accum0 as u64;
122        c[1] += accum1 as u64;
123
124        U56x8 { limbs: c }
125    }
126
127    fn sub(a: &U56x8, b: &U56x8) -> U56x8 {
128        let co1 = ((1u64 << 56) - 1) * 2;
129        let co2 = co1 - 2;
130
131        let mut limbs = [0u64; 8];
132        for (i, limb) in limbs.iter_mut().enumerate() {
133            *limb =
134                a.limbs[i]
135                    .wrapping_sub(b.limbs[i])
136                    .wrapping_add(if i == 4 { co2 } else { co1 });
137        }
138
139        let mut res = U56x8 { limbs };
140        Self::weak_reduce(&mut res);
141        res
142    }
143
144    fn neg(a: &U56x8) -> U56x8 {
145        let zero = Self::zero();
146        Self::sub(&zero, a)
147    }
148
149    fn inv(a: &U56x8) -> Result<U56x8, FieldError> {
150        if *a == Self::zero() {
151            return Err(FieldError::InvZeroError);
152        }
153        Ok(Self::pow(
154            a,
155            P448_GOLDILOCKS_PRIME_FIELD_ORDER - U448::from_u64(2),
156        ))
157    }
158
159    fn div(a: &U56x8, b: &U56x8) -> Result<U56x8, FieldError> {
160        let b_inv = &Self::inv(b)?;
161        Ok(Self::mul(a, b_inv))
162    }
163
164    /// Taken from https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/src/per_field/f_generic.tmpl.c
165    fn eq(a: &U56x8, b: &U56x8) -> bool {
166        let mut c = Self::sub(a, b);
167        Self::strong_reduce(&mut c);
168        let mut ret = 0u64;
169        for limb in c.limbs.iter() {
170            ret |= limb;
171        }
172        ret == 0
173    }
174
175    fn zero() -> U56x8 {
176        U56x8 { limbs: [0u64; 8] }
177    }
178
179    fn one() -> U56x8 {
180        let mut limbs = [0u64; 8];
181        limbs[0] = 1;
182        U56x8 { limbs }
183    }
184
185    fn from_u64(x: u64) -> U56x8 {
186        let mut limbs = [0u64; 8];
187        limbs[0] = x & ((1u64 << 56) - 1);
188        limbs[1] = x >> 56;
189        U56x8 { limbs }
190    }
191
192    fn from_base_type(x: U56x8) -> U56x8 {
193        let mut x = x;
194        Self::strong_reduce(&mut x);
195        x
196    }
197}
198
199impl IsPrimeField for P448GoldilocksPrimeField {
200    type RepresentativeType = U448;
201
202    fn representative(a: &U56x8) -> U448 {
203        let mut a = *a;
204        Self::strong_reduce(&mut a);
205
206        let mut r = U448::from_u64(0);
207        for i in (0..7).rev() {
208            r = r << 56;
209            r = r + U448::from_u64(a.limbs[i]);
210        }
211        r
212    }
213
214    fn from_hex(hex_string: &str) -> Result<Self::BaseType, CreationError> {
215        U56x8::from_hex(hex_string)
216    }
217
218    #[cfg(feature = "std")]
219    fn to_hex(x: &U56x8) -> String {
220        U56x8::to_hex(x)
221    }
222
223    fn field_bit_size() -> usize {
224        448
225    }
226}
227
228impl P448GoldilocksPrimeField {
229    /// Reduces the value in each limb to less than 2^57 (2^56 + 2^8 - 2 is the largest possible value in a limb after this reduction)
230    /// Taken from https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/src/p448/arch_ref64/f_impl.h
231    fn weak_reduce(a: &mut U56x8) {
232        let a = &mut a.limbs;
233
234        let mask = (1u64 << 56) - 1;
235        let tmp = a[7] >> 56;
236        a[4] += tmp;
237
238        for i in (1..8).rev() {
239            a[i] = (a[i] & mask) + (a[i - 1] >> 56);
240        }
241
242        a[0] = (a[0] & mask) + tmp;
243    }
244
245    /// Reduces the number to its canonical form
246    /// Taken from https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/src/per_field/f_generic.tmpl.c
247    fn strong_reduce(a: &mut U56x8) {
248        P448GoldilocksPrimeField::weak_reduce(a);
249
250        const MODULUS: U56x8 = U56x8 {
251            limbs: [
252                0xffffffffffffff,
253                0xffffffffffffff,
254                0xffffffffffffff,
255                0xffffffffffffff,
256                0xfffffffffffffe,
257                0xffffffffffffff,
258                0xffffffffffffff,
259                0xffffffffffffff,
260            ],
261        };
262        let mask = (1u128 << 56) - 1;
263
264        let mut scarry = 0i128;
265        for i in 0..8 {
266            scarry = scarry + (a.limbs[i] as i128) - (MODULUS.limbs[i] as i128);
267            a.limbs[i] = ((scarry as u128) & mask) as u64;
268            scarry >>= 56;
269        }
270
271        assert!((scarry as u64) == 0 || (scarry as u64).wrapping_add(1) == 0);
272
273        let scarry_0 = scarry as u64;
274        let mut carry = 0u128;
275
276        for i in 0..8 {
277            carry = carry + (a.limbs[i] as u128) + ((scarry_0 & MODULUS.limbs[i]) as u128);
278            a.limbs[i] = (carry & mask) as u64;
279            carry >>= 56;
280        }
281
282        assert!((carry as u64).wrapping_add(scarry_0) == 0);
283    }
284}
285
286impl U56x8 {
287    pub const fn from_hex(hex_string: &str) -> Result<Self, CreationError> {
288        let mut result = [0u64; 8];
289        let mut limb = 0;
290        let mut limb_index = 0;
291        let mut shift = 0;
292        let value = hex_string.as_bytes();
293        let mut i: usize = value.len();
294        while i > 0 {
295            i -= 1;
296            limb |= match value[i] {
297                c @ b'0'..=b'9' => (c as u64 - '0' as u64) << shift,
298                c @ b'a'..=b'f' => (c as u64 - 'a' as u64 + 10) << shift,
299                c @ b'A'..=b'F' => (c as u64 - 'A' as u64 + 10) << shift,
300                _ => {
301                    return Err(CreationError::InvalidHexString);
302                }
303            };
304            shift += 4;
305            if shift == 56 && limb_index < 7 {
306                result[limb_index] = limb;
307                limb = 0;
308                limb_index += 1;
309                shift = 0;
310            }
311        }
312        result[limb_index] = limb;
313
314        Ok(U56x8 { limbs: result })
315    }
316
317    #[cfg(feature = "std")]
318    pub fn to_hex(&self) -> String {
319        let mut hex_string = String::new();
320        for &limb in self.limbs.iter().rev() {
321            hex_string.push_str(&format!("{limb:014X}"));
322        }
323        hex_string.trim_start_matches('0').to_string()
324    }
325}
326
327#[cfg(test)]
328mod tests {
329    use super::*;
330
331    #[test]
332    fn construct_u56x8_from_hex_string_1() {
333        let hex_str = "1";
334        let num = U56x8::from_hex(hex_str).unwrap();
335        assert_eq!(num.limbs, [1, 0, 0, 0, 0, 0, 0, 0]);
336    }
337
338    #[test]
339    fn construct_u56x8_from_hex_string_2() {
340        let hex_str = "49bbeeaa7102b38a0cfba4634f64a288bcb9b1366599f7afcb5453567ef7c34cce0f7139c6dea4841497172f637c7bbbf3ca1990ad88381e";
341        let num = U56x8::from_hex(hex_str).unwrap();
342        assert_eq!(
343            num.limbs,
344            [
345                56886054472923166,
346                6526028801096691,
347                16262733217666199,
348                35738265244798833,
349                43338005839369046,
350                45749290377754213,
351                38857821720366948,
352                20754307036021427
353            ]
354        );
355    }
356
357    #[test]
358    fn strong_reduce_test1() {
359        let mut num = U56x8::from_hex("fffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffffffffffffffffffffffffffffffffffffffffffffffffffff").unwrap();
360        P448GoldilocksPrimeField::strong_reduce(&mut num);
361        assert_eq!(num.limbs, [0, 0, 0, 0, 0, 0, 0, 0]);
362    }
363
364    #[test]
365    fn strong_reduce_test2() {
366        let mut num = U56x8::from_hex("ffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000000000000000000000000000000000000000000000000000").unwrap();
367        P448GoldilocksPrimeField::strong_reduce(&mut num);
368        assert_eq!(num.limbs, [1, 0, 0, 0, 0, 0, 0, 0]);
369    }
370
371    #[test]
372    fn representative_test() {
373        let num = U56x8::from_hex("ffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000000000000000000000000000000000000000000000000029").unwrap();
374        let r = P448GoldilocksPrimeField::representative(&num);
375        assert_eq!(r, U448::from_u64(42));
376    }
377
378    #[test]
379    fn p448_add_test_1() {
380        let num1 = U56x8::from_hex("73c7941e36ee1e12b2105fb96634848d62def10bc1782576cfa7f54486820202847bbfb2e8f89ff7707f9913b8cf9b9efaf2029cfd6d3fa9").unwrap();
381        let num2 = U56x8::from_hex("f3ef02193a11b6ea80be4bd2944d32c4674456a888b470b14e0cf223bed114bb28146d967f0d220cf20be2016dc84f51e5d5e29a71751f06").unwrap();
382        let num3 = P448GoldilocksPrimeField::add(&num1, &num2);
383        assert_eq!(num3, U56x8::from_hex("67b6963770ffd4fd32ceab8bfa81b751ca2347b44a2c96281db4e769455316bdac902d496805c204628b7b152697eaf0e0c7e5376ee25eb0").unwrap());
384    }
385
386    #[test]
387    fn p448_sub_test_1() {
388        let num1 = U56x8::from_hex("22264a9d5272984a996cc5eef6bd165e63bc70f2050bbd5bc24343df9cc25f826cef7bff7466963a82cd59f36671c724c53b8b27330ea076").unwrap();
389        let num2 = U56x8::from_hex("7a0063b5cd729df62c0e77071727639e06d0892eacb505569e8b47a99175d1d09a4bd7c22a2168c1fb9f3de31d9633d92341f84d000633b1").unwrap();
390        let num3 = P448GoldilocksPrimeField::sub(&num1, &num2);
391        assert_eq!(num3, U56x8::from_hex("a825e6e784fffa546d5e4ee7df95b2c05cebe7c35856b80523b7fc350b4c8db1d2a3a43d4a452d78872e1c1048db934ba1f992da33086cc4").unwrap());
392    }
393
394    #[test]
395    fn p448_neg_test_1() {
396        let num1 = U56x8::from_hex("21183d1faa857cd3f08d54871837b06d70af4e6b85173c0ff02685147f38e8b9af3141baad0067f3514a527bd3e7405a953c3a8fa9a15bb3").unwrap();
397        let num2 = P448GoldilocksPrimeField::neg(&num1);
398        assert_eq!(num2, U56x8::from_hex("dee7c2e0557a832c0f72ab78e7c84f928f50b1947ae8c3f00fd97aea80c7174650cebe4552ff980caeb5ad842c18bfa56ac3c570565ea44c").unwrap());
399    }
400
401    #[test]
402    fn p448_mul_test_1() {
403        let num1 = U56x8::from_hex("a").unwrap();
404        let num2 = U56x8::from_hex("b").unwrap();
405        let num3 = P448GoldilocksPrimeField::mul(&num1, &num2);
406        assert_eq!(num3, U56x8::from_hex("6e").unwrap());
407    }
408
409    #[test]
410    fn p448_mul_test_2() {
411        let num1 = U56x8::from_hex("b7aa542ac8824fbf654ee0ab4ea5eb3b0ad65b48bfef5e4d8b84ab5737e9283c06ecbadd799688cdf73cd7d077d53b5e6f738b264086d034").unwrap();
412        let num2 = U56x8::from_hex("89a36d8b491f5a9af136a35061a59aa2c65353a3c99bb205a53c7ae2f37e6ae492f24248fc549344ba2f203c6d5b2b5dab216fdd1a7dcf87").unwrap();
413        let num3 = P448GoldilocksPrimeField::mul(&num1, &num2);
414        assert_eq!(num3, U56x8::from_hex("f61c57f70d8a1eaf261907d08eb1086c2289f7bbb6ff6a0dfd016f91ac9eda658879b52a654a10b2ce123717fad3ab15b1e77ce643683886").unwrap());
415    }
416
417    #[test]
418    fn p448_pow_test_1() {
419        let num1 = U56x8::from_hex("6b1b1d952930ee34fb6ed3521f7653293fd7e01de2027673d3d5a0bf3dc0688530bec50b3dfca4df28cc432bec1198e17fde3e1cc79e5732").unwrap();
420        let num2 = P448GoldilocksPrimeField::pow(&num1, 65537u64);
421        assert_eq!(num2, U56x8::from_hex("ec48eda1579a0879c01e8853e4a718ede9cd6bcf88d6696b47dc4dce7d2acdd1a37674aa455d84126800893975c95bb47c40b098a9e30836").unwrap());
422    }
423
424    #[test]
425    fn p448_inv_test_1() {
426        let num1 = U56x8::from_hex("b86e226f5ac29af28c74e272fc129ab167798f70dedd2ce76aa76204a23beb74c8ddba2a643196c62ee35a18472d6de7d82b6af4b2fc5e58").unwrap();
427        let num2 = U56x8::from_hex("bb2bd89a1297c7a6052b41be503aa7de2cd6e6775396e76bf995f27f1dccf69131067824ded693bdd6e58fe7c2276fa92ec1d9a0048b9be6").unwrap();
428        let num3 = P448GoldilocksPrimeField::div(&num1, &num2);
429        assert_eq!(num3.unwrap(), U56x8::from_hex("707b5cc75967b58ebd28d14d4ed7ed9eaae1187d0b359c7733cf61b1a5c87fc88228ca532c50f19d1ba57146ca2e38417922033f647c8d9").unwrap());
430    }
431
432    #[test]
433    fn p448_from_u64_test_1() {
434        let num = P448GoldilocksPrimeField::from_u64(2012613457133209520u64);
435        assert_eq!(num, U56x8::from_hex("1bee3d46a69887b0").unwrap());
436    }
437
438    #[test]
439    fn p448_from_base_type_test_1() {
440        let mut limbs = [0u64; 8];
441        limbs[0] = 15372427657916355716u64;
442        limbs[1] = 6217911673150459564u64;
443        let num1 = U56x8 { limbs };
444        let num2 = P448GoldilocksPrimeField::from_base_type(num1);
445        assert_eq!(
446            num2,
447            U56x8::from_hex("564a75b90ae34f8155d5821d7e9484").unwrap()
448        );
449    }
450
451    #[cfg(feature = "std")]
452    #[test]
453    fn to_hex_test() {
454        let mut limbs = [0u64; 8];
455        limbs[0] = 15372427657916355716u64;
456        limbs[1] = 6217911673150459564u64;
457        let num = U56x8::from_hex("564A75B90AE34F8155D5821D7E9484").unwrap();
458        assert_eq!(U56x8::to_hex(&num), "564A75B90AE34F8155D5821D7E9484")
459    }
460}
lambdaworks_math/field/fields/p448_goldilocks_prime_field.rs

lambdaworks_math/field/fields/
p448_goldilocks_prime_field.rs
