Montgomery Arithmetic Routines

In these routines a big parameter can also be used wherever a flash is specified, but not vice versa. Further information may be gleaned from the (lightly) commented source code. An asterisk after the name indicates that the function does not take a mip parameter if MR_GENERIC_MT is defined in mirdef.h.

Converts a big number to n-residue form.

Parameters:

←x
→y the n-residue form of x

Precondition:

Must be preceded by call to prepare_monty()

See also: redc

Finds the dot product of two arrays of n-residues. So-called "lazy" reduction is used, in that the sum of products is only reduced once with respect to the Montgomery modulus. This is quicker---nearly twice as fast.

Parameters:

←m
←x An array of m n-residues
←y An array of m n-residues
→w =Σxiyi (mod n), where n is the current Montgomery modulus

Precondition:

Must be preceded by call to prepare_monty().

Adds two double length bigs modulo pR, where R = 2n and n is the smallest multiple of the word-length of the underlying MIRACL type, such that R > p. This is required for lazy reduction.

Parameters:

←x
←y
→w = a + b (mod pR)

Subtracts two double length bigs modulo pR, where R = 2n and n is the smallest multiple of the wordlength of the underlying MIRACL type, such that R > p. This is required for lazy reduction.

Parameters:

←x
←y
→w = a − b (mod pR)

Uses the method of lazy reduction combined with Karatsuba's method to multiply two zzn2 variables. Requires just 3 multiplications and two modular reductions.

Parameters:

←a0
←a1
←b0
←b1
→r = the "real part" of (a0 + a1i)(b0 + b1i)
→i = the "imaginary part" of (a0 + a1i)(b0 + b1i)

Modular Lucas exponentiation of an n-residue.

Parameters:

←p An n-residue
←r A big exponent
→vp = Vr−1(p) (mod n) where n is the current Montgomery modulus
→v = Vr(p) (mod n) where n is the current Montgomery modulus

Only v is returned if v and vp are the same big variable.

Precondition:

Must be preceded by call to prepare_monty() and conversion of the first parameter to n-residue form. Note that the exponent is not converted to n-residue form

See also: lucas

Modular addition of two n-residues.

Parameters:

←x
←y
→w = x + y (mod n), where n is the current Montgomery modulus

Precondition:

Must be preceded by a call to prepare_monty().

Modular division of two n-residues.

Parameters:

←x
←y
→w = x/y (mod n), where n is the current Montgomery modulus

Returns:

GCD of y and n as an integer, if possible, or MR_TOOBIG. Should be 1 for a valid result

Precondition:

Must be preceded by call to prepare_monty() and conversion of parameters to n-residue form. Parameters x and y must be distinct.

Modular multiplication of two n-residues. Note that this routine will invoke a KCM Modular Multiplier if MR_KCM has been defined in mirdef.h and set to an appropriate size for the current modulus, or a Comba fixed size modular multiplier if MR_COMBA is defined as exactly the size of the modulus.

Parameters:

←x
←y
→w = xy (mod n), where n is the current Montgomery modulus

Precondition:

Must be preceded by call to prepare_month() and conversion of parameters to n-residue form.

Modular subtraction of two n-residues.

Parameters:

←x
←y
→w = x − y (mod n), where n is the current Montgomery modulus

Precondition:

Must be preceded by a call to prepare_monty().

Finds the modular inverses of many numbers simultaneously, exploiting Montgomery's observation that x−1 = y(xy)−1, y−1 = x(xy)−1. This will be quicker, as modular inverses are slow to calculate, and this way only one is required.

Parameters:

←m The number of inverses required
←x An array of m n-residues whose inverses are wanted
→w An array with the inverses of za x

Returns:

TRUE if successful, otherwise FALSE

Precondition:

The parameters x and w must be distinct.

Modular negation.

Parameters:

←x An n-residue number
→w = −x (mod n), where n is the current Montgomery modulus

Precondition:

Must be preceded by a call to prepare_monty().

Modular exponentiation of an n-residue.

Parameters:

←x
←y
→w = xy (mod n), where n is the current Montgomery modulus

Precondition:

Must be preceded by call to prepare_monty(). Note that the small integer x and the exponent are not converted to n-residue form.

Modular exponentiation of an n-residue.

Parameters:

←x An n-reside number, the base
←y A big number, the exponent
→w = xy (mod n), where n is the current Montgomery modulus

Precondition:

Must be preceded by call to prepare_monty() and conversion of the first parameter to n-residue form. Note that the exponent is not converted to n-residue form

See also: nres_powltr, nres_powmod2

Example:

prepare_monty(n);
...
nres(x, y); // convert to n-residue form
nres_powmod(y, e, z);
redc(z, w); // convert back to normal form

Calculates the product of two modular exponentiations involving n-residues.

Parameters:

←x An n-residue number
←y A big integer
←a An n-residue number
←b A big integer
→w = xy ab (mod n), where n is the current Montgomery modulus

Precondition:

Must be preceded by call to prepare_monty() and conversion of the appropriate parameters to n-residue form. Note that the exponents are not converted to n-residue form

See also: nres_powltr, nres_powmod

Calculates the product of n modular exponentiations involving n-residues. Extra memory is allocated internally by this function.

Parameters:

←n The number of n-residue numbers
←x An array of n n-residue numbers
←y An array of n big integers
→w = x[0]y[0]x[1]y[1] · · · x[n − 1]y[n−1) (mod p), where p is the current Montgomery modulus

Precondition:

Must be preceded by call to prepare_monty() and conversion of the appropriate parameters to n-residue form. Note that the exponents are not converted to n-residue forms.

Multiplies an n-residue by a small integer.

Parameters:

←x
←k
→w = kx (mod n), where n is the current Montgomery modulus

Precondition:

Must be preceded by call to prepare_monty() and conversion of the first parameter to n-residue form. Note that the small integer is not converted to n-residue form

[notice=note]See also: nres_modmult[/notice]

Calculates the square root of an n-residue mod a prime modulus.

Parameters:

←x
→w =x (mod n), where n is the current Montgomery modulus

Returns:

TRUE if the square root exists, otherwise FALSE

Precondition:

Must be preceded by call to prepare_monty() and conversion of the first parameter to n-residue form.

Prepares a Montgomery modulus for use. Each call to this function replaces the previous modulus (if any).

Parameters:

←n A big number which is to be the Montgomery modulus

Returns:

None

Precondition:

The parameter n must be positive and odd. Allocated memory is freed when the current instance of MIRACL is terminated by a call to mirexit().

Converts an n-residue back to normal form.

Parameters:

←x an n-residue
→y the normal form of the n-residue x

Precondition:

Must be preceded by call to prepare_monty()

See also: nres