Trait ark_ff::biginteger::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 = ()> + Into<BigUint> {
    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 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)

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 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)

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.

Implementors

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

const NUM_LIMBS: usize = N