math.big

The math.big module provides arbitrary-precision signed integers and arithmetic.

Primality testing

Integer.is_probably_prime(rounds) combines trial division, Miller-Rabin, and a Lucas probable-prime test. For values below 3317044064679887385961981, its fixed Miller-Rabin bases make the result deterministic. Above that bound, it performs every requested random round in addition to the fixed bases, so a composite has probability below 1 / 4^rounds of being reported as probably prime. Passing zero or a negative round count selects the default of 40 rounds.

Use Integer.is_probably_prime_checked(rounds) when an operating-system entropy failure must be distinguished from a composite result. The boolean form fails closed and returns false if entropy is unavailable.

The result remains probabilistic for large values. Protocols that validate untrusted parameters may require additional checks.

import math.big

fn main() {
    n := big.integer_from_string('170141183460469231731687303715884105727')!
    assert n.is_probably_prime(40)
}

big.jacobi(a, n) returns the Jacobi symbol -1, 0, or 1. The modulus n must be positive and odd; invalid moduli cause a panic.

fn integer_from_bytes(oinput []u8, config IntegerConfig) Integer

integer_from_bytes creates a new big.Integer from the given byte array. By default, positive integers are assumed. If you want a negative integer, use in the following manner: value := big.integer_from_bytes(bytes, signum: -1)

fn integer_from_i64(value i64) Integer

integer_from_i64 creates a new big.Integer from the given i64 value.

fn integer_from_int(value int) Integer

integer_from_int creates a new big.Integer from the given int value.

fn integer_from_radix(all_characters string, radix u32) !Integer

integer_from_radix creates a new big.Integer from the given string and radix.

fn integer_from_string(characters string) !Integer

integer_from_string creates a new big.Integer from the decimal digits specified in the given string. For other bases, use big.integer_from_radix instead.

fn integer_from_u32(value u32) Integer

integer_from_u32 creates a new big.Integer from the given u32 value.

fn integer_from_u64(value u64) Integer

integer_from_u64 creates a new big.Integer from the given u64 value.

fn jacobi(a Integer, n Integer) int

jacobi returns the Jacobi symbol (a / n), which is +1, -1 or 0. n must be positive and odd.

struct Integer {
	digits []u64 // in one u64, use only `digit_bits` store a digit
pub:
	signum   int
	is_const bool
}

big.Integer

It has the following properties:1. Every "digit" is an integer in the range [0, 2^digit_bits-1).2. The signum can be one of three values: -1, 0, +1 for negative, zero, and positive values, respectively.3. There should be no leading zeros in the digit array.4. The digits are stored in little endian format, that is, the digits with a lower positional value (towards the right when represented as a string) have a lower index, and vice versa.5. zero's signum is zero, digits.len = 0

fn (dividend Integer) % (divisor Integer) Integer

% returns the remainder of dividend divided by divisor.

WARNING: this method will panic if divisor == 0. For a modular division method that returns a Result refer to mod_checked.

Note: in V, assert big.integer_from_i64(-10) % big.integer_from_i64(7) == big.integer_from_i64(-3) passes. In other words, the result is negative 3, and is NOT positive 4.

fn (multiplicand Integer) * (multiplier Integer) Integer

• returns the product of the integers multiplicand and multiplier.

fn (augend Integer) + (addend Integer) Integer

• returns the sum of the integers augend and addend.

fn (minuend Integer) - (subtrahend Integer) Integer

• returns the difference of the integers minuend and subtrahend

fn (dividend Integer) / (divisor Integer) Integer

/ returns the quotient of dividend divided by divisor.

WARNING: this method will panic if divisor == 0. For a division method that returns a Result refer to div_checked.

fn (a Integer) < (b Integer) bool

< returns true if the integer a is less than b.

fn (a Integer) == (b Integer) bool

== returns true if the integers a and b are equal in value and sign.

fn (a Integer) abs() Integer

abs returns the absolute value of the integer a.

fn (a Integer) abs_cmp(b Integer) int

abs_cmp returns the result of comparing the magnitudes of the integers a and b. It returns a negative int if |a| < |b|, 0 if |a| == |b|, and a positive int if |a| > |b|.

fn (base Integer) big_mod_pow(exponent Integer, modulus Integer) !Integer

big_mod_pow returns the integer base raised to the power of the integer exponent modulo the integer modulus.

fn (integer Integer) bin_str() string

bin_str returns the binary string representation of the integer a.

fn (x Integer) bit_len() int

bit_len returns the number of bits required to represent the integer a.

fn (a Integer) bitwise_and(b Integer) Integer

bitwise_and returns the "bitwise and" of the integers |a| and |b|.

Note: both operands are treated as absolute values.

fn (a Integer) bitwise_com() Integer

bitwise_com returns "bitwise complement" of integer a.

Note: this function consider the sign of the input.

fn (a Integer) bitwise_not() Integer

bitwise_not returns the "bitwise not" of the integer |a|.

Note: the integer is treated as an absolute value.

fn (a Integer) bitwise_or(b Integer) Integer

bitwise_or returns the "bitwise or" of the integers |a| and |b|.

Note: both operands are treated as absolute values.

fn (a Integer) bitwise_xor(b Integer) Integer

bitwise_xor returns the "bitwise exclusive or" of the integers |a| and |b|.

Note: both operands are treated as absolute values.

fn (a Integer) bytes() ([]u8, int)

bytes returns the a byte representation of the integer a, along with the signum int.

Note: The byte array returned is in big endian order.

fn (mut a Integer) dec()

dec decrements a by 1 in place.

fn (dividend Integer) div_checked(divisor Integer) !Integer

div_checked returns the quotient of dividend divided by divisor or an error if divisor == 0.

fn (dividend Integer) div_mod(divisor Integer) (Integer, Integer)

div_mod returns the quotient and remainder from the division of the integers dividend divided by divisor.

WARNING: this method will panic if divisor == 0. Refer to div_mod_checked for a safer version.

fn (dividend Integer) div_mod_checked(divisor Integer) !(Integer, Integer)

div_mod_checked returns the quotient and remainder from the division of the integers dividend divided by divisor. An error is returned if divisor == 0.

fn (a Integer) factorial() Integer

factorial returns the factorial of the integer a.

fn (mut result Integer) from_json_number(raw_number string) !

from_json_number implements a custom decoder for json2

fn (a Integer) gcd(b Integer) Integer

gcd returns the greatest common divisor of the two integers a and b.

fn (a Integer) gcd_binary(b Integer) Integer

gcd_binary returns the greatest common divisor of the two integers a and b. Note that gcd_binary is faster than gcd_euclid, for large integers (over 8 bytes long). Inspired by the 2013-christmas-special by D. Lemire & R. Corderoy https://en.algorithmica.org/hpc/analyzing-performance/gcd/ For more information, refer to the Wikipedia article: https://en.wikipedia.org/wiki/Binary_GCD_algorithm Discussion and further information: https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/

fn (a Integer) gcd_euclid(b Integer) Integer

gcd_euclid returns the greatest common divisor of the two integers a and b. Note that gcd_euclid is faster than gcd_binary, for very-small-integers up to 8-byte/u64.

fn (a Integer) get_bit(i u32) bool

get_bit checks whether the bit at the given index is set.

fn (integer Integer) hex() string

hex returns the hexadecimal string representation of the integer a.

fn (mut a Integer) inc()

inc increments a by 1 in place.

fn (a Integer) int() int

int returns the integer value of the integer a.

Note: This may cause loss of precision.

fn (x Integer) is_odd() bool

is_odd returns true if the integer x is odd, therefore an integer of the form 2k + 1. An input of 0 returns false.

fn (x Integer) is_power_of_2() bool

is_power_of_2 returns true when the integer x satisfies 2^n, where n >= 0

fn (x Integer) is_probably_prime(rounds int) bool

is_probably_prime reports whether x is prime, with a probability of a composite being misreported below 1 / 4^rounds.

The test is deterministic for x below 3317044064679887385961981, where a fixed set of bases is provably sufficient, and probabilistic above it. Passing rounds <= 0 selects a sane default (40 rounds, the value used for key generation in most cryptographic libraries).

Note that a true result is a statement of probability, not certainty. Do not use this to validate an attacker-supplied modulus without also checking the surrounding protocol. If the system entropy source fails, this form fails closed with false; use is_probably_prime_checked when the caller must distinguish that error.

fn (x Integer) is_probably_prime_checked(rounds int) !bool

is_probably_prime_checked is the fallible form of is_probably_prime. It returns an error if the operating system cannot provide entropy for random Miller-Rabin witnesses. Values inside the deterministic range need no entropy.

fn (a Integer) isqrt() Integer

isqrt returns the closest integer square root of the integer a.

WARNING: this method will panic if a < 0. Refer to isqrt_checked for a safer version.

fn (a Integer) isqrt_checked() !Integer

isqrt returns the closest integer square root of the integer a. An error is returned if a < 0.

fn (a Integer) left_shift(amount u32) Integer

left_shift returns the integer a shifted left by amount bits.

fn (dividend Integer) mod_checked(divisor Integer) !Integer

mod_checked returns the remainder of dividend divided by divisor or an error if divisor == 0.

fn (dividend Integer) mod_euclid(divisor Integer) Integer

modulo_euclid returns the result of mathematical modulus. The result is always non-negative for positive divisor.

WARNING: this method will panic if divisor == 0.

fn (dividend Integer) mod_euclid_checked(divisor Integer) !Integer

mod_euclid_checked returns the result of mathematical modulus. The result is always non-negative for positive divisor or an error if divisor == 0.

fn (a Integer) mod_inverse(n Integer) !Integer

mod_inverse calculates the multiplicative inverse of the integer a in the ring ℤ/nℤ. Therefore, the return value x satisfies a * x == 1 (mod m). An error is returned if a and n are not relatively prime, i.e. gcd(a, n) != 1 or if n <= 1

fn (base Integer) mod_pow(exponent u64, modulus Integer) Integer

mod_pow returns the integer base raised to the power of the u32 exponent modulo the integer modulus.

fn (a Integer) neg() Integer

neg returns the result of negation of the integer a.

fn (base Integer) pow(exponent u32) Integer

pow returns the integer base raised to the power of the u32 exponent.

fn (integer Integer) radix_str(radix u32) string

radix_str returns the string representation of the integer a in the specified radix.

fn (a Integer) right_shift(amount u32) Integer

right_shift returns the integer a shifted right by amount bits.

fn (mut a Integer) set_bit(i u32, value bool)

set_bit sets the bit at the given index to the given value.

fn (integer Integer) str() string

str returns the decimal string representation of the integer a.

fn (result Integer) to_json() string

to_json implements a custom encoder for json2

struct IntegerConfig {
pub:
	signum int = 1
}