Trait BigInteger 

pub trait BigInteger:
    CanonicalSerialize
    + CanonicalDeserialize
    + Copy
    + Clone
    + Debug
    + Default
    + Display
    + Eq
    + Ord
    + Send
    + Sized
    + Sync
    + 'static
    + UniformRand
    + Zeroize
    + AsMut<[u64]>
    + AsRef<[u64]>
    + From<u64>
    + From<u32>
    + From<u16>
    + From<u8>
    + TryFrom<BigUint, Error = ()>
    + FromStr
    + Into<BigUint>
    + BitXorAssign<Self>
    + for<'a> BitXorAssign<&'a Self>
    + BitXor<Self, Output = Self>
    + for<'a> BitXor<&'a Self, Output = Self>
    + BitAndAssign<Self>
    + for<'a> BitAndAssign<&'a Self>
    + BitAnd<Self, Output = Self>
    + for<'a> BitAnd<&'a Self, Output = Self>
    + BitOrAssign<Self>
    + for<'a> BitOrAssign<&'a Self>
    + BitOr<Self, Output = Self>
    + for<'a> BitOr<&'a Self, Output = Self>
    + Shr<u32, Output = Self>
    + ShrAssign<u32>
    + Shl<u32, Output = Self>
    + ShlAssign<u32> {
    const NUM_LIMBS: usize;

    // Required methods
    fn add_with_carry(&mut self, other: &Self) -> bool;
    fn sub_with_borrow(&mut self, other: &Self) -> bool;
    fn mul2(&mut self) -> bool;
    fn muln(&mut self, amt: u32);
    fn mul_low(&self, other: &Self) -> Self;
    fn mul_high(&self, other: &Self) -> Self;
    fn mul(&self, other: &Self) -> (Self, Self);
    fn div2(&mut self);
    fn divn(&mut self, amt: u32);
    fn is_odd(&self) -> bool;
    fn is_even(&self) -> bool;
    fn is_zero(&self) -> bool;
    fn num_bits(&self) -> u32;
    fn get_bit(&self, i: usize) -> bool;
    fn from_bits_be(bits: &[bool]) -> Self;
    fn from_bits_le(bits: &[bool]) -> Self;
    fn to_bytes_be(&self) -> Vec<u8> ;
    fn to_bytes_le(&self) -> Vec<u8> ;

    // Provided methods
    fn to_bits_be(&self) -> Vec<bool> { ... }
    fn to_bits_le(&self) -> Vec<bool> { ... }
    fn find_wnaf(&self, w: usize) -> Option<Vec<i64>> { ... }
}

This defines a BigInteger, a smart wrapper around a sequence of u64 limbs, least-significant limb first.

Required Associated Constants

const NUM_LIMBS: usize

Number of 64-bit limbs representing Self.

Required Methods

fn add_with_carry(&mut self, other: &Self) -> bool

Add another BigInteger to self. This method stores the result in self, and returns a carry bit.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

// Basic
let (mut one, mut x) = (B::from(1u64), B::from(2u64));
let carry = x.add_with_carry(&one);
assert_eq!(x, B::from(3u64));
assert_eq!(carry, false);

// Edge-Case
let mut x = B::from(u64::MAX);
let carry = x.add_with_carry(&one);
assert_eq!(x, B::from(0u64));
assert_eq!(carry, true)

fn sub_with_borrow(&mut self, other: &Self) -> bool

Subtract another BigInteger from this one. This method stores the result in self, and returns a borrow.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

// Basic
let (mut one_sub, two, mut three_sub) = (B::from(1u64), B::from(2u64), B::from(3u64));
let borrow = three_sub.sub_with_borrow(&two);
assert_eq!(three_sub, one_sub);
assert_eq!(borrow, false);

// Edge-Case
let borrow = one_sub.sub_with_borrow(&two);
assert_eq!(one_sub, B::from(u64::MAX));
assert_eq!(borrow, true);

fn mul2(&mut self) -> bool

Performs a leftwise bitshift of this number, effectively multiplying it by 2. Overflow is ignored.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

// Basic
let mut two_mul = B::from(2u64);
two_mul.mul2();
assert_eq!(two_mul, B::from(4u64));

// Edge-Cases
let mut zero = B::from(0u64);
zero.mul2();
assert_eq!(zero, B::from(0u64));

let mut arr: [bool; 64] = [false; 64];
arr[0] = true;
let mut mul = B::from_bits_be(&arr);
mul.mul2();
assert_eq!(mul, B::from(0u64));

fn muln(&mut self, amt: u32)

👎Deprecated since 0.4.2:

please use the operator << instead

Performs a leftwise bitshift of this number by n bits, effectively multiplying it by 2^n. Overflow is ignored.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

// Basic
let mut one_mul = B::from(1u64);
one_mul.muln(5);
assert_eq!(one_mul, B::from(32u64));

// Edge-Case
let mut zero = B::from(0u64);
zero.muln(5);
assert_eq!(zero, B::from(0u64));

let mut arr: [bool; 64] = [false; 64];
arr[4] = true;
let mut mul = B::from_bits_be(&arr);
mul.muln(5);
assert_eq!(mul, B::from(0u64));

fn mul_low(&self, other: &Self) -> Self

Multiplies this BigInteger by another BigInteger, storing the result in self. Overflow is ignored.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

// Basic
let mut a = B::from(42u64);
let b = B::from(3u64);
assert_eq!(a.mul_low(&b), B::from(126u64));

// Edge-Case
let mut zero = B::from(0u64);
assert_eq!(zero.mul_low(&B::from(5u64)), B::from(0u64));

fn mul_high(&self, other: &Self) -> Self

Multiplies this BigInteger by another BigInteger, returning the high bits of the result.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

// Basic
let (one, x) = (B::from(1u64), B::from(2u64));
let r = x.mul_high(&one);
assert_eq!(r, B::from(0u64));

// Edge-Case
let mut x = B::from(u64::MAX);
let r = x.mul_high(&B::from(2u64));
assert_eq!(r, B::from(1u64))

fn mul(&self, other: &Self) -> (Self, Self)

Multiplies this BigInteger by another BigInteger, returning both low and high bits of the result.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

// Basic
let mut a = B::from(42u64);
let b = B::from(3u64);
let (low_bits, high_bits) = a.mul(&b);
assert_eq!(low_bits, B::from(126u64));
assert_eq!(high_bits, B::from(0u64));

// Edge-Case
let mut x = B::from(u64::MAX);
let mut max_plus_max = x;
max_plus_max.add_with_carry(&x);
let (low_bits, high_bits) = x.mul(&B::from(2u64));
assert_eq!(low_bits, max_plus_max);
assert_eq!(high_bits, B::from(1u64));

fn div2(&mut self)

Performs a rightwise bitshift of this number, effectively dividing it by 2.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

// Basic
let (mut two, mut four_div) = (B::from(2u64), B::from(4u64));
four_div.div2();
assert_eq!(two, four_div);

// Edge-Case
let mut zero = B::from(0u64);
zero.div2();
assert_eq!(zero, B::from(0u64));

let mut one = B::from(1u64);
one.div2();
assert_eq!(one, B::from(0u64));

fn divn(&mut self, amt: u32)

👎Deprecated since 0.4.2:

please use the operator >> instead

Performs a rightwise bitshift of this number by some amount.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

// Basic
let (mut one, mut thirty_two_div) = (B::from(1u64), B::from(32u64));
thirty_two_div.divn(5);
assert_eq!(one, thirty_two_div);

// Edge-Case
let mut arr: [bool; 64] = [false; 64];
arr[4] = true;
let mut div = B::from_bits_le(&arr);
div.divn(5);
assert_eq!(div, B::from(0u64));

fn is_odd(&self) -> bool

Returns true iff this number is odd.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let mut one = B::from(1u64);
assert!(one.is_odd());

fn is_even(&self) -> bool

Returns true iff this number is even.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let mut two = B::from(2u64);
assert!(two.is_even());

fn is_zero(&self) -> bool

Returns true iff this number is zero.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let mut zero = B::from(0u64);
assert!(zero.is_zero());

fn num_bits(&self) -> u32

Compute the minimum number of bits needed to encode this number.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let zero = B::from(0u64);
assert_eq!(zero.num_bits(), 0);
let one = B::from(1u64);
assert_eq!(one.num_bits(), 1);
let max = B::from(u64::MAX);
assert_eq!(max.num_bits(), 64);
let u32_max = B::from(u32::MAX as u64);
assert_eq!(u32_max.num_bits(), 32);

fn get_bit(&self, i: usize) -> bool

Compute the i-th bit of self.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let mut one = B::from(1u64);
assert!(one.get_bit(0));
assert!(!one.get_bit(1));

fn from_bits_be(bits: &[bool]) -> Self

Returns the big integer representation of a given big endian boolean array.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let mut arr: [bool; 64] = [false; 64];
arr[63] = true;
let mut one = B::from(1u64);
assert_eq!(B::from_bits_be(&arr), one);

fn from_bits_le(bits: &[bool]) -> Self

Returns the big integer representation of a given little endian boolean array.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let mut arr: [bool; 64] = [false; 64];
arr[0] = true;
let mut one = B::from(1u64);
assert_eq!(B::from_bits_le(&arr), one);

fn to_bytes_be(&self) -> Vec<u8>

Returns the byte representation in a big endian byte array, with leading zeros.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let one = B::from(1u64);
let arr = one.to_bytes_be();
let mut vec = vec![0; 8];
vec[7] = 1;
assert_eq!(arr, vec);

fn to_bytes_le(&self) -> Vec<u8>

Returns the byte representation in a little endian byte array, with trailing zeros.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let one = B::from(1u64);
let arr = one.to_bytes_le();
let mut vec = vec![0; 8];
vec[0] = 1;
assert_eq!(arr, vec);

Provided Methods

fn to_bits_be(&self) -> Vec<bool>

Returns the bit representation in a big endian boolean array, with leading zeroes.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let one = B::from(1u64);
let arr = one.to_bits_be();
let mut vec = vec![false; 64];
vec[63] = true;
assert_eq!(arr, vec);

fn to_bits_le(&self) -> Vec<bool>

Returns the bit representation in a little endian boolean array, with trailing zeroes.

Example

use ark_ff::{biginteger::BigInteger64 as B, BigInteger as _};

let one = B::from(1u64);
let arr = one.to_bits_le();
let mut vec = vec![false; 64];
vec[0] = true;
assert_eq!(arr, vec);

fn find_wnaf(&self, w: usize) -> Option<Vec<i64>>

Returns the windowed non-adjacent form of self, for a window of size w.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors

impl<const N: usize> BigInteger for BigInt<N>

const NUM_LIMBS: usize = N