ff_ce/
lib.rs

1#![allow(unused_imports)]
2
3extern crate byteorder;
4extern crate rand;
5extern crate serde;
6extern crate hex as hex_ext;
7pub mod hex {
8    pub use hex_ext::*;
9}
10
11#[cfg(feature = "derive")]
12#[macro_use]
13extern crate ff_derive_ce;
14
15#[cfg(feature = "derive")]
16pub use ff_derive_ce::*;
17
18use std::error::Error;
19use std::fmt;
20use std::hash;
21use std::io::{self, Read, Write};
22
23/// This trait represents an element of a field.
24pub trait Field: Sized 
25    + Eq 
26    + Copy 
27    + Clone 
28    + Send 
29    + Sync 
30    + fmt::Debug 
31    + fmt::Display 
32    + 'static 
33    + rand::Rand 
34    + hash::Hash 
35    + Default 
36    + serde::Serialize
37    + serde::de::DeserializeOwned
38{
39    /// Returns the zero element of the field, the additive identity.
40    fn zero() -> Self;
41
42    /// Returns the one element of the field, the multiplicative identity.
43    fn one() -> Self;
44
45    /// Returns true iff this element is zero.
46    fn is_zero(&self) -> bool;
47
48    /// Squares this element.
49    fn square(&mut self);
50
51    /// Doubles this element.
52    fn double(&mut self);
53
54    /// Negates this element.
55    fn negate(&mut self);
56
57    /// Adds another element to this element.
58    fn add_assign(&mut self, other: &Self);
59
60    /// Subtracts another element from this element.
61    fn sub_assign(&mut self, other: &Self);
62
63    /// Multiplies another element by this element.
64    fn mul_assign(&mut self, other: &Self);
65
66    /// Computes the multiplicative inverse of this element, if nonzero.
67    fn inverse(&self) -> Option<Self>;
68
69    /// Exponentiates this element by a power of the base prime modulus via
70    /// the Frobenius automorphism.
71    fn frobenius_map(&mut self, power: usize);
72
73    /// Exponentiates this element by a number represented with `u64` limbs,
74    /// least significant digit first.
75    fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self {
76        let mut res = Self::one();
77
78        let mut found_one = false;
79
80        for i in BitIterator::new(exp) {
81            if found_one {
82                res.square();
83            } else {
84                found_one = i;
85            }
86
87            if i {
88                res.mul_assign(self);
89            }
90        }
91
92        res
93    }
94}
95
96/// This trait represents an element of a field that has a square root operation described for it.
97pub trait SqrtField: Field {
98    /// Returns the Legendre symbol of the field element.
99    fn legendre(&self) -> LegendreSymbol;
100
101    /// Returns the square root of the field element, if it is
102    /// quadratic residue.
103    fn sqrt(&self) -> Option<Self>;
104}
105
106/// This trait represents a wrapper around a biginteger which can encode any element of a particular
107/// prime field. It is a smart wrapper around a sequence of `u64` limbs, least-significant digit
108/// first.
109pub trait PrimeFieldRepr:
110    Sized
111    + Copy
112    + Clone
113    + Eq
114    + Ord
115    + Send
116    + Sync
117    + Default
118    + fmt::Debug
119    + fmt::Display
120    + 'static
121    + rand::Rand
122    + AsRef<[u64]>
123    + AsMut<[u64]>
124    + From<u64>
125    + hash::Hash
126    + serde::Serialize
127    + serde::de::DeserializeOwned
128{
129    /// Subtract another represetation from this one.
130    fn sub_noborrow(&mut self, other: &Self);
131
132    /// Add another representation to this one.
133    fn add_nocarry(&mut self, other: &Self);
134
135    /// Compute the number of bits needed to encode this number. Always a
136    /// multiple of 64.
137    fn num_bits(&self) -> u32;
138
139    /// Returns true iff this number is zero.
140    fn is_zero(&self) -> bool;
141
142    /// Returns true iff this number is odd.
143    fn is_odd(&self) -> bool;
144
145    /// Returns true iff this number is even.
146    fn is_even(&self) -> bool;
147
148    /// Performs a rightwise bitshift of this number, effectively dividing
149    /// it by 2.
150    fn div2(&mut self);
151
152    /// Performs a rightwise bitshift of this number by some amount.
153    fn shr(&mut self, amt: u32);
154
155    /// Performs a leftwise bitshift of this number, effectively multiplying
156    /// it by 2. Overflow is ignored.
157    fn mul2(&mut self);
158
159    /// Performs a leftwise bitshift of this number by some amount.
160    fn shl(&mut self, amt: u32);
161
162    /// Writes this `PrimeFieldRepr` as a big endian integer.
163    fn write_be<W: Write>(&self, mut writer: W) -> io::Result<()> {
164        use byteorder::{BigEndian, WriteBytesExt};
165
166        for digit in self.as_ref().iter().rev() {
167            writer.write_u64::<BigEndian>(*digit)?;
168        }
169
170        Ok(())
171    }
172
173    /// Reads a big endian integer into this representation.
174    fn read_be<R: Read>(&mut self, mut reader: R) -> io::Result<()> {
175        use byteorder::{BigEndian, ReadBytesExt};
176
177        for digit in self.as_mut().iter_mut().rev() {
178            *digit = reader.read_u64::<BigEndian>()?;
179        }
180
181        Ok(())
182    }
183
184    /// Writes this `PrimeFieldRepr` as a little endian integer.
185    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
186        use byteorder::{LittleEndian, WriteBytesExt};
187
188        for digit in self.as_ref().iter() {
189            writer.write_u64::<LittleEndian>(*digit)?;
190        }
191
192        Ok(())
193    }
194
195    /// Reads a little endian integer into this representation.
196    fn read_le<R: Read>(&mut self, mut reader: R) -> io::Result<()> {
197        use byteorder::{LittleEndian, ReadBytesExt};
198
199        for digit in self.as_mut().iter_mut() {
200            *digit = reader.read_u64::<LittleEndian>()?;
201        }
202
203        Ok(())
204    }
205}
206
207#[derive(Debug, PartialEq)]
208pub enum LegendreSymbol {
209    Zero = 0,
210    QuadraticResidue = 1,
211    QuadraticNonResidue = -1,
212}
213
214/// An error that may occur when trying to interpret a `PrimeFieldRepr` as a
215/// `PrimeField` element.
216#[derive(Debug)]
217pub enum PrimeFieldDecodingError {
218    /// The encoded value is not in the field
219    NotInField(String),
220}
221
222impl Error for PrimeFieldDecodingError {
223    fn description(&self) -> &str {
224        match *self {
225            PrimeFieldDecodingError::NotInField(..) => "not an element of the field",
226        }
227    }
228}
229
230impl fmt::Display for PrimeFieldDecodingError {
231    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
232        match *self {
233            PrimeFieldDecodingError::NotInField(ref repr) => {
234                write!(f, "{} is not an element of the field", repr)
235            }
236        }
237    }
238}
239
240/// This represents an element of a prime field.
241pub trait PrimeField: Field {
242    /// The prime field can be converted back and forth into this biginteger
243    /// representation.
244    type Repr: PrimeFieldRepr + From<Self>;
245
246    /// Interpret a string of numbers as a (congruent) prime field element.
247    /// Does not accept unnecessary leading zeroes or a blank string.
248    fn from_str(s: &str) -> Option<Self> {
249        if s.is_empty() {
250            return None;
251        }
252
253        if s == "0" {
254            return Some(Self::zero());
255        }
256
257        let mut res = Self::zero();
258
259        let ten = Self::from_repr(Self::Repr::from(10)).unwrap();
260
261        let mut first_digit = true;
262
263        for c in s.chars() {
264            match c.to_digit(10) {
265                Some(c) => {
266                    if first_digit {
267                        if c == 0 {
268                            return None;
269                        }
270
271                        first_digit = false;
272                    }
273
274                    res.mul_assign(&ten);
275                    res.add_assign(&Self::from_repr(Self::Repr::from(u64::from(c))).unwrap());
276                }
277                None => {
278                    return None;
279                }
280            }
281        }
282
283        Some(res)
284    }
285
286    /// Convert this prime field element into a biginteger representation.
287    fn from_repr(repr: Self::Repr) -> Result<Self, PrimeFieldDecodingError>;
288
289    /// Creates an element from raw representation in Montgommery form.
290    fn from_raw_repr(repr: Self::Repr) -> Result<Self, PrimeFieldDecodingError>;
291
292    /// Convert a biginteger representation into a prime field element, if
293    /// the number is an element of the field.
294    fn into_repr(&self) -> Self::Repr;
295
296    /// Expose Montgommery represendation.
297    fn into_raw_repr(&self) -> Self::Repr;
298
299    /// Returns the field characteristic; the modulus.
300    fn char() -> Self::Repr;
301
302    /// How many bits are needed to represent an element of this field.
303    const NUM_BITS: u32;
304
305    /// How many bits of information can be reliably stored in the field element.
306    const CAPACITY: u32;
307
308    /// Returns the multiplicative generator of `char()` - 1 order. This element
309    /// must also be quadratic nonresidue.
310    fn multiplicative_generator() -> Self;
311
312    /// 2^s * t = `char()` - 1 with t odd.
313    const S: u32;
314
315    /// Returns the 2^s root of unity computed by exponentiating the `multiplicative_generator()`
316    /// by t.
317    fn root_of_unity() -> Self;
318}
319
320/// An "engine" is a collection of types (fields, elliptic curve groups, etc.)
321/// with well-defined relationships. Specific relationships (for example, a
322/// pairing-friendly curve) can be defined in a subtrait.
323pub trait ScalarEngine: Sized + 'static + Clone + Copy + Send + Sync + fmt::Debug {
324    /// This is the scalar field of the engine's groups.
325    type Fr: PrimeField + SqrtField;
326}
327
328#[derive(Debug)]
329pub struct BitIterator<E> {
330    t: E,
331    n: usize,
332}
333
334impl<E: AsRef<[u64]>> BitIterator<E> {
335    pub fn new(t: E) -> Self {
336        let n = t.as_ref().len() * 64;
337
338        BitIterator { t, n }
339    }
340}
341
342impl<E: AsRef<[u64]>> Iterator for BitIterator<E> {
343    type Item = bool;
344
345    fn next(&mut self) -> Option<bool> {
346        if self.n == 0 {
347            None
348        } else {
349            self.n -= 1;
350            let part = self.n / 64;
351            let bit = self.n - (64 * part);
352
353            Some(self.t.as_ref()[part] & (1 << bit) > 0)
354        }
355    }
356
357    fn size_hint(&self) -> (usize, Option<usize>) {
358        (self.n, Some(self.n))
359    }
360}
361
362impl<E: AsRef<[u64]>> ExactSizeIterator for BitIterator<E> {
363    fn len(&self) -> usize {
364        self.n
365    }
366}
367
368#[test]
369fn test_bit_iterator() {
370    let mut a = BitIterator::new([0xa953d79b83f6ab59, 0x6dea2059e200bd39]);
371    let expected = "01101101111010100010000001011001111000100000000010111101001110011010100101010011110101111001101110000011111101101010101101011001";
372
373    for e in expected.chars() {
374        assert!(a.next().unwrap() == (e == '1'));
375    }
376
377    assert!(a.next().is_none());
378
379    let expected = "1010010101111110101010000101101011101000011101110101001000011001100100100011011010001011011011010001011011101100110100111011010010110001000011110100110001100110011101101000101100011100100100100100001010011101010111110011101011000011101000111011011101011001";
380
381    let mut a = BitIterator::new([
382        0x429d5f3ac3a3b759,
383        0xb10f4c66768b1c92,
384        0x92368b6d16ecd3b4,
385        0xa57ea85ae8775219,
386    ]);
387
388    for e in expected.chars() {
389        assert!(a.next().unwrap() == (e == '1'));
390    }
391
392    assert!(a.next().is_none());
393}
394
395
396#[test]
397fn test_bit_iterator_length() {
398    let a = BitIterator::new([0xa953d79b83f6ab59, 0x6dea2059e200bd39]);
399    let trusted_len = a.len();
400    let (lower, some_upper) = a.size_hint();
401    let upper = some_upper.unwrap();
402    assert_eq!(trusted_len, 128);
403    assert_eq!(lower, 128);
404    assert_eq!(upper, 128);
405
406    let mut i = 0;
407    for _ in a {
408        i += 1;
409    }
410
411    assert_eq!(trusted_len, i);
412}
413
414pub use self::arith_impl::*;
415
416mod arith_impl {
417    /// Calculate a - b - borrow, returning the result and modifying
418    /// the borrow value.
419    #[inline(always)]
420    pub fn sbb(a: u64, b: u64, borrow: &mut u64) -> u64 {
421        use std::num::Wrapping;
422
423        let tmp = (1u128 << 64).wrapping_add(u128::from(a)).wrapping_sub(u128::from(b)).wrapping_sub(u128::from(*borrow));
424
425        *borrow = if tmp >> 64 == 0 { 1 } else { 0 };
426
427        tmp as u64
428    }
429
430    /// Calculate a + b + carry, returning the sum and modifying the
431    /// carry value.
432    #[inline(always)]
433    pub fn adc(a: u64, b: u64, carry: &mut u64) -> u64 {
434        use std::num::Wrapping;
435
436        let tmp = u128::from(a).wrapping_add(u128::from(b)).wrapping_add(u128::from(*carry));
437
438        *carry = (tmp >> 64) as u64;
439
440        tmp as u64
441    }
442
443    /// Calculate a + (b * c) + carry, returning the least significant digit
444    /// and setting carry to the most significant digit.
445    #[inline(always)]
446    pub fn mac_with_carry(a: u64, b: u64, c: u64, carry: &mut u64) -> u64 {
447        use std::num::Wrapping;
448
449        let tmp = (u128::from(a)).wrapping_add(u128::from(b).wrapping_mul(u128::from(c))).wrapping_add(u128::from(*carry));
450
451        *carry = (tmp >> 64) as u64;
452
453        tmp as u64
454    }
455
456    #[inline(always)]
457    pub fn full_width_mul(a: u64, b: u64) -> (u64, u64) {
458        let tmp = (a as u128) * (b as u128);
459
460        return (tmp as u64, (tmp >> 64) as u64);
461    }
462
463    #[inline(always)]
464    pub fn mac_by_value(a: u64, b: u64, c: u64) -> (u64, u64) {
465        let tmp = ((b as u128) * (c as u128)) + (a as u128);
466
467        (tmp as u64, (tmp >> 64) as u64)
468    }
469
470    #[inline(always)]
471    pub fn mac_by_value_return_carry_only(a: u64, b: u64, c: u64) -> u64 {
472        let tmp = ((b as u128) * (c as u128)) + (a as u128);
473
474        (tmp >> 64) as u64
475    }
476
477    #[inline(always)]
478    pub fn mac_with_carry_by_value(a: u64, b: u64, c: u64, carry: u64) -> (u64, u64) {
479        let tmp = ((b as u128) * (c as u128)) + (a as u128) + (carry as u128);
480
481        (tmp as u64, (tmp >> 64) as u64)
482    }
483
484    #[inline(always)]
485    pub fn mul_double_add_by_value(a: u64, b: u64, c: u64) -> (u64, u64, u64) {
486        // multiply
487        let tmp = (b as u128) * (c as u128);
488        // doulbe
489        let lo = tmp as u64;
490        let hi = (tmp >> 64) as u64;
491        let superhi = hi >> 63;
492        let hi = hi << 1 | lo >> 63;
493        let lo = lo << 1;
494        // add
495        let tmp = (lo as u128) + ((hi as u128) << 64) + (a as u128);
496
497        (tmp as u64, (tmp >> 64) as u64, superhi)
498    }
499
500    #[inline(always)]
501    pub fn mul_double_add_add_carry_by_value(a: u64, b: u64, c: u64, carry: u64) -> (u64, u64, u64) {
502        // multiply
503        let tmp = (b as u128) * (c as u128);
504        // doulbe
505        let lo = tmp as u64;
506        let hi = (tmp >> 64) as u64;
507        let superhi = hi >> 63;
508        let hi = hi << 1 | lo >> 63;
509        let lo = lo << 1;
510        // add
511        let tmp = (lo as u128) + ((hi as u128) << 64) + (a as u128) + (carry as u128);
512
513        (tmp as u64, (tmp >> 64) as u64, superhi)
514    }
515
516    #[inline(always)]
517    pub fn mul_double_add_add_carry_by_value_ignore_superhi(a: u64, b: u64, c: u64, carry: u64) -> (u64, u64) {
518        // multiply
519        let tmp = (b as u128) * (c as u128);
520        // doulbe
521        let lo = tmp as u64;
522        let hi = (tmp >> 64) as u64;
523        let hi = hi << 1 | lo >> 63;
524        let lo = lo << 1;
525        // add
526        let tmp = (lo as u128) + ((hi as u128) << 64) + (a as u128) + (carry as u128);
527
528        (tmp as u64, (tmp >> 64) as u64)
529    }
530
531    #[inline(always)]
532    pub fn mul_double_add_low_and_high_carry_by_value(b: u64, c: u64, lo_carry: u64, hi_carry: u64) -> (u64, u64, u64) {
533        // multiply
534        let tmp = (b as u128) * (c as u128);
535        // doulbe
536        let lo = tmp as u64;
537        let hi = (tmp >> 64) as u64;
538        let superhi = hi >> 63;
539        let hi = hi << 1 | lo >> 63;
540        let lo = lo << 1;
541        // add
542        let tmp = (lo as u128) + ((hi as u128) << 64) + (lo_carry as u128) + ((hi_carry as u128) << 64);
543
544        (tmp as u64, (tmp >> 64) as u64, superhi)
545    }
546
547    #[inline(always)]
548    pub fn mul_double_add_low_and_high_carry_by_value_ignore_superhi(b: u64, c: u64, lo_carry: u64, hi_carry: u64) -> (u64, u64) {
549        // multiply
550        let tmp = (b as u128) * (c as u128);
551        // doulbe
552        let lo = tmp as u64;
553        let hi = (tmp >> 64) as u64;
554        let hi = hi << 1 | lo >> 63;
555        let lo = lo << 1;
556        // add
557        let tmp = (lo as u128) + ((hi as u128) << 64) + (lo_carry as u128) + ((hi_carry as u128) << 64);
558
559        (tmp as u64, (tmp >> 64) as u64)
560    }
561
562    #[inline(always)]
563    pub fn mul_double_add_add_low_and_high_carry_by_value(a: u64, b: u64, c: u64, lo_carry: u64, hi_carry: u64) -> (u64, u64, u64) {
564        // multiply
565        let tmp = (b as u128) * (c as u128);
566        // doulbe
567        let lo = tmp as u64;
568        let hi = (tmp >> 64) as u64;
569        let superhi = hi >> 63;
570        let hi = hi << 1 | lo >> 63;
571        let lo = lo << 1;
572        // add
573        let tmp = (lo as u128) + ((hi as u128) << 64) + (a as u128) + (lo_carry as u128) + ((hi_carry as u128) << 64);
574
575        (tmp as u64, (tmp >> 64) as u64, superhi)
576    }
577
578    #[inline(always)]
579    pub fn mul_double_add_add_low_and_high_carry_by_value_ignore_superhi(a: u64, b: u64, c: u64, lo_carry: u64, hi_carry: u64) -> (u64, u64) {
580        // multiply
581        let tmp = (b as u128) * (c as u128);
582        // doulbe
583        let lo = tmp as u64;
584        let hi = (tmp >> 64) as u64;
585        let hi = hi << 1 | lo >> 63;
586        let lo = lo << 1;
587        // add
588        let tmp = (lo as u128) + ((hi as u128) << 64) + (a as u128) + (lo_carry as u128) + ((hi_carry as u128) << 64);
589
590        (tmp as u64, (tmp >> 64) as u64)
591    }
592
593    #[inline(always)]
594    pub fn mac_with_low_and_high_carry_by_value(a: u64, b: u64, c: u64, lo_carry: u64, hi_carry: u64) -> (u64, u64) {
595        let tmp = ((b as u128) * (c as u128)) + (a as u128) + (lo_carry as u128) + ((hi_carry as u128) << 64);
596
597        (tmp as u64, (tmp >> 64) as u64)
598    }
599}
600
601pub use to_hex::{to_hex, from_hex};
602
603mod to_hex {
604    use super::{PrimeField, PrimeFieldRepr, hex_ext};
605
606    pub fn to_hex<F: PrimeField>(el: &F) -> String {
607        let repr = el.into_repr();
608        let required_length = repr.as_ref().len() * 8;
609        let mut buf: Vec<u8> = Vec::with_capacity(required_length);
610        repr.write_be(&mut buf).unwrap();
611
612        hex_ext::encode(&buf)
613    }
614
615    pub fn from_hex<F: PrimeField>(value: &str) -> Result<F, String> {
616        let value = if value.starts_with("0x") { &value[2..] } else { value };
617        if value.len() % 2 != 0 {return Err(format!("hex length must be even for full byte encoding: {}", value))}
618        let mut buf = hex_ext::decode(&value).map_err(|_| format!("could not decode hex: {}", value))?;
619        let mut repr = F::Repr::default();
620        let required_length = repr.as_ref().len() * 8;
621        buf.reverse();
622        buf.resize(required_length, 0);
623
624        repr.read_le(&buf[..]).map_err(|e| format!("could not read {}: {}", value, &e))?;
625
626        F::from_repr(repr).map_err(|e| format!("could not convert into prime field: {}: {}", value, &e))
627    }
628}
ff_ce/lib.rs

ff_ce/
lib.rs
