Next: , Previous: (dir), Up: (dir)

MPM

This manual describes how to use the MPM bignum modular arithmetic library.

Copyright 2002, 2007 Kevin Ryde

MPM is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version.



Next: , Previous: Top, Up: Top

1 Introduction

Nothing is built or installed by default, but a build can be done with

     make mpm

Since various GNU MP internals are used it's only possible to compile against a GNU MP build tree, but mpm.h and the resulting libmpm.a can then be used from anywhere. mpm.h provides all prototypes and defines.

     #include <gmp.h>
     #include "mpm.h"

And an application should link against libmpm.a, for example with

     gcc myprog.c libmpm.a -lgmp

Note that libmpm.a can only be used with the particular libgmp it was built for.


Next: , Previous: Introduction, Up: Top

2 Types and Conventions

— Data type: mpm_t
— Data type: mpr_t

A modulus is represented by a type mpm_t, and a residue by mpr_t.

The modulus should be initialized first (see Initializing Moduli), and then residues are initialized for use with that modulus (see Initializing Residues).

An mpr_t can only be used with the particular modulus it was initialized against (using the wrong modulus will have unpredictable results). An mpr_t can be cleared then and re-initialized for a new modulus.

When an mpr_t is passed as a parameter it's effectively call-by-reference, meaning that any change to its value is made to the copy in the caller as well. The usual way to return results from a function is to designate certain parameters as outputs, and set their values in the function. This is as per mpz_t (see Parameter Conventions).

Note however that mpr_init and friends are macros which operate only on the local mpr_t, not in any caller. This is because mpr_t is just a pointer which mpr_init assigns to. This is different from how mpz_t works, but it makes the implementation more efficient, and allows the compiler to detect any mpr_t variables used uninitialized.

const cannot be used with mpr_t currently. Perhaps this will change.


Next: , Previous: Types and Conventions, Up: Top

3 Efficiency

Modulus Initialization
mpm_init is not fast since it pre-computes various values associated with the modulus, for subsequent use in mpr operations.
Division
mpr_div is not much more than a combination of mpr_invert and mpr_mul, and mpr_invert is quite slow, being effectively an extended GCD against the modulus. An application using the same divisor repeatedly is best off taking an inverse once then using that with mpr_mul as required.
Small operands
mpr_mul_ui, mpr_mul_si and mpr_addmul_ui are good for small multipliers. In particular with REDC it's better to multiply by a small operand than to convert that to a residue.

mpr_add_ui is good in the plain division method, but for REDC it's best to convert to an mpr_t if the same ui value is going to be used repeatedly.


Next: , Previous: Efficiency, Up: Top

4 Initializing Moduli

— Function: void mpm_init (mpm_t m, mpz_t op)
— Function: int mpm_init_str (mpm_t, const char *op, int base)
— Function: void mpm_init_ui (mpm_t m, unsigned long op)

Initialize m for operations modulo op.

Currently odd values use REDC (basecase or sub-quadratic according to the size), but even values only use a simple division method which may be less efficient. Special values 2^N and 2^N-1 are not noticed; if they're likely to occur then an application should check and use mpm_init_2exp or mpm_init_2expsub1 below.

— Function: void mpm_init_2exp (mpm_t m, unsigned long n)

Initialize m for operations mod 2^n.

— Function: void mpm_init_2expsub1 (mpm_t m, unsigned long n)

Initialize m for operations mod 2^n-1.

— Function: void mpm_clear (mpm_t m)

Clear m.

— Macro: mpz_t mpm_modref (mpm_t m)

Return a reference to the modulus value of m. The value must not be changed, but it can be used as a source operand for normal mpz functions.


Next: , Previous: Initializing Moduli, Up: Top

5 Initialization Functions

— Macro: void mpr_init (mpr_t op, mpm_t m)

Initialize op, ready to hold residues mod m.

— Macro: void mpr_clear (mpr_t op, mpm_t m)

Clear op, a residue modulo m.


Next: , Previous: Initializing Residues, Up: Top

6 Assignment Functions

— Macro: void mpr_set (mpr_t rop, mpr_t op, mpm_t m)

Set rop to the value of op, both residues mod m.

— Macro: void mpr_set_z (mpr_t rop, mpz_t op, mpm_t m)
— Macro: void mpr_set_si (mpr_t rop, mpz_t op, mpm_t m)
— Macro: void mpr_set_ui (mpr_t rop, mpz_t op, mpm_t m)

Set rop to the value of op, converting it to a residue mod m.

— Macro: void mpr_set_str (mpr_t rop, char *str, int base, mpm_t m)

Set rop from a null-terminated string str in the given base. The return value is 0 if the string is valid, or -1 if not. Parsing is the same as for mpz_set_str.

— Macro: unsigned long mpr_get_ui (mpr_t op, mpm_t m)

Get the value of op, a residue mod m, as an integer in the range 0 to m-1.

If the result is too big to fit an unsigned long then just the least significant bits that do fit are returned.

— Macro: void mpr_get_z (mpz_t rop, mpr_t op, mpm_t m)

Set rop to the value of op, a residue mod m. rop will be in the range 0 to m-1.

— Function: void mpr_swap (mpr_t op1, mpz_t op1, mpm_t m)

Swap the values of op1 and op2, residues mod m.


Next: , Previous: Assigning Residues, Up: Top

7 Combined Initialization and Assignment Functions

— Macro: void mpr_init_set (mpr_t rop, mpr_t op, mpm_t m)
— Macro: void mpr_init_set_si (mpr_t rop, mpz_t op, mpm_t m)
— Macro: void mpr_init_set_ui (mpr_t rop, mpz_t op, mpm_t m)
— Macro: void mpr_init_set_z (mpr_t rop, mpz_t op, mpm_t m)

Initialize rop and set it to the value of op, mod m.

— Macro: void mpr_init_set_str (mpr_t rop, char *str, int base, mpm_t m)

Initialize rop and set its value from a null-terminated string str in the given base. The return value is 0 if the string is valid, or -1 if not. rop is still initialized if the string is invalid. Parsing is the same as for mpz_set_str.


Next: , Previous: Simultaneous Residue Init & Assign, Up: Top

8 Arithmetic Functions

— Macro: void mpr_add (mpr_t rop, mpr_t op1, mpr_t op2, mpm_t m)
— Macro: void mpr_add_ui (mpr_t rop, mpr_t op1, unsigned long op2, mpm_t m)

Set rop to op1 + op2, mod m.

— Macro: void mpr_addmul_ui (mpr_t rop, mpr_t op1, unsigned long op2, mpm_t m)

Set rop to rop + op1 times op2, mod m.

— Macro: void mpr_div (mpr_t rop, mpr_t op1, mpr_t op2, mpm_t m)

Set rop to op1 / op2, mod m. op2 and m must have no common factors for this result to exist and be unique, if there are common factors then the behaviour of this function is undefined.

— Macro: void mpr_div_2exp (mpr_t rop, mpr_t op1, unsigned long op2, mpm_t m)

Set rop to op1 / 2^op2, mod m. m must be odd, otherwise the behaviour of this function is undefined.

— Macro: int mpr_invert (mpr_t rop, mpr_t op, mpm_t m)

Set rop to 1 / op, mod m. If this inverse exists and is unique the return value is non-zero, if not then the return value is zero and rop is undefined. The inverse will exist whenever op and m have no common factors.

— Macro: void mpr_mul (mpr_t rop, mpr_t op1, mpr_t op2, mpm_t m)
— Macro: void mpr_mul_si (mpr_t rop, mpr_t op1, long op2, mpm_t m)
— Macro: void mpr_mul_ui (mpr_t rop, mpr_t op1, unsigned long op2, mpm_t m)

Set rop to op1 times op2, mod m.

— Macro: void mpr_mul_2exp (mpr_t rop, mpr_t op1, unsigned long op2, mpm_t m)

Set rop to op1 times 2^op2, mod m.

— Macro: void mpr_neg (mpr_t rop, mpr_t op, mpm_t m)

Set rop to -op, mod m.

— Macro: void mpr_pow (mpr_t rop, mpr_t op1, mpz_t op2, mpm_t m)
— Function: void mpr_pow_ui (mpr_t rop, mpr_t op1, unsigned long op2, mpm_t m)
— Function: void mpr_ui_pow (mpr_t rop, unsigned long op1, mpz_t op2, mpm_t m)
— Function: void mpr_ui_pow_ui (mpr_t rop, unsigned long op1, unsigned long op2, mpm_t m)
— Function: void mpr_z_pow_ui (mpr_t rop, mpz_t op1, unsigned long op2, mpm_t m)

Set rop to op1 to the power op2, mod m.

— Macro: void mpr_sub (mpr_t rop, mpr_t op1, mpr_t op2, mpm_t m)
— Macro: void mpr_sub_ui (mpr_t rop, mpr_t op1, unsigned long op2, mpm_t m)

Set rop to op1 - op2, mod m.

— Macro: void mpr_submul_ui (mpr_t rop, mpr_t op1, unsigned long op2, mpm_t m)

Set rop to rop - op1 times op2, mod m.


Next: , Previous: Residue Arithmetic, Up: Top

9 Comparison Functions

— Macro: int mpr_equal (mpr_t op1, mpr_t op2, mpm_t m)
— Macro: int mpr_equal_ui (mpr_t op1, unsigned long op2, mpm_t m)

Return non-zero if op1 and op2 are equal, mod m.

— Macro: int mpr_equal_one (mpr_t op, mpm_t m)
— Macro: int mpr_equal_zero (mpr_t op, mpm_t m)
— Macro: int mpr_equal_negone (mpr_t op, mpm_t m)

Return non-zero if op is equal to 1, 0 or -1, respectively, mod m.


Next: , Previous: Residue Comparisons, Up: Top

10 Number Theoretic Functions

— Macro: int mpr_gcd (mpz_t rop, mpr_t op, mpm_t m)

Set rop to the greatest common divisor of op and the modulus m.

If op is zero then rop is set to m, otherwise rop is in the range 1 <= rop < m.

— Macro: int mpr_jacobi (mpr_t op, mpm_t m)

Return the value of the Jacobi symbol (op/m). m must be odd.

— Function: int mpr_sprp_p (mpr_t b, mpm_t m)

Return 1 if the modulus value m is a strong probable prime (sprp) to the given base b, or 0 if not.

For m written as m = e*2^k, with e odd, m is an sprp if either b^e = 1 mod m, or b^(e*2^i) = -1 mod m for some 0 <= i < k.

When mpr_sprp_p returns 0, m is definitely composite. But when it returns 1, m is only “probably prime” because although all primes get a return of 1, a few composites (called strong pseudoprimes) do too. If base b is chosen randomly then mpr_sprp_p is a single run of the Miller-Rabin primality testing algorithm.


Next: , Previous: Number Theoretic Functions, Up: Top

11 Internals

11.1 REDC Algorithm

REDC is Peter L. Montgomery's algorithm from “Modular Multiplication Without Trial Division”, Mathematics of Computation, volume 44, number 170, April 1985. Residues are kept in the range 0 to m-1 and for an input x the value held is x*R mod m, where R is a power of 2 chosen as the next whole number of limbs bigger than m.

The key to this representation is that it allows the reduction part of a modular multiplication to be implemented using an “exact remainder” style, which is simpler and a little faster, especially for smallish moduli.

11.2 Division Algorithm

For plain division, residues are also kept in the range 0 to m-1.


Next: , Previous: Internals, Up: Top

Concept Index


Previous: Concept Index, Up: Top

Function and Type Index