jaulib v1.3.0
Jau Support Library (C++, Java, ..)
Classes | Public Types | Public Member Functions | Static Public Member Functions | List of all members
jau::mp::BigInt Class Reference

Arbitrary precision integer type. More...

#include <big_int.hpp>

Collaboration diagram for jau::mp::BigInt:

Public Types

enum  sign_t { negative = 0 , positive = 1 }
 Sign symbol definitions for positive and negative numbers. More...
 

Public Member Functions

 BigInt () noexcept=default
 
 BigInt (BigInt &&other) noexcept
 
 BigInt (const BigInt &o) noexcept=default
 
 BigInt (const std::string &str)
 Construct a big_int_t from a string encoded as hexadecimal or decimal. More...
 
 BigInt (const uint8_t buf[], size_t byte_len, const lb_endian_t byte_order)
 Create a big_int_t from an integer in a byte array with given byte_len, considering the given byte_order. More...
 
 BigInt (std::vector< mp_word_t > &&other_reg) noexcept
 
 BigInt (uint64_t n)
 Create big_int_t from an unsigned 64 bit integer. More...
 
 ~BigInt () noexcept=default
 
BigInt abs () const noexcept
 Returns absolute (positive) value of this instance. More...
 
size_t binary_encode (uint8_t output[], size_t byte_len, const lb_endian_t byte_order) const noexcept
 Stores this number to the value in buf with given byte_len, considering the given byte_order. More...
 
size_t bits () const noexcept
 Returns bit length of this integer. More...
 
uint8_t byte_at (size_t n) const noexcept
 
size_t bytes () const
 Returns byte length of this integer. More...
 
void clear ()
 Zeroize the big_int. More...
 
int compare (const BigInt &b) const noexcept
 Compares this instance against other considering both sign() value Returns. More...
 
void conditionally_set_bit (size_t n, bool set_it) noexcept
 Conditionally set bit at specified position. More...
 
const mp_word_tdata () const
 Return a const pointer to the register. More...
 
BigIntflip_sign () noexcept
 Flip the sign of this big_int. More...
 
bool get_bit (size_t n) const noexcept
 Return bit value at specified position. More...
 
bool is_even () const noexcept
 Test if the integer has an even value. More...
 
bool is_negative () const noexcept
 Tests if the sign of the integer is negative. More...
 
bool is_nonzero () const noexcept
 Test if the integer is not zero. More...
 
bool is_odd () const noexcept
 Test if the integer has an odd value. More...
 
bool is_positive () const noexcept
 Tests if the sign of the integer is positive. More...
 
bool is_zero () const noexcept
 Test if the integer is zero. More...
 
BigIntmod_add (const BigInt &y, const BigInt &mod, std::vector< mp_word_t > &ws)
 Set *this to (*this + y) % mod This function assumes *this is >= 0 && < mod. More...
 
BigIntmod_mul (uint8_t y, const BigInt &mod, std::vector< mp_word_t > &ws)
 Set *this to (*this * y) % mod This function assumes *this is >= 0 && < mod y should be small, less than 16. More...
 
BigInt mod_pow (BigInt e, BigInt m)
 Returns (*this)^e % m, or pow(*this, e) % m. More...
 
BigIntmod_sub (const BigInt &y, const BigInt &mod, std::vector< mp_word_t > &ws)
 Set *this to (*this - y) % mod This function assumes *this is >= 0 && < mod. More...
 
bool operator! () const noexcept
 ! operator, returns true iff this is zero, otherwise false. More...
 
bool operator!= (const BigInt &b) const noexcept
 
BigInt operator% (const BigInt &mod)
 
BigIntoperator%= (const BigInt &mod)
 Modulo operator. More...
 
BigInt operator* (const BigInt &y) noexcept
 
BigIntoperator*= (const BigInt &y) noexcept
 
BigInt operator+ (const BigInt &y) const noexcept
 
BigIntoperator++ () noexcept
 
BigInt operator++ (int) noexcept
 
BigIntoperator+= (const BigInt &y) noexcept
 
BigInt operator- () const noexcept
 Unary negation operator, returns new negative instance of this. More...
 
BigInt operator- (const BigInt &y) const noexcept
 
BigIntoperator-- () noexcept
 
BigInt operator-- (int) noexcept
 
BigIntoperator-= (const BigInt &y) noexcept
 
BigInt operator/ (const BigInt &y) const
 
BigIntoperator/= (const BigInt &y)
 
bool operator< (const BigInt &b) const noexcept
 
BigInt operator<< (size_t shift) const
 
BigIntoperator<<= (size_t shift) noexcept
 
bool operator<= (const BigInt &b) const noexcept
 
BigIntoperator= (BigInt &&other) noexcept
 
BigIntoperator= (const BigInt &r)=default
 
bool operator== (const BigInt &b) const noexcept
 
bool operator> (const BigInt &b) const noexcept
 
bool operator>= (const BigInt &b) const noexcept
 
BigInt operator>> (size_t shift) const
 
BigIntoperator>>= (size_t shift) noexcept
 
BigInt pow (BigInt e)
 Returns (*this)^e, or pow(*this, e) More...
 
BigIntrev_sub (const BigInt &y, std::vector< mp_word_t > &ws)
 Set *this to y - *this. More...
 
sign_t reverse_sign () const noexcept
 
void set_bit (size_t n) noexcept
 Set bit at specified position. More...
 
BigIntset_sign (sign_t sign) noexcept
 Set sign of the integer. More...
 
size_t sig_words () const noexcept
 Return how many words we need to hold this value. More...
 
sign_t sign () const noexcept
 Return the sign of the integer. More...
 
size_t size () const noexcept
 Give size of internal register. More...
 
BigIntsquare (std::vector< mp_word_t > &ws)
 Square value of *this. More...
 
void swap (BigInt &other) noexcept
 Swap this value with another. More...
 
std::string to_dec_string (bool add_details=false) const noexcept
 
std::string to_hex_string (bool add_details=false) const noexcept
 
mp_word_t word_at (size_t n) const noexcept
 Return the mp_word_t at a specified position of the internal register. More...
 

Static Public Member Functions

static BigInt from_s32 (int32_t n)
 Create big_int from a signed 32 bit integer. More...
 
static BigInt from_u64 (uint64_t n)
 Create big_int from an unsigned 64 bit integer. More...
 
static BigInt from_word (mp_word_t n)
 Create big_int from a mp_word_t (limb) More...
 
static BigInt one ()
 Create a 1-value big_int. More...
 
static BigInt power_of_2 (size_t n)
 Create a power of two. More...
 
static BigInt with_capacity (size_t n)
 Create big_int of specified size, all zeros. More...
 
static BigInt zero ()
 Create a 0-value big_int. More...
 

Detailed Description

Arbitrary precision integer type.

Local storage format

Internally the big integer is stored in an array of mp_word_t ordered little-endian alike, with the least significant word at the array-bottom and most significant word at the array-top.

The mp_word_t itself is stored in jau::endian::native!

Definition at line 43 of file big_int.hpp.

Member Enumeration Documentation

◆ sign_t

Sign symbol definitions for positive and negative numbers.

Enumerator
negative 
positive 

Definition at line 48 of file big_int.hpp.

Constructor & Destructor Documentation

◆ BigInt() [1/7]

jau::mp::BigInt::BigInt ( )
defaultnoexcept
Here is the caller graph for this function:

◆ BigInt() [2/7]

jau::mp::BigInt::BigInt ( const BigInt o)
defaultnoexcept

◆ ~BigInt()

jau::mp::BigInt::~BigInt ( )
defaultnoexcept

◆ BigInt() [3/7]

jau::mp::BigInt::BigInt ( uint64_t  n)
inline

Create big_int_t from an unsigned 64 bit integer.

Parameters
ninitial value of this big_int_t

Definition at line 129 of file big_int.hpp.

◆ BigInt() [4/7]

jau::mp::BigInt::BigInt ( const std::string &  str)
inline

Construct a big_int_t from a string encoded as hexadecimal or decimal.

Both number bases may lead a -, denoting a negative number.

Hexadecimal is detected by a leading 0x.

Definition at line 145 of file big_int.hpp.

◆ BigInt() [5/7]

jau::mp::BigInt::BigInt ( const uint8_t  buf[],
size_t  byte_len,
const lb_endian_t  byte_order 
)
inline

Create a big_int_t from an integer in a byte array with given byte_len, considering the given byte_order.

The value is stored in the local storage format, see bigint_storage_format

Parameters
bufthe byte array holding the value
byte_lensize of buf in bytes
littleEndian

Definition at line 178 of file big_int.hpp.

◆ BigInt() [6/7]

jau::mp::BigInt::BigInt ( std::vector< mp_word_t > &&  other_reg)
inlinenoexcept

Definition at line 182 of file big_int.hpp.

◆ BigInt() [7/7]

jau::mp::BigInt::BigInt ( BigInt &&  other)
inlinenoexcept

Definition at line 186 of file big_int.hpp.

Member Function Documentation

◆ zero()

static BigInt jau::mp::BigInt::zero ( )
inlinestatic

Create a 0-value big_int.

Definition at line 60 of file big_int.hpp.

Here is the caller graph for this function:

◆ one()

static BigInt jau::mp::BigInt::one ( )
inlinestatic

Create a 1-value big_int.

Definition at line 65 of file big_int.hpp.

Here is the caller graph for this function:

◆ from_u64()

static BigInt jau::mp::BigInt::from_u64 ( uint64_t  n)
inlinestatic

Create big_int from an unsigned 64 bit integer.

Parameters
ninitial value of this big_int

Definition at line 71 of file big_int.hpp.

Here is the caller graph for this function:

◆ from_word()

static BigInt jau::mp::BigInt::from_word ( mp_word_t  n)
inlinestatic

Create big_int from a mp_word_t (limb)

Parameters
ninitial value of this big_int

Definition at line 86 of file big_int.hpp.

Here is the caller graph for this function:

◆ from_s32()

static BigInt jau::mp::BigInt::from_s32 ( int32_t  n)
inlinestatic

Create big_int from a signed 32 bit integer.

Parameters
ninitial value of this big_int

Definition at line 96 of file big_int.hpp.

◆ with_capacity()

static BigInt jau::mp::BigInt::with_capacity ( size_t  n)
inlinestatic

Create big_int of specified size, all zeros.

Parameters
nsize of the internal register in words

Definition at line 108 of file big_int.hpp.

Here is the caller graph for this function:

◆ power_of_2()

static BigInt jau::mp::BigInt::power_of_2 ( size_t  n)
inlinestatic

Create a power of two.

Parameters
nthe power of two to create
Returns
big_int_t representing 2^n

Definition at line 119 of file big_int.hpp.

◆ operator=() [1/2]

BigInt & jau::mp::BigInt::operator= ( const BigInt r)
default

◆ operator=() [2/2]

BigInt & jau::mp::BigInt::operator= ( BigInt &&  other)
inlinenoexcept

Definition at line 192 of file big_int.hpp.

◆ swap()

void jau::mp::BigInt::swap ( BigInt other)
inlinenoexcept

Swap this value with another.

Parameters
otherbig_int to swap values with

Definition at line 203 of file big_int.hpp.

Here is the caller graph for this function:

◆ operator-() [1/2]

BigInt jau::mp::BigInt::operator- ( ) const
inlinenoexcept

Unary negation operator, returns new negative instance of this.

Definition at line 216 of file big_int.hpp.

◆ byte_at()

uint8_t jau::mp::BigInt::byte_at ( size_t  n) const
inlinenoexcept
Parameters
nthe offset to get a byte from
Returns
byte at offset n

Definition at line 222 of file big_int.hpp.

Here is the caller graph for this function:

◆ word_at()

mp_word_t jau::mp::BigInt::word_at ( size_t  n) const
inlinenoexcept

Return the mp_word_t at a specified position of the internal register.

Parameters
nposition in the register
Returns
value at position n

Definition at line 232 of file big_int.hpp.

Here is the caller graph for this function:

◆ data()

const mp_word_t * jau::mp::BigInt::data ( ) const
inline

Return a const pointer to the register.

Returns
a pointer to the start of the internal register

Definition at line 240 of file big_int.hpp.

Here is the caller graph for this function:

◆ is_negative()

bool jau::mp::BigInt::is_negative ( ) const
inlinenoexcept

Tests if the sign of the integer is negative.

Returns
true, iff the integer has a negative sign

Definition at line 246 of file big_int.hpp.

Here is the caller graph for this function:

◆ is_positive()

bool jau::mp::BigInt::is_positive ( ) const
inlinenoexcept

Tests if the sign of the integer is positive.

Returns
true, iff the integer has a positive sign

Definition at line 252 of file big_int.hpp.

Here is the caller graph for this function:

◆ sign()

sign_t jau::mp::BigInt::sign ( ) const
inlinenoexcept

Return the sign of the integer.

Returns
the sign of the integer

Definition at line 258 of file big_int.hpp.

Here is the caller graph for this function:

◆ reverse_sign()

sign_t jau::mp::BigInt::reverse_sign ( ) const
inlinenoexcept
Returns
the opposite sign of the represented integer value

Definition at line 263 of file big_int.hpp.

Here is the caller graph for this function:

◆ flip_sign()

BigInt & jau::mp::BigInt::flip_sign ( )
inlinenoexcept

Flip the sign of this big_int.

Definition at line 273 of file big_int.hpp.

Here is the caller graph for this function:

◆ set_sign()

BigInt & jau::mp::BigInt::set_sign ( sign_t  sign)
inlinenoexcept

Set sign of the integer.

Parameters
signnew Sign to set

Definition at line 281 of file big_int.hpp.

Here is the caller graph for this function:

◆ abs()

BigInt jau::mp::BigInt::abs ( ) const
inlinenoexcept

Returns absolute (positive) value of this instance.

Definition at line 290 of file big_int.hpp.

◆ size()

size_t jau::mp::BigInt::size ( ) const
inlinenoexcept

Give size of internal register.

Returns
size of internal register in words

Definition at line 298 of file big_int.hpp.

Here is the caller graph for this function:

◆ sig_words()

size_t jau::mp::BigInt::sig_words ( ) const
inlinenoexcept

Return how many words we need to hold this value.

Returns
significant words of the represented integer value

Definition at line 304 of file big_int.hpp.

Here is the caller graph for this function:

◆ bytes()

size_t jau::mp::BigInt::bytes ( ) const
inline

Returns byte length of this integer.

Definition at line 307 of file big_int.hpp.

Here is the caller graph for this function:

◆ bits()

size_t jau::mp::BigInt::bits ( ) const
inlinenoexcept

Returns bit length of this integer.

Definition at line 310 of file big_int.hpp.

Here is the caller graph for this function:

◆ clear()

void jau::mp::BigInt::clear ( )
inline

Zeroize the big_int.

The size of the underlying register is not modified.

Definition at line 324 of file big_int.hpp.

◆ compare()

int jau::mp::BigInt::compare ( const BigInt b) const
inlinenoexcept

Compares this instance against other considering both sign() value Returns.

  • -1 if this < other
  • 0 if this == other
  • 1 if this > other

Definition at line 333 of file big_int.hpp.

◆ is_even()

bool jau::mp::BigInt::is_even ( ) const
inlinenoexcept

Test if the integer has an even value.

Returns
true if the integer is even, false otherwise

Definition at line 341 of file big_int.hpp.

◆ is_odd()

bool jau::mp::BigInt::is_odd ( ) const
inlinenoexcept

Test if the integer has an odd value.

Returns
true if the integer is odd, false otherwise

Definition at line 347 of file big_int.hpp.

◆ is_nonzero()

bool jau::mp::BigInt::is_nonzero ( ) const
inlinenoexcept

Test if the integer is not zero.

Returns
true if the integer is non-zero, false otherwise

Definition at line 353 of file big_int.hpp.

Here is the caller graph for this function:

◆ is_zero()

bool jau::mp::BigInt::is_zero ( ) const
inlinenoexcept

Test if the integer is zero.

Returns
true if the integer is zero, false otherwise

Definition at line 359 of file big_int.hpp.

Here is the caller graph for this function:

◆ get_bit()

bool jau::mp::BigInt::get_bit ( size_t  n) const
inlinenoexcept

Return bit value at specified position.

Parameters
nthe bit offset to test
Returns
true, if the bit at position n is set, false otherwise

Definition at line 368 of file big_int.hpp.

Here is the caller graph for this function:

◆ set_bit()

void jau::mp::BigInt::set_bit ( size_t  n)
inlinenoexcept

Set bit at specified position.

Parameters
nbit position to set

Definition at line 376 of file big_int.hpp.

Here is the caller graph for this function:

◆ conditionally_set_bit()

void jau::mp::BigInt::conditionally_set_bit ( size_t  n,
bool  set_it 
)
inlinenoexcept

Conditionally set bit at specified position.

Note if set_it is false, nothing happens, and if the bit is already set, it remains set.

Parameters
nbit position to set
set_itif the bit should be set

Definition at line 388 of file big_int.hpp.

Here is the caller graph for this function:

◆ operator!()

bool jau::mp::BigInt::operator! ( ) const
inlinenoexcept

! operator, returns true iff this is zero, otherwise false.

Definition at line 395 of file big_int.hpp.

◆ operator==()

bool jau::mp::BigInt::operator== ( const BigInt b) const
inlinenoexcept

Definition at line 397 of file big_int.hpp.

◆ operator!=()

bool jau::mp::BigInt::operator!= ( const BigInt b) const
inlinenoexcept

Definition at line 398 of file big_int.hpp.

◆ operator<=()

bool jau::mp::BigInt::operator<= ( const BigInt b) const
inlinenoexcept

Definition at line 399 of file big_int.hpp.

◆ operator>=()

bool jau::mp::BigInt::operator>= ( const BigInt b) const
inlinenoexcept

Definition at line 400 of file big_int.hpp.

◆ operator<()

bool jau::mp::BigInt::operator< ( const BigInt b) const
inlinenoexcept

Definition at line 401 of file big_int.hpp.

◆ operator>()

bool jau::mp::BigInt::operator> ( const BigInt b) const
inlinenoexcept

Definition at line 402 of file big_int.hpp.

◆ operator++() [1/2]

BigInt & jau::mp::BigInt::operator++ ( )
inlinenoexcept

Definition at line 410 of file big_int.hpp.

◆ operator--() [1/2]

BigInt & jau::mp::BigInt::operator-- ( )
inlinenoexcept

Definition at line 412 of file big_int.hpp.

◆ operator++() [2/2]

BigInt jau::mp::BigInt::operator++ ( int  )
inlinenoexcept

Definition at line 414 of file big_int.hpp.

◆ operator--() [2/2]

BigInt jau::mp::BigInt::operator-- ( int  )
inlinenoexcept

Definition at line 416 of file big_int.hpp.

◆ operator+=()

BigInt & jau::mp::BigInt::operator+= ( const BigInt y)
inlinenoexcept

Definition at line 418 of file big_int.hpp.

◆ operator-=()

BigInt & jau::mp::BigInt::operator-= ( const BigInt y)
inlinenoexcept

Definition at line 422 of file big_int.hpp.

◆ operator+()

BigInt jau::mp::BigInt::operator+ ( const BigInt y) const
inlinenoexcept

Definition at line 426 of file big_int.hpp.

◆ operator-() [2/2]

BigInt jau::mp::BigInt::operator- ( const BigInt y) const
inlinenoexcept

Definition at line 430 of file big_int.hpp.

◆ operator<<=()

BigInt & jau::mp::BigInt::operator<<= ( size_t  shift)
inlinenoexcept

Definition at line 434 of file big_int.hpp.

◆ operator>>=()

BigInt & jau::mp::BigInt::operator>>= ( size_t  shift)
inlinenoexcept

Definition at line 450 of file big_int.hpp.

◆ operator<<()

BigInt jau::mp::BigInt::operator<< ( size_t  shift) const
inline

Definition at line 462 of file big_int.hpp.

◆ operator>>()

BigInt jau::mp::BigInt::operator>> ( size_t  shift) const
inline

Definition at line 473 of file big_int.hpp.

◆ operator*=()

BigInt & jau::mp::BigInt::operator*= ( const BigInt y)
inlinenoexcept

Definition at line 494 of file big_int.hpp.

◆ operator*()

BigInt jau::mp::BigInt::operator* ( const BigInt y)
inlinenoexcept

Definition at line 499 of file big_int.hpp.

◆ operator/=()

BigInt & jau::mp::BigInt::operator/= ( const BigInt y)
inline

Definition at line 518 of file big_int.hpp.

◆ operator/()

BigInt jau::mp::BigInt::operator/ ( const BigInt y) const
inline

Definition at line 527 of file big_int.hpp.

◆ operator%=()

BigInt & jau::mp::BigInt::operator%= ( const BigInt mod)
inline

Modulo operator.

Parameters
ythe modulus to reduce this by

Definition at line 539 of file big_int.hpp.

◆ operator%()

BigInt jau::mp::BigInt::operator% ( const BigInt mod)
inline

Definition at line 543 of file big_int.hpp.

◆ pow()

BigInt jau::mp::BigInt::pow ( BigInt  e)
inline

Returns (*this)^e, or pow(*this, e)

Implementation is not optimized and naive, i.e. O(n)

Parameters
ethe exponent

Definition at line 568 of file big_int.hpp.

Here is the caller graph for this function:

◆ mod_pow()

BigInt jau::mp::BigInt::mod_pow ( BigInt  e,
BigInt  m 
)
inline

Returns (*this)^e % m, or pow(*this, e) % m.

Implementation is not optimized and naive, i.e. O(n)

Parameters
ethe exponent

Definition at line 602 of file big_int.hpp.

Here is the caller graph for this function:

◆ square()

BigInt & jau::mp::BigInt::square ( std::vector< mp_word_t > &  ws)

Square value of *this.

Parameters
wsa temp workspace

◆ rev_sub()

BigInt & jau::mp::BigInt::rev_sub ( const BigInt y,
std::vector< mp_word_t > &  ws 
)

Set *this to y - *this.

Parameters
ythe big_int_t to subtract from
wsa temp workspace

◆ mod_add()

BigInt & jau::mp::BigInt::mod_add ( const BigInt y,
const BigInt mod,
std::vector< mp_word_t > &  ws 
)

Set *this to (*this + y) % mod This function assumes *this is >= 0 && < mod.

Parameters
ythe big_int_t to add - assumed y >= 0 and y < mod
modthe positive modulus
wsa temp workspace

◆ mod_sub()

BigInt & jau::mp::BigInt::mod_sub ( const BigInt y,
const BigInt mod,
std::vector< mp_word_t > &  ws 
)

Set *this to (*this - y) % mod This function assumes *this is >= 0 && < mod.

Parameters
ythe big_int_t to subtract - assumed y >= 0 and y < mod
modthe positive modulus
wsa temp workspace

◆ mod_mul()

BigInt & jau::mp::BigInt::mod_mul ( uint8_t  y,
const BigInt mod,
std::vector< mp_word_t > &  ws 
)

Set *this to (*this * y) % mod This function assumes *this is >= 0 && < mod y should be small, less than 16.

Parameters
ythe small integer to multiply by
modthe positive modulus
wsa temp workspace

◆ to_dec_string()

std::string jau::mp::BigInt::to_dec_string ( bool  add_details = false) const
inlinenoexcept
Parameters
rnga random number generator
minthe minimum value (must be non-negative)
maxthe maximum value (must be non-negative and > min)
Returns
random integer in [min,max) static big_int_t random_integer(RandomNumberGenerator& rng, const big_int_t& min, const big_int_t& max); // TODO

Definition at line 681 of file big_int.hpp.

Here is the caller graph for this function:

◆ to_hex_string()

std::string jau::mp::BigInt::to_hex_string ( bool  add_details = false) const
inlinenoexcept

Definition at line 754 of file big_int.hpp.

Here is the caller graph for this function:

◆ binary_encode()

size_t jau::mp::BigInt::binary_encode ( uint8_t  output[],
size_t  byte_len,
const lb_endian_t  byte_order 
) const
inlinenoexcept

Stores this number to the value in buf with given byte_len, considering the given byte_order.

The value is read from the local storage in its format, see bigint_storage_format

If byte_len is less than the byt-esize of this integer, i.e. bytes(), then it will be truncated.

If byte_len is greater than the byte-size of this integer, i.e. bytes(), it will be zero-padded.

Returns
actual number of bytes copied, i.e. min(byte_len, bytes());

Definition at line 1119 of file big_int.hpp.

Here is the caller graph for this function:

The documentation for this class was generated from the following file: