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.

Multi-precision Integer Library

typedef
typedef int32_t t_sint
typedef
typedef uint32_t t_uint
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_SIZE
1024
Maximum number of bytes for usable MPIs.
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_BAD_INPUT_DATA
-0x0004
Bad input parameters to function.
define
SHMPI_ERR_INVALID_CHARACTER
-0x0006
There is an invalid character in the digit string.
define
SHMPI_ERR_BUFFER_TOO_SMALL
-0x0008
The buffer is too small to write to.
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.
define
SHMPI_ERR_NOT_ACCEPTABLE
-0x000E
The input arguments are not acceptable.
define
SHMPI_ERR_MALLOC_FAILED
-0x0010
Memory allocation failed.
define
MPI_HAVE_INT32
define
SHMEM_ALG_GENPRIME