ark_ff/biginteger/
mod.rs

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

ark_ff/biginteger/
mod.rs
