group

group__libshare__memmpi
Multi-precision integers allow for the use of "big numbers" that would otherwise not be compatuable directly on the registers of common computers.

function

void shmpi_init

(shmpi *X)

Initialize one MPI (make internal references valid) This just makes it ready to be set or freed, but does not define a value for the MPI.

Param

X

One MPI to initialize.
function

void shmpi_free

(shmpi *X)

Unallocate one MPI.

Param

X

One MPI to unallocate.
function

int shmpi_grow

(shmpi *X, size_t nblimbs)

Enlarge to the specified number of limbs.

Param

X

MPI to grow
nblimbs

The target number of limbs
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_shrink

(shmpi *X, size_t nblimbs)

Resize down, keeping at least the specified number of limbs.

Param

X

MPI to shrink
nblimbs

The minimum number of limbs to keep
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_copy

(shmpi *X, const shmpi *Y)

Copy the contents of Y into X.

Param

X

Destination MPI
Y

Source MPI
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

void shmpi_swap

(shmpi *X, shmpi *Y)

Swap the contents of X and Y.

Param

X

First MPI value
Y

Second MPI value
function

int shmpi_safe_cond_assign

(shmpi *X, const shmpi *Y, unsigned char assign)

Safe conditional assignement X = Y if assign is 1.

Param

X

MPI to conditionally assign to
Y

Value to be assigned
assign

1: perform the assignment, 0: keep X's original value
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed,
Note

This function is equivalent to if( assign ) shmpi_copy( X, Y ); except that it avoids leaking any information about whether the assignment was done or not (the above code may leak information through branch prediction and/or memory access patterns analysis).
function

int shmpi_safe_cond_swap

(shmpi *X, shmpi *Y, unsigned char assign)

Safe conditional swap X <-> Y if swap is 1.

Param

X

First value
shmpi
structshmpi
compound
Y

Second value
shmpi
structshmpi
compound
assign

1: perform the swap, 0: keep X and Y's original values
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed,
Note

This function is equivalent to if( assign ) shmpi_swap( X, Y ); except that it avoids leaking any information about whether the assignment was done or not (the above code may leak information through branch prediction and/or memory access patterns analysis).
function

int shmpi_lset

(shmpi *X, t_sint z)

Set value from integer.

Param

X

MPI to set
z

Value to use
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_get_bit

(const shmpi *X, size_t pos)

Get a specific bit from X.

Param

X

MPI to use
pos

Zero-based index of the bit in X
Return Value

Either a 0 or a 1
function

int shmpi_set_bit

(shmpi *X, size_t pos, unsigned char val)

Set a bit of X to a specific value of 0 or 1.

Note

Will grow X if necessary to set a bit to 1 in a not yet existing limb. Will not grow if bit should be set to 0
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed, MPI_ERR_MPI_BAD_INPUT_DATA if val is not 0 or 1
Param

X

MPI to use
pos

Zero-based index of the bit in X
val

The value to set the bit to (0 or 1)
function

size_t shmpi_lsb

(const shmpi *X)

Return the number of zero-bits before the least significant '1' bit.

Note: Thus also the zero-based index of the least significant '1' bit

Param

X

MPI to use
function

size_t shmpi_msb

(const shmpi *X)

Return the number of bits up to and including the most significant '1' bit'.

Note: Thus also the one-based index of the most significant '1' bit

Param

X

MPI to use
function

size_t shmpi_size

(const shmpi *X)

Return the total size in bytes.

Param

X

MPI to use
function

int shmpi_read_string

(shmpi *X, int radix, const char *s)

Import from an ASCII string.

Param

X

Destination MPI
radix

Input numeric base
s

Null-terminated string buffer
Return Value

0 if successful, or a MPI_ERR_MPI_XXX error code
function

int shmpi_write_string

(const shmpi *X, int radix, char *s, size_t *slen)

Export into an ASCII string.

Param

X

Source MPI
radix

Output numeric base
s

String buffer
slen

String buffer size
Return Value

0 if successful, or a MPI_ERR_MPI_XXX error code. *slen is always updated to reflect the amount of data that has (or would have) been written.
Note

Call this function with *slen = 0 to obtain the minimum required buffer size in *slen.
function

int shmpi_read_binary

(shmpi *X, const unsigned char *buf, size_t buflen)

Import X from unsigned binary data, big endian.

Param

X

Destination MPI
buf

Input buffer
buflen

Input buffer size
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_write_binary

(const shmpi *X, unsigned char *buf, size_t buflen)

Export X into unsigned binary data, big endian.

Always fills the whole buffer, which will start with zeros if the number is smaller.

Param

X

Source MPI
buf

Output buffer
buflen

Output buffer size
Return Value

0 if successful, MPI_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
function

int shmpi_shift_l

(shmpi *X, size_t count)

Left-shift: X <<= count.

Param

X

MPI to shift
count

Amount to shift
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_shift_r

(shmpi *X, size_t count)

Right-shift: X >>= count.

Param

X

MPI to shift
count

Amount to shift
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_cmp_abs

(const shmpi *X, const shmpi *Y)

Compare unsigned values.

Param

X

Left-hand MPI
Y

Right-hand MPI
Return Value

1 if |X| is greater than |Y|, -1 if |X| is lesser than |Y| or 0 if |X| is equal to |Y|
function

int shmpi_cmp_mpi

(const shmpi *X, const shmpi *Y)

Compare signed values.

Param

X

Left-hand MPI
Y

Right-hand MPI
Return Value

1 if X is greater than Y, -1 if X is lesser than Y or 0 if X is equal to Y
function

int shmpi_cmp_int

(const shmpi *X, t_sint z)

Compare signed values.

Param

X

Left-hand MPI
z

The integer value to compare to
Return Value

1 if X is greater than z, -1 if X is lesser than z or 0 if X is equal to z
function

int shmpi_add_abs

(shmpi *X, const shmpi *A, const shmpi *B)

Unsigned addition: X = |A| + |B|.

Param

X

Destination MPI
A

Left-hand MPI
B

Right-hand MPI
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_sub_abs

(shmpi *X, const shmpi *A, const shmpi *B)

Unsigned subtraction: X = |A| - |B|.

Param

X

Destination MPI
A

Left-hand MPI
B

Right-hand MPI
Return Value

0 if successful, MPI_ERR_MPI_NEGATIVE_VALUE if B is greater than A
function

int shmpi_add_mpi

(shmpi *X, const shmpi *A, const shmpi *B)

Signed addition: X = A + B.

Param

X

Destination MPI
A

Left-hand MPI
B

Right-hand MPI
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_sub_mpi

(shmpi *X, const shmpi *A, const shmpi *B)

Signed subtraction: X = A - B.

Param

X

Destination MPI
A

Left-hand MPI
B

Right-hand MPI
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_add_int

(shmpi *X, const shmpi *A, t_sint b)

Signed addition: X = A + b.

Param

X

Destination MPI
A

Left-hand MPI
b

The integer value to add
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_sub_int

(shmpi *X, const shmpi *A, t_sint b)

Signed subtraction: X = A - b.

Param

X

Destination MPI
A

Left-hand MPI
b

The integer value to subtract
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_mul_mpi

(shmpi *X, const shmpi *A, const shmpi *B)

Baseline multiplication: X = A * B.

Param

X

Destination MPI
A

Left-hand MPI
B

Right-hand MPI
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_mul_int

(shmpi *X, const shmpi *A, t_sint b)

Baseline multiplication: X = A * b Note: despite the functon signature, b is treated as a t_uint.

Negative values of b are treated as large positive values.

Param

X

Destination MPI
A

Left-hand MPI
b

The integer value to multiply with
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_div_mpi

(shmpi *Q, shmpi *R, const shmpi *A, const shmpi *B)

Division by : A = Q * B + R.
shmpi
structshmpi
compound

Param

Q

Destination MPI for the quotient
R

Destination MPI for the rest value
A

Left-hand MPI
B

Right-hand MPI
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed, MPI_ERR_MPI_DIVISION_BY_ZERO if B == 0
Note

Either Q or R can be NULL.
function

int shmpi_div_int

(shmpi *Q, shmpi *R, const shmpi *A, t_sint b)

Division by int: A = Q * b + R.

Param

Q

Destination MPI for the quotient
R

Destination MPI for the rest value
A

Left-hand MPI
b

Integer to divide by
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed, MPI_ERR_MPI_DIVISION_BY_ZERO if b == 0
Note

Either Q or R can be NULL.
function

int shmpi_mod_mpi

(shmpi *R, const shmpi *A, const shmpi *B)

Modulo: R = A mod B.

Param

R

Destination MPI for the rest value
A

Left-hand MPI
B

Right-hand MPI
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed, MPI_ERR_MPI_DIVISION_BY_ZERO if B == 0, MPI_ERR_MPI_NEGATIVE_VALUE if B < 0
function

int shmpi_mod_int

(t_uint *r, const shmpi *A, t_sint b)

Modulo: r = A mod b.

Param

r

Destination t_uint
A

Left-hand MPI
b

Integer to divide by
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed, MPI_ERR_MPI_DIVISION_BY_ZERO if b == 0, MPI_ERR_MPI_NEGATIVE_VALUE if b < 0
function

int shmpi_exp_mod

(shmpi *X, const shmpi *A, const shmpi *E, const shmpi *N, shmpi *_RR)

Sliding-window exponentiation: X = A^E mod N.

Param

X

Destination MPI
A

Left-hand MPI
E

Exponent MPI
N

Modular MPI
_RR

Speed-up MPI used for recalculations
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed, MPI_ERR_MPI_BAD_INPUT_DATA if N is negative or even or if E is negative
Note

_RR is used to avoid re-computing R*R mod N across multiple calls, which speeds up things a bit. It can be set to NULL if the extra performance is unneeded.
function

int shmpi_fill_random

(shmpi *X, size_t size, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)

Fill an MPI X with size bytes of random.

Param

X

Destination MPI
size

Size in bytes
f_rng

RNG function
p_rng

RNG parameter
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_gcd

(shmpi *G, const shmpi *A, const shmpi *B)

Greatest common divisor: G = gcd(A, B).

Param

G

Destination MPI
A

Left-hand MPI
B

Right-hand MPI
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed
function

int shmpi_inv_mod

(shmpi *X, const shmpi *A, const shmpi *N)

Modular inverse: X = A^-1 mod N.

Param

X

Destination MPI
A

Left-hand MPI
N

Right-hand MPI
Return Value

0 if successful, MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed, MPI_ERR_MPI_BAD_INPUT_DATA if N is negative or nil MPI_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
function

int shmpi_is_prime

(shmpi *X, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)

Miller-Rabin primality test.

Param

X

MPI to check
f_rng

RNG function
p_rng

RNG parameter
Return Value

0 if successful (probably prime), MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed, MPI_ERR_MPI_NOT_ACCEPTABLE if X is not prime
function

int shmpi_gen_prime

(shmpi *X, size_t nbits, int dh_flag, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)

Prime number generation.

Param

X

Destination MPI
nbits

Required size of X in bits ( 3 <= nbits <= MPI_MPI_MAX_BITS )
dh_flag

If 1, then (X-1)/2 will be prime too
f_rng

RNG function
p_rng

RNG parameter
Return Value

0 if successful (probably prime), MPI_ERR_MPI_MALLOC_FAILED if memory allocation failed, MPI_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
function

size_t shmpi_bitlen

(const shmpi *X)

Return Value

The the number of bits.
define

SHMPI_MAX_BITS

( 8 * SHMPI_MAX_SIZE )

Maximum number of bits for usable MPIs.

define

SHMPI_ERR_FILE_IO_ERROR

-0x0002

An error occurred while reading from or writing to a file.

define

SHMPI_ERR_INVALID_CHARACTER

-0x0006

There is an invalid character in the digit string.

define

SHMPI_ERR_NEGATIVE_VALUE

-0x000A

The input arguments are negative or result in illegal output.

define

SHMPI_ERR_DIVISION_BY_ZERO

-0x000C

The input argument for division is zero, which is not allowed.