type word[link]

type word = u32;

A big integer is stored in an array of words. The first word holds information about the effective size of the big integer. The subsequend words encode the value in little-endian order. The WORD_BITMASK masks the bits that are actually used to store the value in each word.

def WORD_BITMASK[link]

def WORD_BITMASK: word = 2147483647;

Bitmask for bits that are used for storing the value in a word.

def WORD_BITSZ[link]

def WORD_BITSZ: u32 = 31;

Number of bits that are used for storing the value in a word.

fn add[link]

fn add(a: []word, b: const []word, ctl: u32) u32;

Adds 'b' to 'a', if 'ctl' is 1. If 'ctl' is 0, the result will be discarded. Returns the carry, if the addition overflows.

'a' and 'b' must have the same effective word length.

fn decode[link]

fn decode(dest: []u8, src: const []word) void;

Decode 'src' into a big-endian unsigned byte array. The caller must ensure that 'dest' has enough space to store the decoded value. See decodelen on how to determine the required length.

fn decodelen[link]

fn decodelen(src: const []word) size;

Returns the number of bytes required to store a big integer given by 'src'.

For static allocation following expression may be used:

((len(src) - 1) * WORD_BITSZ + 7) / 8

fn decrodd[link]

fn decrodd(x: []word) void;

Decrements 1 from an odd integer 'x'.

fn encode[link]

fn encode(dest: []word, src: const []u8) void;

Encode 'src' from its big-endian unsigned encoding into the internal representation. The caller must make sure that 'dest' has enough space to store 'src'. See encodelen for how to calculate the required size.

This function runs in constant time for given 'src' length.

fn encodelen[link]

fn encodelen(x: []u8) size;

Minimal required words to encode 'x' into an []word. To statically allocate resources, following expression may be used:

((number_of_bits + WORD_BITSZ - 1) / WORD_BITSZ) + 1

fn encodemod[link]

fn encodemod(dest: []word, src: const []u8, m: const []word) u32;

Encodes an integer from its big-endian unsigned encoding. 'src' must be lower than 'm'. If not 'dest' will be set to 0. 'dest' will have the announced bit length of 'm' after decoding.

The return value is 1 if the decoded value fits within 'm' or 0 otherwise.

This function runs in constant time for a given 'src' length and announced bit length of m, independent of whether the value fits within 'm' or not.

fn encodereduce[link]

fn encodereduce(dest: []word, src: const []u8, m: const []word) void;

Encode an integer from its big-endian unsigned representation, and reduce it modulo the provided modulus 'm'. The announced bit length of the result is set to be equal to that of the modulus.

'dest' must be distinct from 'm'.

fn ewordlen[link]

fn ewordlen(x: const []word) u32;

Get the effective word lenght of 'x'. The effective wordlen is the number of words that are used to represent the actual value. Eg. the number 7 will have an effective word length of 1, no matter of len(x). The first element containing the encoded word len is not added to the result.

fn frommonty[link]

fn frommonty(x: []word, m: const []word, m0i: word) void;

Convert a modular integer back from Montgomery representation. The integer 'x' must be less than 'm', but with the same announced bit length. The 'm0i' parameter is equal to -(1/m0) mod 2^32, where m0 is the least significant value word of 'm' (this works only if 'm' is an odd integer). See ninv for how to get this value.

fn iszero[link]

fn iszero(x: []word) u32;

Checks whether the effective words of 'x' are zero. Returns 1 if so, or 0 otherwise.

fn modpow[link]

fn modpow(x: []word, e: const []u8, m: const []word, m0i: u32, tmp: []word) u32;

Compute a modular exponentiation. 'x' must be an integer modulo 'm' (same announced bit length, lower value). 'm' must be odd. The exponent is in big-endian unsigned notation, over len(e) bytes. The 'm0i' parameter is equal to -(1/m0) mod 2^31, where m0 is the least significant value word of 'm' (this works only if 'm' is an odd integer). See ninv on how to get this value. The 'tmp' array is used for temporaries and MUST be large enough to accommodate at least two temporary values with the same size as 'm' (including the leading 'bit length' word). If there is room for more temporaries, then this function may use the extra room for window-based optimisation, resulting in faster computations.

Returned value is 1 on success, 0 on error. An error is reported if the provided 'tmp' array is too short.

fn montymul[link]

fn montymul(d: []word, x: const []word, y: const []word, m: const []word, m0i: u32) void;

Compute a modular Montgomery multiplication. 'd' is filled with the value of 'x'*'y'/R modulo 'm' (where R is the Montgomery factor). The array 'd' must be distinct from 'x', 'y' and 'm'. 'x' and 'y' must be numerically lower than 'm'. 'x' and 'y' may be the same array. The 'm0i' parameter is equal to

• (1/m0) mod 2^32, where m0 is the least significant value word of 'm' (this works only if 'm' is an odd integer). See ninv for how to get this value.

fn mulacc[link]

fn mulacc(d: []word, a: const []word, b: const []word) void;

Compute 'd' + 'a' * 'b', result in 'd'. The initial announced bit length of 'd' MUST match that of 'a'. The 'd' array MUST be large enough to accommodate the full result, plus (possibly) an extra word. The resulting announced bit length of 'd' will be the sum of the announced bit lengths of 'a' and 'b' (therefore, it may be larger than the actual bit length of the numerical result).

'a' and 'b' may be the same array. 'd' must be disjoint from both 'a' and 'b'.

fn ninv[link]

fn ninv(m0: word) word;

Calculates "m0i" which is equal to -(1/'m0') mod 2^WORD_BITSZ. 'm0' is the the first significant word of a big integer, which is the word at index 1.

fn reduce[link]

fn reduce(x: []word, a: const []word, m: const []word) void;

Reduce an integer 'a' modulo another 'm'. The result is written in 'x' and its announced bit length is set to be equal to that of 'm'.

'x' must be distinct from 'a' and 'm'.

This function runs in constant time for given announced bit lengths of 'a' and 'm'.

fn rshift[link]

fn rshift(x: []word, count: word) void;

Right-shift an integer 'x' by 'count'. The shift amount must be less than WORD_BITSZ.

fn sub[link]

fn sub(a: []word, b: const []word, do: u32) u32;

Subtracts 'b' from 'a', if 'ctl' is 1. If 'ctl' is 0, the result will be discared. Returns the carry, if the subtraction overflows.

'a' and 'b' must be of the same effective word length.

fn tomonty[link]

fn tomonty(x: []word, m: const []word) void;

Convert a modular integer to Montgomery representation. The integer 'x' must be lower than 'm', but with the same announced bit length.

fn zero[link]

fn zero(x: []word, ebitlen: word) void;

Sets encoded bitlen of 'x' to 'ebitlen' and then zeroes its effective words.