ark_ff/biginteger/
mod.rs

1use crate::{
2    bits::{BitIteratorBE, BitIteratorLE},
3    const_for, UniformRand,
4};
5#[allow(unused)]
6use ark_ff_macros::unroll_for_loops;
7use ark_serialize::{
8    CanonicalDeserialize, CanonicalSerialize, Compress, SerializationError, Valid, Validate,
9};
10use ark_std::{
11    convert::TryFrom,
12    fmt::{Debug, Display, UpperHex},
13    io::{Read, Write},
14    rand::{
15        distributions::{Distribution, Standard},
16        Rng,
17    },
18    vec::Vec,
19};
20use num_bigint::BigUint;
21use zeroize::Zeroize;
22
23#[macro_use]
24pub mod arithmetic;
25
26#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash, Zeroize)]
27pub struct BigInt<const N: usize>(pub [u64; N]);
28
29impl<const N: usize> Default for BigInt<N> {
30    fn default() -> Self {
31        Self([0u64; N])
32    }
33}
34
35impl<const N: usize> CanonicalSerialize for BigInt<N> {
36    fn serialize_with_mode<W: Write>(
37        &self,
38        writer: W,
39        compress: Compress,
40    ) -> Result<(), SerializationError> {
41        self.0.serialize_with_mode(writer, compress)
42    }
43
44    fn serialized_size(&self, compress: Compress) -> usize {
45        self.0.serialized_size(compress)
46    }
47}
48
49impl<const N: usize> Valid for BigInt<N> {
50    fn check(&self) -> Result<(), SerializationError> {
51        self.0.check()
52    }
53}
54
55impl<const N: usize> CanonicalDeserialize for BigInt<N> {
56    fn deserialize_with_mode<R: Read>(
57        reader: R,
58        compress: Compress,
59        validate: Validate,
60    ) -> Result<Self, SerializationError> {
61        Ok(BigInt::<N>(<[u64; N]>::deserialize_with_mode(
62            reader, compress, validate,
63        )?))
64    }
65}
66
67/// Construct a [`struct@BigInt<N>`] element from a literal string.
68///
69/// # Panics
70///
71/// If the integer represented by the string cannot fit in the number
72/// of limbs of the `BigInt`, this macro results in a
73/// * compile-time error if used in a const context
74/// * run-time error otherwise.
75///
76/// # Usage
77/// ```rust
78/// # use ark_ff::BigInt;
79/// const ONE: BigInt<6> = BigInt!("1");
80///
81/// fn check_correctness() {
82///     assert_eq!(ONE, BigInt::from(1u8));
83/// }
84/// ```
85#[macro_export]
86macro_rules! BigInt {
87    ($c0:expr) => {{
88        let (is_positive, limbs) = $crate::ark_ff_macros::to_sign_and_limbs!($c0);
89        assert!(is_positive);
90        let mut integer = $crate::BigInt::zero();
91        assert!(integer.0.len() >= limbs.len());
92        $crate::const_for!((i in 0..(limbs.len())) {
93            integer.0[i] = limbs[i];
94        });
95        integer
96    }};
97}
98
99#[doc(hidden)]
100macro_rules! const_modulo {
101    ($a:expr, $divisor:expr) => {{
102        // Stupid slow base-2 long division taken from
103        // https://en.wikipedia.org/wiki/Division_algorithm
104        assert!(!$divisor.const_is_zero());
105        let mut remainder = Self::new([0u64; N]);
106        let end = $a.num_bits();
107        let mut i = (end - 1) as isize;
108        let mut carry;
109        while i >= 0 {
110            (remainder, carry) = remainder.const_mul2_with_carry();
111            remainder.0[0] |= $a.get_bit(i as usize) as u64;
112            if remainder.const_geq($divisor) || carry {
113                let (r, borrow) = remainder.const_sub_with_borrow($divisor);
114                remainder = r;
115                assert!(borrow == carry);
116            }
117            i -= 1;
118        }
119        remainder
120    }};
121}
122
123impl<const N: usize> BigInt<N> {
124    pub const fn new(value: [u64; N]) -> Self {
125        Self(value)
126    }
127
128    pub const fn zero() -> Self {
129        Self([0u64; N])
130    }
131
132    pub const fn one() -> Self {
133        let mut one = Self::zero();
134        one.0[0] = 1;
135        one
136    }
137
138    #[doc(hidden)]
139    pub const fn const_is_even(&self) -> bool {
140        self.0[0] % 2 == 0
141    }
142
143    #[doc(hidden)]
144    pub const fn const_is_odd(&self) -> bool {
145        self.0[0] % 2 == 1
146    }
147
148    #[doc(hidden)]
149    pub const fn mod_4(&self) -> u8 {
150        // To compute n % 4, we need to simply look at the
151        // 2 least significant bits of n, and check their value mod 4.
152        (((self.0[0] << 62) >> 62) % 4) as u8
153    }
154
155    /// Compute a right shift of `self`
156    /// This is equivalent to a (saturating) division by 2.
157    #[doc(hidden)]
158    pub const fn const_shr(&self) -> Self {
159        let mut result = *self;
160        let mut t = 0;
161        crate::const_for!((i in 0..N) {
162            let a = result.0[N - i - 1];
163            let t2 = a << 63;
164            result.0[N - i - 1] >>= 1;
165            result.0[N - i - 1] |= t;
166            t = t2;
167        });
168        result
169    }
170
171    const fn const_geq(&self, other: &Self) -> bool {
172        const_for!((i in 0..N) {
173            let a = self.0[N - i - 1];
174            let b = other.0[N - i - 1];
175            if a < b {
176                return false;
177            } else if a > b {
178                return true;
179            }
180        });
181        true
182    }
183
184    /// Compute the largest integer `s` such that `self = 2**s * t + 1` for odd `t`.
185    #[doc(hidden)]
186    pub const fn two_adic_valuation(mut self) -> u32 {
187        let mut two_adicity = 0;
188        assert!(self.const_is_odd());
189        // Since `self` is odd, we can always subtract one
190        // without a borrow
191        self.0[0] -= 1;
192        while self.const_is_even() {
193            self = self.const_shr();
194            two_adicity += 1;
195        }
196        two_adicity
197    }
198
199    /// Compute the smallest odd integer `t` such that `self = 2**s * t + 1` for some
200    /// integer `s = self.two_adic_valuation()`.
201    #[doc(hidden)]
202    pub const fn two_adic_coefficient(mut self) -> Self {
203        assert!(self.const_is_odd());
204        // Since `self` is odd, we can always subtract one
205        // without a borrow
206        self.0[0] -= 1;
207        while self.const_is_even() {
208            self = self.const_shr();
209        }
210        assert!(self.const_is_odd());
211        self
212    }
213
214    /// Divide `self` by 2, rounding down if necessary.
215    /// That is, if `self.is_odd()`, compute `(self - 1)/2`.
216    /// Else, compute `self/2`.
217    #[doc(hidden)]
218    pub const fn divide_by_2_round_down(mut self) -> Self {
219        if self.const_is_odd() {
220            self.0[0] -= 1;
221        }
222        self.const_shr()
223    }
224
225    /// Find the number of bits in the binary decomposition of `self`.
226    #[doc(hidden)]
227    pub const fn const_num_bits(self) -> u32 {
228        ((N - 1) * 64) as u32 + (64 - self.0[N - 1].leading_zeros())
229    }
230
231    #[inline]
232    pub(crate) const fn const_sub_with_borrow(mut self, other: &Self) -> (Self, bool) {
233        let mut borrow = 0;
234
235        const_for!((i in 0..N) {
236            self.0[i] = sbb!(self.0[i], other.0[i], &mut borrow);
237        });
238
239        (self, borrow != 0)
240    }
241
242    #[inline]
243    pub(crate) const fn const_add_with_carry(mut self, other: &Self) -> (Self, bool) {
244        let mut carry = 0;
245
246        crate::const_for!((i in 0..N) {
247            self.0[i] = adc!(self.0[i], other.0[i], &mut carry);
248        });
249
250        (self, carry != 0)
251    }
252
253    const fn const_mul2_with_carry(mut self) -> (Self, bool) {
254        let mut last = 0;
255        crate::const_for!((i in 0..N) {
256            let a = self.0[i];
257            let tmp = a >> 63;
258            self.0[i] <<= 1;
259            self.0[i] |= last;
260            last = tmp;
261        });
262        (self, last != 0)
263    }
264
265    pub(crate) const fn const_is_zero(&self) -> bool {
266        let mut is_zero = true;
267        crate::const_for!((i in 0..N) {
268            is_zero &= self.0[i] == 0;
269        });
270        is_zero
271    }
272
273    /// Computes the Montgomery R constant modulo `self`.
274    #[doc(hidden)]
275    pub const fn montgomery_r(&self) -> Self {
276        let two_pow_n_times_64 = crate::const_helpers::RBuffer::<N>([0u64; N], 1);
277        const_modulo!(two_pow_n_times_64, self)
278    }
279
280    /// Computes the Montgomery R2 constant modulo `self`.
281    #[doc(hidden)]
282    pub const fn montgomery_r2(&self) -> Self {
283        let two_pow_n_times_64_square =
284            crate::const_helpers::R2Buffer::<N>([0u64; N], [0u64; N], 1);
285        const_modulo!(two_pow_n_times_64_square, self)
286    }
287}
288
289impl<const N: usize> BigInteger for BigInt<N> {
290    const NUM_LIMBS: usize = N;
291
292    #[inline]
293    fn add_with_carry(&mut self, other: &Self) -> bool {
294        {
295            use arithmetic::adc_for_add_with_carry as adc;
296
297            let a = &mut self.0;
298            let b = &other.0;
299            let mut carry = 0;
300
301            if N >= 1 {
302                carry = adc(&mut a[0], b[0], carry);
303            }
304            if N >= 2 {
305                carry = adc(&mut a[1], b[1], carry);
306            }
307            if N >= 3 {
308                carry = adc(&mut a[2], b[2], carry);
309            }
310            if N >= 4 {
311                carry = adc(&mut a[3], b[3], carry);
312            }
313            if N >= 5 {
314                carry = adc(&mut a[4], b[4], carry);
315            }
316            if N >= 6 {
317                carry = adc(&mut a[5], b[5], carry);
318            }
319            for i in 6..N {
320                carry = adc(&mut a[i], b[i], carry);
321            }
322            carry != 0
323        }
324    }
325
326    #[inline]
327    fn sub_with_borrow(&mut self, other: &Self) -> bool {
328        use arithmetic::sbb_for_sub_with_borrow as sbb;
329
330        let a = &mut self.0;
331        let b = &other.0;
332        let mut borrow = 0u8;
333
334        if N >= 1 {
335            borrow = sbb(&mut a[0], b[0], borrow);
336        }
337        if N >= 2 {
338            borrow = sbb(&mut a[1], b[1], borrow);
339        }
340        if N >= 3 {
341            borrow = sbb(&mut a[2], b[2], borrow);
342        }
343        if N >= 4 {
344            borrow = sbb(&mut a[3], b[3], borrow);
345        }
346        if N >= 5 {
347            borrow = sbb(&mut a[4], b[4], borrow);
348        }
349        if N >= 6 {
350            borrow = sbb(&mut a[5], b[5], borrow);
351        }
352        for i in 6..N {
353            borrow = sbb(&mut a[i], b[i], borrow);
354        }
355        borrow != 0
356    }
357
358    #[inline]
359    #[allow(unused)]
360    fn mul2(&mut self) -> bool {
361        #[cfg(all(target_arch = "x86_64", feature = "asm"))]
362        #[allow(unsafe_code)]
363        {
364            let mut carry = 0;
365
366            for i in 0..N {
367                unsafe {
368                    use core::arch::x86_64::_addcarry_u64;
369                    carry = _addcarry_u64(carry, self.0[i], self.0[i], &mut self.0[i])
370                };
371            }
372
373            carry != 0
374        }
375
376        #[cfg(not(all(target_arch = "x86_64", feature = "asm")))]
377        {
378            let mut last = 0;
379            for i in 0..N {
380                let a = &mut self.0[i];
381                let tmp = *a >> 63;
382                *a <<= 1;
383                *a |= last;
384                last = tmp;
385            }
386            last != 0
387        }
388    }
389
390    #[inline]
391    fn muln(&mut self, mut n: u32) {
392        if n >= (64 * N) as u32 {
393            *self = Self::from(0u64);
394            return;
395        }
396
397        while n >= 64 {
398            let mut t = 0;
399            for i in 0..N {
400                core::mem::swap(&mut t, &mut self.0[i]);
401            }
402            n -= 64;
403        }
404
405        if n > 0 {
406            let mut t = 0;
407            #[allow(unused)]
408            for i in 0..N {
409                let a = &mut self.0[i];
410                let t2 = *a >> (64 - n);
411                *a <<= n;
412                *a |= t;
413                t = t2;
414            }
415        }
416    }
417
418    #[inline]
419    fn div2(&mut self) {
420        let mut t = 0;
421        for i in 0..N {
422            let a = &mut self.0[N - i - 1];
423            let t2 = *a << 63;
424            *a >>= 1;
425            *a |= t;
426            t = t2;
427        }
428    }
429
430    #[inline]
431    fn divn(&mut self, mut n: u32) {
432        if n >= (64 * N) as u32 {
433            *self = Self::from(0u64);
434            return;
435        }
436
437        while n >= 64 {
438            let mut t = 0;
439            for i in 0..N {
440                core::mem::swap(&mut t, &mut self.0[N - i - 1]);
441            }
442            n -= 64;
443        }
444
445        if n > 0 {
446            let mut t = 0;
447            #[allow(unused)]
448            for i in 0..N {
449                let a = &mut self.0[N - i - 1];
450                let t2 = *a << (64 - n);
451                *a >>= n;
452                *a |= t;
453                t = t2;
454            }
455        }
456    }
457
458    #[inline]
459    fn is_odd(&self) -> bool {
460        self.0[0] & 1 == 1
461    }
462
463    #[inline]
464    fn is_even(&self) -> bool {
465        !self.is_odd()
466    }
467
468    #[inline]
469    fn is_zero(&self) -> bool {
470        self.0.iter().all(|&e| e == 0)
471    }
472
473    #[inline]
474    fn num_bits(&self) -> u32 {
475        let mut ret = N as u32 * 64;
476        for i in self.0.iter().rev() {
477            let leading = i.leading_zeros();
478            ret -= leading;
479            if leading != 64 {
480                break;
481            }
482        }
483
484        ret
485    }
486
487    #[inline]
488    fn get_bit(&self, i: usize) -> bool {
489        if i >= 64 * N {
490            false
491        } else {
492            let limb = i / 64;
493            let bit = i - (64 * limb);
494            (self.0[limb] & (1 << bit)) != 0
495        }
496    }
497
498    #[inline]
499    fn from_bits_be(bits: &[bool]) -> Self {
500        let mut res = Self::default();
501        let mut acc: u64 = 0;
502
503        let mut bits = bits.to_vec();
504        bits.reverse();
505        for (i, bits64) in bits.chunks(64).enumerate() {
506            for bit in bits64.iter().rev() {
507                acc <<= 1;
508                acc += *bit as u64;
509            }
510            res.0[i] = acc;
511            acc = 0;
512        }
513        res
514    }
515
516    fn from_bits_le(bits: &[bool]) -> Self {
517        let mut res = Self::zero();
518        for (bits64, res_i) in bits.chunks(64).zip(&mut res.0) {
519            for (i, bit) in bits64.iter().enumerate() {
520                *res_i |= (*bit as u64) << i;
521            }
522        }
523        res
524    }
525
526    #[inline]
527    fn to_bytes_be(&self) -> Vec<u8> {
528        let mut le_bytes = self.to_bytes_le();
529        le_bytes.reverse();
530        le_bytes
531    }
532
533    #[inline]
534    fn to_bytes_le(&self) -> Vec<u8> {
535        let array_map = self.0.iter().map(|limb| limb.to_le_bytes());
536        let mut res = Vec::with_capacity(N * 8);
537        for limb in array_map {
538            res.extend_from_slice(&limb);
539        }
540        res
541    }
542}
543
544impl<const N: usize> UpperHex for BigInt<N> {
545    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
546        write!(f, "{:016X}", BigUint::from(*self))
547    }
548}
549
550impl<const N: usize> Display for BigInt<N> {
551    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
552        write!(f, "{}", BigUint::from(*self))
553    }
554}
555
556impl<const N: usize> Ord for BigInt<N> {
557    #[inline]
558    #[cfg_attr(target_arch = "x86_64", unroll_for_loops(12))]
559    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
560        use core::cmp::Ordering;
561        #[cfg(target_arch = "x86_64")]
562        for i in 0..N {
563            let a = &self.0[N - i - 1];
564            let b = &other.0[N - i - 1];
565            match a.cmp(b) {
566                Ordering::Equal => {},
567                order => return order,
568            };
569        }
570        #[cfg(not(target_arch = "x86_64"))]
571        for (a, b) in self.0.iter().rev().zip(other.0.iter().rev()) {
572            if a < b {
573                return Ordering::Less;
574            } else if a > b {
575                return Ordering::Greater;
576            }
577        }
578        Ordering::Equal
579    }
580}
581
582impl<const N: usize> PartialOrd for BigInt<N> {
583    #[inline]
584    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
585        Some(self.cmp(other))
586    }
587}
588
589impl<const N: usize> Distribution<BigInt<N>> for Standard {
590    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInt<N> {
591        let mut res = [0u64; N];
592        for item in res.iter_mut() {
593            *item = rng.gen();
594        }
595        BigInt::<N>(res)
596    }
597}
598
599impl<const N: usize> AsMut<[u64]> for BigInt<N> {
600    #[inline]
601    fn as_mut(&mut self) -> &mut [u64] {
602        &mut self.0
603    }
604}
605
606impl<const N: usize> AsRef<[u64]> for BigInt<N> {
607    #[inline]
608    fn as_ref(&self) -> &[u64] {
609        &self.0
610    }
611}
612
613impl<const N: usize> From<u64> for BigInt<N> {
614    #[inline]
615    fn from(val: u64) -> BigInt<N> {
616        let mut repr = Self::default();
617        repr.0[0] = val;
618        repr
619    }
620}
621
622impl<const N: usize> From<u32> for BigInt<N> {
623    #[inline]
624    fn from(val: u32) -> BigInt<N> {
625        let mut repr = Self::default();
626        repr.0[0] = u64::from(val);
627        repr
628    }
629}
630
631impl<const N: usize> From<u16> for BigInt<N> {
632    #[inline]
633    fn from(val: u16) -> BigInt<N> {
634        let mut repr = Self::default();
635        repr.0[0] = u64::from(val);
636        repr
637    }
638}
639
640impl<const N: usize> From<u8> for BigInt<N> {
641    #[inline]
642    fn from(val: u8) -> BigInt<N> {
643        let mut repr = Self::default();
644        repr.0[0] = u64::from(val);
645        repr
646    }
647}
648
649impl<const N: usize> TryFrom<BigUint> for BigInt<N> {
650    type Error = ();
651
652    /// Returns `Err(())` if the bit size of `val` is more than `N * 64`.
653    #[inline]
654    fn try_from(val: num_bigint::BigUint) -> Result<BigInt<N>, Self::Error> {
655        let bytes = val.to_bytes_le();
656
657        if bytes.len() > N * 8 {
658            Err(())
659        } else {
660            let mut limbs = [0u64; N];
661
662            bytes
663                .chunks(8)
664                .into_iter()
665                .enumerate()
666                .for_each(|(i, chunk)| {
667                    let mut chunk_padded = [0u8; 8];
668                    chunk_padded[..chunk.len()].copy_from_slice(chunk);
669                    limbs[i] = u64::from_le_bytes(chunk_padded)
670                });
671
672            Ok(Self(limbs))
673        }
674    }
675}
676
677impl<const N: usize> From<BigInt<N>> for BigUint {
678    #[inline]
679    fn from(val: BigInt<N>) -> num_bigint::BigUint {
680        BigUint::from_bytes_le(&val.to_bytes_le())
681    }
682}
683
684/// Compute the signed modulo operation on a u64 representation, returning the result.
685/// If n % modulus > modulus / 2, return modulus - n
686/// # Example
687/// ```
688/// use ark_ff::signed_mod_reduction;
689/// let res = signed_mod_reduction(6u64, 8u64);
690/// assert_eq!(res, -2i64);
691/// ```
692pub fn signed_mod_reduction(n: u64, modulus: u64) -> i64 {
693    let t = (n % modulus) as i64;
694    if t as u64 >= (modulus / 2) {
695        t - (modulus as i64)
696    } else {
697        t
698    }
699}
700
701pub type BigInteger64 = BigInt<1>;
702pub type BigInteger128 = BigInt<2>;
703pub type BigInteger256 = BigInt<4>;
704pub type BigInteger320 = BigInt<5>;
705pub type BigInteger384 = BigInt<6>;
706pub type BigInteger448 = BigInt<7>;
707pub type BigInteger768 = BigInt<12>;
708pub type BigInteger832 = BigInt<13>;
709
710#[cfg(test)]
711mod tests;
712
713/// This defines a `BigInteger`, a smart wrapper around a
714/// sequence of `u64` limbs, least-significant limb first.
715// TODO: get rid of this trait once we can use associated constants in const generics.
716pub trait BigInteger:
717    CanonicalSerialize
718    + CanonicalDeserialize
719    + Copy
720    + Clone
721    + Debug
722    + Default
723    + Display
724    + Eq
725    + Ord
726    + Send
727    + Sized
728    + Sync
729    + 'static
730    + UniformRand
731    + Zeroize
732    + AsMut<[u64]>
733    + AsRef<[u64]>
734    + From<u64>
735    + From<u32>
736    + From<u16>
737    + From<u8>
738    + TryFrom<BigUint, Error = ()>
739    + Into<BigUint>
740{
741    /// Number of 64-bit limbs representing `Self`.
742    const NUM_LIMBS: usize;
743
744    /// Add another [`BigInteger`] to `self`. This method stores the result in `self`,
745    /// and returns a carry bit.
746    ///
747    /// # Example
748    ///
749    /// ```
750    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
751    ///
752    /// // Basic
753    /// let (mut one, mut x) = (B::from(1u64), B::from(2u64));
754    /// let carry = x.add_with_carry(&one);
755    /// assert_eq!(x, B::from(3u64));
756    /// assert_eq!(carry, false);
757    ///
758    /// // Edge-Case
759    /// let mut x = B::from(u64::MAX);
760    /// let carry = x.add_with_carry(&one);
761    /// assert_eq!(x, B::from(0u64));
762    /// assert_eq!(carry, true)
763    /// ```
764    fn add_with_carry(&mut self, other: &Self) -> bool;
765
766    /// Subtract another [`BigInteger`] from this one. This method stores the result in
767    /// `self`, and returns a borrow.
768    ///
769    /// # Example
770    ///
771    /// ```
772    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
773    ///
774    /// // Basic
775    /// let (mut one_sub, two, mut three_sub) = (B::from(1u64), B::from(2u64), B::from(3u64));
776    /// let borrow = three_sub.sub_with_borrow(&two);
777    /// assert_eq!(three_sub, one_sub);
778    /// assert_eq!(borrow, false);
779    ///
780    /// // Edge-Case
781    /// let borrow = one_sub.sub_with_borrow(&two);
782    /// assert_eq!(one_sub, B::from(u64::MAX));
783    /// assert_eq!(borrow, true);
784    /// ```
785    fn sub_with_borrow(&mut self, other: &Self) -> bool;
786
787    /// Performs a leftwise bitshift of this number, effectively multiplying
788    /// it by 2. Overflow is ignored.
789    /// # Example
790    ///
791    /// ```
792    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
793    ///
794    /// // Basic
795    /// let mut two_mul = B::from(2u64);
796    /// two_mul.mul2();
797    /// assert_eq!(two_mul, B::from(4u64));
798    ///
799    /// // Edge-Cases
800    /// let mut zero = B::from(0u64);
801    /// zero.mul2();
802    /// assert_eq!(zero, B::from(0u64));
803    ///
804    /// let mut arr: [bool; 64] = [false; 64];
805    /// arr[0] = true;
806    /// let mut mul = B::from_bits_be(&arr);
807    /// mul.mul2();
808    /// assert_eq!(mul, B::from(0u64));
809    /// ```
810    fn mul2(&mut self) -> bool;
811
812    /// Performs a leftwise bitshift of this number by n bits, effectively multiplying
813    /// it by 2^n. Overflow is ignored.
814    /// # Example
815    ///
816    /// ```
817    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
818    ///
819    /// // Basic
820    /// let mut one_mul = B::from(1u64);
821    /// one_mul.muln(5);
822    /// assert_eq!(one_mul, B::from(32u64));
823    ///
824    /// // Edge-Case
825    /// let mut zero = B::from(0u64);
826    /// zero.muln(5);
827    /// assert_eq!(zero, B::from(0u64));
828    ///
829    /// let mut arr: [bool; 64] = [false; 64];
830    /// arr[4] = true;
831    /// let mut mul = B::from_bits_be(&arr);
832    /// mul.muln(5);
833    /// assert_eq!(mul, B::from(0u64));
834    /// ```
835    fn muln(&mut self, amt: u32);
836
837    /// Performs a rightwise bitshift of this number, effectively dividing
838    /// it by 2.
839    /// # Example
840    ///
841    /// ```
842    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
843    ///
844    /// // Basic
845    /// let (mut two, mut four_div) = (B::from(2u64), B::from(4u64));
846    /// four_div.div2();
847    /// assert_eq!(two, four_div);
848    ///
849    /// // Edge-Case
850    /// let mut zero = B::from(0u64);
851    /// zero.div2();
852    /// assert_eq!(zero, B::from(0u64));
853    ///
854    /// let mut one = B::from(1u64);
855    /// one.div2();
856    /// assert_eq!(one, B::from(0u64));
857    /// ```
858    fn div2(&mut self);
859
860    /// Performs a rightwise bitshift of this number by some amount.
861    /// # Example
862    ///
863    /// ```
864    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
865    ///
866    /// // Basic
867    /// let (mut one, mut thirty_two_div) = (B::from(1u64), B::from(32u64));
868    /// thirty_two_div.divn(5);
869    /// assert_eq!(one, thirty_two_div);
870    ///
871    /// // Edge-Case
872    /// let mut arr: [bool; 64] = [false; 64];
873    /// arr[4] = true;
874    /// let mut div = B::from_bits_le(&arr);
875    /// div.divn(5);
876    /// assert_eq!(div, B::from(0u64));
877    /// ```
878    fn divn(&mut self, amt: u32);
879
880    /// Returns true iff this number is odd.
881    /// # Example
882    ///
883    /// ```
884    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
885    ///
886    /// let mut one = B::from(1u64);
887    /// assert!(one.is_odd());
888    /// ```
889    fn is_odd(&self) -> bool;
890
891    /// Returns true iff this number is even.
892    /// # Example
893    ///
894    /// ```
895    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
896    ///
897    /// let mut two = B::from(2u64);
898    /// assert!(two.is_even());
899    /// ```
900    fn is_even(&self) -> bool;
901
902    /// Returns true iff this number is zero.
903    /// # Example
904    ///
905    /// ```
906    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
907    ///
908    /// let mut zero = B::from(0u64);
909    /// assert!(zero.is_zero());
910    /// ```
911    fn is_zero(&self) -> bool;
912
913    /// Compute the minimum number of bits needed to encode this number.
914    /// # Example
915    /// ```
916    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
917    ///
918    /// let zero = B::from(0u64);
919    /// assert_eq!(zero.num_bits(), 0);
920    /// let one = B::from(1u64);
921    /// assert_eq!(one.num_bits(), 1);
922    /// let max = B::from(u64::MAX);
923    /// assert_eq!(max.num_bits(), 64);
924    /// let u32_max = B::from(u32::MAX as u64);
925    /// assert_eq!(u32_max.num_bits(), 32);
926    /// ```
927    fn num_bits(&self) -> u32;
928
929    /// Compute the `i`-th bit of `self`.
930    /// # Example
931    ///
932    /// ```
933    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
934    ///
935    /// let mut one = B::from(1u64);
936    /// assert!(one.get_bit(0));
937    /// assert!(!one.get_bit(1));
938    /// ```
939    fn get_bit(&self, i: usize) -> bool;
940
941    /// Returns the big integer representation of a given big endian boolean
942    /// array.
943    /// # Example
944    ///
945    /// ```
946    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
947    ///
948    /// let mut arr: [bool; 64] = [false; 64];
949    /// arr[63] = true;
950    /// let mut one = B::from(1u64);
951    /// assert_eq!(B::from_bits_be(&arr), one);
952    /// ```   
953    fn from_bits_be(bits: &[bool]) -> Self;
954
955    /// Returns the big integer representation of a given little endian boolean
956    /// array.
957    /// # Example
958    ///
959    /// ```
960    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
961    ///
962    /// let mut arr: [bool; 64] = [false; 64];
963    /// arr[0] = true;
964    /// let mut one = B::from(1u64);
965    /// assert_eq!(B::from_bits_le(&arr), one);
966    /// ```   
967    fn from_bits_le(bits: &[bool]) -> Self;
968
969    /// Returns the bit representation in a big endian boolean array,
970    /// with leading zeroes.
971    /// # Example
972    ///
973    /// ```
974    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
975    ///
976    /// let one = B::from(1u64);
977    /// let arr = one.to_bits_be();
978    /// let mut vec = vec![false; 64];
979    /// vec[63] = true;
980    /// assert_eq!(arr, vec);
981    /// ```  
982    fn to_bits_be(&self) -> Vec<bool> {
983        BitIteratorBE::new(self).collect::<Vec<_>>()
984    }
985
986    /// Returns the bit representation in a little endian boolean array,
987    /// with trailing zeroes.
988    /// # Example
989    ///
990    /// ```
991    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
992    ///
993    /// let one = B::from(1u64);
994    /// let arr = one.to_bits_le();
995    /// let mut vec = vec![false; 64];
996    /// vec[0] = true;
997    /// assert_eq!(arr, vec);
998    /// ```
999    fn to_bits_le(&self) -> Vec<bool> {
1000        BitIteratorLE::new(self).collect::<Vec<_>>()
1001    }
1002
1003    /// Returns the byte representation in a big endian byte array,
1004    /// with leading zeros.
1005    /// # Example
1006    ///
1007    /// ```
1008    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
1009    ///
1010    /// let one = B::from(1u64);
1011    /// let arr = one.to_bytes_be();
1012    /// let mut vec = vec![0; 8];
1013    /// vec[7] = 1;
1014    /// assert_eq!(arr, vec);
1015    /// ```
1016    fn to_bytes_be(&self) -> Vec<u8>;
1017
1018    /// Returns the byte representation in a little endian byte array,
1019    /// with trailing zeros.
1020    /// # Example
1021    ///
1022    /// ```
1023    /// use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};
1024    ///
1025    /// let one = B::from(1u64);
1026    /// let arr = one.to_bytes_le();
1027    /// let mut vec = vec![0; 8];
1028    /// vec[0] = 1;
1029    /// assert_eq!(arr, vec);
1030    /// ```
1031    fn to_bytes_le(&self) -> Vec<u8>;
1032
1033    /// Returns the windowed non-adjacent form of `self`, for a window of size `w`.
1034    fn find_wnaf(&self, w: usize) -> Option<Vec<i64>> {
1035        // w > 2 due to definition of wNAF, and w < 64 to make sure that `i64`
1036        // can fit each signed digit
1037        if (2..64).contains(&w) {
1038            let mut res = vec![];
1039            let mut e = *self;
1040
1041            while !e.is_zero() {
1042                let z: i64;
1043                if e.is_odd() {
1044                    z = signed_mod_reduction(e.as_ref()[0], 1 << w);
1045                    if z >= 0 {
1046                        e.sub_with_borrow(&Self::from(z as u64));
1047                    } else {
1048                        e.add_with_carry(&Self::from((-z) as u64));
1049                    }
1050                } else {
1051                    z = 0;
1052                }
1053                res.push(z);
1054                e.div2();
1055            }
1056
1057            Some(res)
1058        } else {
1059            None
1060        }
1061    }
1062}
ark_ff/biginteger/mod.rs

ark_ff/biginteger/
mod.rs
