Module `BIG`

Big Number Arithmetic (BIG)

Base arithmetical operations on big numbers.

Most operators are overloaded and can be used on BIG numbers as if they would be natural. Multiplications by ECP curve points are also possible using ECP as first argument.

For explanations and example usage see dev.zenroom.org/crypto.

Info:

Copyright: Dyne.org foundation 2017-2018
License: AGPLv3
Author: Denis "Jaromil" Roio

Global Big Functions

new ([octet])	Create a new Big number.
from_decimal (string)	Convert a decimal string into a big integer object.
modrand (modulo)	Generate a random Big number whose ceiling is defined by the modulo to another number.
random ()	Generate a random Big number whose ceiling is the order of the curve.
modsqrt (n, p)	Tonelli-Shanks algorithm.
zenadd (a, b)	Perform algebraic sum of two Big numbers, taking under account their zencode signs.
zensub (a, b)	Perform algebraic subtraction of two Big numbers, taking under account their zencode signs.
zenmul (a, b)	Perform algebraic multiplication of two Big numbers, taking under account their zencode signs.
zendiv (a, b)	Perform algebraic division of two Big numbers, taking under account their zencode signs.
zenpositive (n)	Check whether a given Big number is positive.
zenmod (a, b)	Compute the modulo operation of two Big numbers (a and b), ensuring that both numbers are positive.
zenopposite (a)	Compute the opposite (additive inverse) of a Big number.
is_integer (data)	Check whether a given Lua value is an integer or a string representation of an integer.

Class Big

big:__gc ()	It is a destructor for a Big number object in Lua.
big:bits ()	Calculate the number of bits required to represent a Big number.
big:bytes ()	Calculate the number of bytes required to represent a Big number.
big:fixed (len, boolean)	Fixed size encoding for integer with big endian order.
big:decimal ()	Convert a Big integer into a decimal string representation.
big:octet ()	Convert a Big number into an octet.
big:__concat (data)	Concatenate two Big integer objects into a single octet.
big:hex ()	Convert a Big number in hexadecimal format.
big:int ()	Convert a Big number into a Lua integer.
big:__eq (data)	Compare two Big numbers for equality.
big:__lt (data)	Provide a simple way to check if one Big integer is less than another.
big:__lte (data)	Provide a simple way to check if one Big integer is less than or equal another.
big:__add (data)	Add two Big numbers and return the result as a new Big number.
big:__sub (data)	Subtract two Big numbers and return the result as a new Big number.
big:modsub (data, modulo)	Perform modular subtraction of two Big numbers modulus a third Big number.
big:__mul (data)	Provide a flexible way to perform multiplication involving big integers, supporting both scalar multiplication with ECP points and modular multiplication of two big integers.
big:modpower (n, m)	Perform modular exponentiation between Big numbers.
big:sqr ()	Compute the square of a Big number.
big:monty (mod)	Perform Montgomery reduction on a double Big number using a modulus.
big:__mod (m)	Compute the modulo operation on a Big number "b" using a modulus "m".
big:__div (data)	Perform integer division of two Big numbers.
big:modmul (coefficient, modulo)	Multiply a Big number by another Big while ceiling the operation to a modulo to avoid excessive results.
big:moddiv (d, m)	Perform modular division using Big numbers arithmetic.
big:modsqr (m)	Perform modular squaring on Big numbers.
big:modneg (m)	Compute the modular negation of a large integer y modulo another large integer m, i.e., −y mod m.
big:jacobi (y)	Compute the Jacobi symbol of two Big numbers x and y.
big:modinv (m)	Compute the modular inverse of a large integer y modulo another large integer m.
big:parity ()	Check the parity (whether a number is even or odd) of a Big number.
big:__shr (n)	Perform a right shift operation on a Big number (c) by a specified number of bits (n).

Global Big Functions

new ([octet])

Create a new Big number. If an argument is present, import it as OCTET and initialise it with its value.

Parameters:

octet value (optional)

Returns:

a new Big number

from_decimal (string)

Convert a decimal string into a big integer object.
It works only for positive numbers.

Parameters:

string representing a decimal number

Returns:

the big integer object

modrand (modulo)

Generate a random Big number whose ceiling is defined by the modulo to another number.

Parameters:

modulo another BIG number, usually ECP.order

Returns:

a new Big number

Usage:

--generate a random Big number starting from the EC BLS381
BIG.modrand(ECP.order())

random ()

Generate a random Big number whose ceiling is the order of the curve.

Returns:

a new Big number

modsqrt (n, p)

Tonelli-Shanks algorithm. Given as input two bigs n and p compute the square root of n modulo p where p is an odd prime and n is a square modulo p.

Parameters:

n Big number
p odd Big number

Returns:

the result of the modular square root computation

zenadd (a, b)

Perform algebraic sum of two Big numbers, taking under account their zencode signs.
The result is stored in a new Big number and pushed onto the Lua stack.

Parameters:

a Big number
b Big number

Returns:

the sum a+b

zensub (a, b)

Perform algebraic subtraction of two Big numbers, taking under account their zencode signs.
The result is stored in a new Big number and pushed onto the Lua stack.

Parameters:

a Big number
b Big number

Returns:

the subtraction a-b

zenmul (a, b)

Perform algebraic multiplication of two Big numbers, taking under account their zencode signs.
The result is stored in a new Big number and pushed onto the Lua stack.

Parameters:

a Big number
b Big number

Returns:

the multiplication a*b

zendiv (a, b)

Perform algebraic division of two Big numbers, taking under account their zencode signs.
The result is stored in a new Big number and pushed onto the Lua stack.

Parameters:

a Big number
b Big number

Returns:

the division a/b

zenpositive (n)

Check whether a given Big number is positive. If it is positive the output is true, otherwise false.

Parameters:

n a Big number

Returns:

a boolean value

zenmod (a, b)

Compute the modulo operation of two Big numbers (a and b), ensuring that both numbers are positive.

Parameters:

a Big number
b Big number

Returns:

a mod b

zenopposite (a)

Compute the opposite (additive inverse) of a Big number.

Parameters:

a Big number

Returns:

the result of the opposite operation

Usage:

--create a Big number
y = big.from_decimal("123234442341233983797129732792324343")
--estimate the opposite
print(big.zenopposite(y):decimal())
--print: -123234442341233983797129732792324343

is_integer (data)

Check whether a given Lua value is an integer or a string representation of an integer.

Parameters:

data a Lua value

Returns:

a boolean value

Class Big

Object Methods

big:__gc ()

It is a destructor for a Big number object in Lua. It is for freeing the memory allocated for the Big number and ensuring there are no memory leaks.

big:bits ()

Calculate the number of bits required to represent a Big number.

Returns:

the number of bits

Usage:

--create a Big number
b = BIG.new(1983783819133422)
--calculate the number of bits
print(b:bits())
--print: 94

big:bytes ()

Calculate the number of bytes required to represent a Big number.

Returns:

the number of bytes

Usage:

--create a Big number
b = BIG.new(1983783819133422)
--calculate the number of bytes
print(b:bytes())
--print: 11

big:fixed (len, boolean)

Fixed size encoding for integer with big endian order. If the second parameter is 'false' it uses little endian order.

Parameters:

len bytes size
boolean use big endian order (if omitted by default is true)

Returns:

a fixed-length octet

Usage:

--create a Big number
b = BIG.from_decimal("1234567891234569213839813381")
 	--bytes size equal to 10
 	print(b:fixed(10):hex())
--print: 03fd35eb7ce4f16ec9962b05

big:decimal ()

Convert a Big integer into a decimal string representation. Slow but only for export. It work only for positive numbers.

Returns:

string which represent a decimal number (only digits 0-9)

Usage:

--create a Big number
b = BIG.from_decimal("1234567891234569213")
--print decimal number
print(b:decimal())

big:octet ()

Convert a Big number into an octet.

Returns:

an octet

big:__concat (data)

Concatenate two Big integer objects into a single octet.

Parameters:

data a big integer object to concatenate

Returns:

the concatenated octet object

Usage:

--create two octets
b = BIG.from_decimal("1234567891")
b2 = BIG.from_decimal("234569213")
--concatenate them
conc = b:__concat(b2)
--print in hexadecimal
--print b: 499602d3
--print b2: 0dfb3dfd
--print conc: 499602d30dfb3dfd

big:hex ()

Convert a Big number in hexadecimal format.

Returns:

an octet in hex

big:int ()

Convert a Big number into a Lua integer.
The function handles big integers that fit within 32 bits and truncates larger integers to 32 bits with a warning.

Returns:

a Lua integer

big:__eq (data)

Compare two Big numbers for equality.

Parameters:

data a Big integer to compare

Returns:

a boolean value

big:__lt (data)

Provide a simple way to check if one Big integer is less than another.

Parameters:

data a Big integer to compare

Returns:

a boolean value

Usage:

--create two Big integers
b = BIG.from_decimal("12345678914124724921472194")
b2 = BIG.from_decimal("1234")
--compare them
if b:__lt(b2) then print("b is less than b2")
else print("b isn't less than b2")
end
--print: b isn't less than b2

big:__lte (data)

Provide a simple way to check if one Big integer is less than or equal another.

Parameters:

data a Big integer to compare

Returns:

a boolean value

big:__add (data)

Add two Big numbers and return the result as a new Big number.

Parameters:

data a Big integer to add

Returns:

the sum of the two Big numbers

Usage:

--create two Big numbers
b = BIG.from_decimal("12345678914124724921472194")
b2 = BIG.from_decimal("12343234234242334423432")
--make the sum
print(b:__add(b2):decimal())
--print: 12358022148358967255895626

big:__sub (data)

Subtract two Big numbers and return the result as a new Big number. If the second argument is bigger than the first argument, the behavior depends on whether the big integers are in regular size or double size mode.

Parameters:

data a Big integer to subtract

Returns:

the difference of the two Big numbers

Usage:

--create two Big numbers
b = BIG.from_decimal("12345678914124724921472194")
b2 = BIG.from_decimal("12343234234242334423432")
--make the difference
print(b:__sub(b2):decimal())
--print: 12333335679890482587048762

big:modsub (data, modulo)

Perform modular subtraction of two Big numbers modulus a third Big number.

Parameters:

data a Big number to subtract
modulo the modulus of the operation

Usage:

--create the two big numbers to subtract
b = BIG.from_decimal("12345678914124724921472194")
b2 = BIG.from_decimal("12343234234242334423432")
--define the modulo
mod = BIG.from_decimal("1234")
print(b:modsub(b2, mod):decimal())
--print: 576

big:__mul (data)

Provide a flexible way to perform multiplication involving big integers, supporting both scalar multiplication with ECP points and modular multiplication of two big integers.

Parameters:

data a big integer or an ECP point

Returns:

the result of the multiplication

big:modpower (n, m)

Perform modular exponentiation between Big numbers.

Parameters:

n exponent (Big number)
m modulus (Big number)

Returns:

a Big number x^n mod m

Usage:

--create three Big numbers
x = big.from_decimal("12341212142425354332324242422")
n = big.from_decimal("15376863816838361893936136936")
m = big.from_decimal("31873379237941484018414806743")
--calculate x^n mod m
print(x:modpower(n,m):decimal())
--print: 26994051819303675513763443877

big:sqr ()

Compute the square of a Big number.

Returns:

the square of a Big number

big:monty (mod)

Perform Montgomery reduction on a double Big number using a modulus. Montgomery reduction is an efficient algorithm used in modular arithmetic to avoid expensive division operations, often used in cryptographic computations.

Parameters:

mod the modulus

Returns:

a big number representing the Montgomery-reduced value

big:__mod (m)

Compute the modulo operation on a Big number "b" using a modulus "m".

Parameters:

m the modulus

Returns:

b mod m

Usage:

--create the two Big numbers "b" and "m"
b = big.from_decimal("123234442341233983797129732792324343")
m = big.from_decimal("165257575713")
--compute b mod m
print(b:__mod(m):decimal())
--print: 39084337405

big:__div (data)

Perform integer division of two Big numbers.

Parameters:

data a Big number

Returns:

the integer part of the division of two Big numbers

Usage:

--create two Big numbers
b1 = big.from_decimal("123234442341233983797129732792324343")
b2 = big.from_decimal("165257575713")
--compute ⌊b1/b2⌋
print(b1:__div(b2):decimal())
--print: 745711304365574914096826

big:modmul (coefficient, modulo)

Multiply a Big number by another Big while ceiling the operation to a modulo to avoid excessive results.
This operation is to be preferred to the simple overladed operator * in most cases where such a multiplication takes place. It may replace * in the future as a simplification.

Parameters:

coefficient another Big number
modulo usually ECP.order

Returns:

a new Big number

big:moddiv (d, m)

Perform modular division using Big numbers arithmetic. It computes (y/d) mod m.

Parameters:

d the divisor (Big number)
m the modulus (Big number)

Returns:

the result of the modular division

Usage:

--define y, d and m
y = big.from_decimal("123234442341233983797129732792324343")
d = big.from_decimal("165257575713")
m = big.from_decimal("165257")
--compute (y/d) mod m
print(y:moddiv(d,m):decimal())
print: 38881

big:modsqr (m)

Perform modular squaring on Big numbers. Compute the modular square of a Big number y modulo another Big number m, i.e., y^2 mod m.

Parameters:

m the modulus

Returns:

the result of the modular squaring operation

Usage:

--define the two big integers
y = big.from_decimal("123234442341233983797129732792324343")
m = big.from_decimal("165257575713")
--compute y^2 mod m
print(y:modsqr(m):decimal())
--print: 86198167171

big:modneg (m)

Compute the modular negation of a large integer y modulo another large integer m, i.e., −y mod m.

Parameters:

m the modulus

Returns:

the result of the modular negation operation

Usage:

--define the two big integers
y = big.from_decimal("123234442341233983797129732792324343")
m = big.from_decimal("165257575713")
--compute -y mod m
print(y:modneg(m):decimal())
--print: 126173238308

big:jacobi (y)

Compute the Jacobi symbol of two Big numbers x and y. The Jacobi symbol is a mathematical function used in number theory, particularly in primality testing and quadratic residue calculations.

Parameters:

y a Big number

Returns:

the result of the Jacobi symbol computation as an integer

Usage:

--create two Big numbers x and y
x = big.from_decimal("123234442341233983797129732792324343")
y = big.from_decimal("165257575713243243323242243423")
--compute the jacobi symbol
print(x:jacobi(y))
--print: -1

big:modinv (m)

Compute the modular inverse of a large integer y modulo another large integer m.
The modular inverse of y modulo m is a value x such that: x*y = 1 mod m

Parameters:

m the modulus

Returns:

the result of the modular inverse computation

Usage:

--create two Big numbers y and m
y = big.from_decimal("123234442341233983797129732792324343")
m = big.from_decimal("165257575713243243323242243423")
--compute x
print(y:modinv(m):decimal())
--print: 59313399677853266981606933073

big:parity ()

Check the parity (whether a number is even or odd) of a Big number.

Returns:

boolean value (true if odd, false if even)

big:__shr (n)

Perform a right shift operation on a Big number (c) by a specified number of bits (n).

Parameters:

n the number of bits to shift

Returns:

the result of the right shift operation

Zenroom

Contents

Modules

Module BIG

Big Number Arithmetic (BIG)

Info:

Global Big Functions

Class Big

Global Big Functions

Parameters:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Usage:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Usage:

Parameters:

Returns:

Class Big

Returns:

Usage:

Returns:

Usage:

Parameters:

Returns:

Usage:

Returns:

Usage:

Returns:

Parameters:

Returns:

Usage:

Returns:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Usage:

Parameters:

Returns:

Parameters:

Returns:

Usage:

Parameters:

Returns:

Usage:

Parameters:

Usage:

Parameters:

Returns:

Parameters:

Returns:

Usage:

Returns:

Parameters:

Returns:

Parameters:

Returns:

Usage:

Parameters:

Returns:

Module `BIG`