term% cat index.txt MP(2) System Calls Manual MP(2)
NAME
mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy, mpassign, mprand,
strtomp, mpfmt,mptoa, betomp, mptobe, letomp, mptole, mptoui, uitomp,
mptoi, itomp, uvtomp, mptouv, vtomp, mptov, mpdigdiv, mpadd, mpsub,
mpleft, mpright, mpmul, mpexp, mpmod, mpdiv, mpcmp, mpextendedgcd, mp‐
invert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd,
mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre,
crtin, crtout, crtprefree, crtresfree - extended precision arithmetic
SYNOPSIS
#include <u.h>
#include <libc.h>
#include <mp.h>
mpint* mpnew(int n)
void mpfree(mpint *b)
void mpsetminbits(int n)
void mpbits(mpint *b, int n)
void mpnorm(mpint *b)
mpint* mpcopy(mpint *b)
void mpassign(mpint *old, mpint *new)
mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
char* mptoa(mpint *b, int base, char *buf, int blen)
int mpfmt(Fmt*)
mpint* betomp(uchar *buf, uint blen, mpint *b)
int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
mpint* letomp(uchar *buf, uint blen, mpint *b)
int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
uint mptoui(mpint*)
mpint* uitomp(uint, mpint*)
int mptoi(mpint*)
mpint* itomp(int, mpint*)
mpint* vtomp(vlong, mpint*)
vlong mptov(mpint*)
mpint* uvtomp(uvlong, mpint*)
uvlong mptouv(mpint*)
void mpadd(mpint *b1, mpint *b2, mpint *sum)
void mpmagadd(mpint *b1, mpint *b2, mpint *sum)
void mpsub(mpint *b1, mpint *b2, mpint *diff)
void mpmagsub(mpint *b1, mpint *b2, mpint *diff)
void mpleft(mpint *b, int shift, mpint *res)
void mpright(mpint *b, int shift, mpint *res)
void mpmul(mpint *b1, mpint *b2, mpint *prod)
void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
void mpmod(mpint *b, mpint *m, mpint *remainder)
void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient,
mpint *remainder)
int mpcmp(mpint *b1, mpint *b2)
int mpmagcmp(mpint *b1, mpint *b2)
void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
mpint *y)
void mpinvert(mpint *b, mpint *m, mpint *res)
int mpsignif(mpint *b)
int mplowbits0(mpint *b)
void mpdigdiv(mpdigit *dividend, mpdigit divisor,
mpdigit *quotient)
void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen,
mpdigit *sum)
void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen,
mpdigit *diff)
void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,
mpdigit *p)
int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
CRTpre* crtpre(int nfactors, mpint **factors)
CRTres* crtin(CRTpre *crt, mpint *x)
void crtout(CRTpre *crt, CRTres *r, mpint *x)
void crtprefree(CRTpre *cre)
void crtresfree(CRTres *res)
mpint *mpzero, *mpone, *mptwo
DESCRIPTION
These routines perform extended precision integer arithmetic. The ba‐
sic type is mpint, which points to an array of mpdigits, stored in lit‐
tle-endian order:
typedef struct mpint mpint;
struct mpint
{
int sign; /* +1 or -1 */
int size; /* allocated digits */
int top; /* significant digits */
mpdigit *p;
char flags;
};
The sign of 0 is +1.
The size of mpdigit is architecture-dependent and defined in
/$cputype/include/u.h. Mpints are dynamically allocated and must be
explicitly freed. Operations grow the array of digits as needed.
In general, the result parameters are last in the argument list.
Routines that return an mpint will allocate the mpint if the result pa‐
rameter is nil. This includes strtomp, itomp, uitomp, and btomp.
These functions, in addition to mpnew and mpcopy, will return nil if
the allocation fails.
Input and result parameters may point to the same mpint. The routines
check and copy where necessary.
Mpnew creates an mpint with an initial allocation of n bits. If n is
zero, the allocation will be whatever was specified in the last call to
mpsetminbits or to the initial value, 1056. Mpfree frees an mpint.
Mpbits grows the allocation of b to fit at least n bits. If b->top
doesn't cover n bits, mpbits increases it to do so. Unless you are
writing new basic operations, you can restrict yourself to mpnew(0) and
mpfree(b).
Mpnorm normalizes the representation by trimming any high order zero
digits. All routines except mpbits return normalized results.
Mpcopy creates a new mpint with the same value as b while mpassign sets
the value of new to be that of old.
Mprand creates an n bit random number using the generator gen. Gen
takes a pointer to a string of uchar's and the number to fill in.
Strtomp and mptoa convert between ASCII and mpint representations using
the base indicated. Only the bases 10, 16, 32, and 64 are supported.
Anything else defaults to 16. Strtomp skips any leading spaces or
tabs. Strtomp's scan stops when encountering a digit not valid in the
base. If rptr is not zero, *rptr is set to point to the character im‐
mediately after the string converted. If the parse pterminates before
any digits are found, strtomp return nil. Mptoa returns a pointer to
the filled buffer. If the parameter buf is nil, the buffer is allo‐
cated. Mpfmt can be used with fmtinstall(2) and print(2) to print
hexadecimal representations of mpints. The conventional verb is for
which mp.h provides a
Mptobe and mptole convert an mpint to a byte array. The former creates
a big endian representation, the latter a little endian one. If the
destination buf is not nil, it specifies the buffer of length blen for
the result. If the representation is less than blen bytes, the rest of
the buffer is zero filled. If buf is nil, then a buffer is allocated
and a pointer to it is deposited in the location pointed to by bufp.
Sign is ignored in these conversions, i.e., the byte array version is
always positive.
Betomp, and letomp convert from a big or little endian byte array at
buf of length blen to an mpint. If b is not nil, it refers to a preal‐
located mpint for the result. If b is nil, a new integer is allocated
and returned as the result.
The integer conversions are:
mptoui mpint->unsigned int
uitomp unsigned int->mpint
mptoi mpint->int
itomp int->mpint
mptouv mpint->unsigned vlong
uvtomp unsigned vlong->mpint
mptov mpint->vlong
vtomp vlong->mpint
When converting to the base integer types, if the integer is too large,
the largest integer of the appropriate sign and size is returned.
The mathematical functions are:
mpadd sum = b1 + b2.
mpmagadd
sum = abs(b1) + abs(b2).
mpsub diff = b1 - b2.
mpmagsub
diff = abs(b1) - abs(b2).
mpleft res = b<<shift.
mpright
res = b>>shift.
mpmul prod = b1*b2.
mpexp if m is nil, res = b**e. Otherwise, res = b**e mod m.
mpmod remainder = b % m.
mpdiv quotient = dividend/divisor. remainder = dividend % divisor.
mpcmp returns -1, 0, or +1 as b1 is less than, equal to, or greater
than b2.
mpmagcmp
the same as mpcmp but ignores the sign and just compares magni‐
tudes.
Mpextendedgcd computes the greatest common denominator, d, of a and b.
It also computes x and y such that a*x + b*y = d. Both a and b are re‐
quired to be positive. If called with negative arguments, it will re‐
turn a gcd of 0.
Mpinverse computes the multiplicative inverse of b mod m.
Mpsignif returns the number of significant bits in b. Mplowbits0 re‐
turns the number of consecutive zero bits at the low end of the signif‐
icant bits. For example, for 0x14, mpsignif returns 5 and mplowbits0
returns 2. For 0, mpsignif and mplowbits0 both return 0.
The remaining routines all work on arrays of mpdigit rather than
mpint's. They are the basis of all the other routines. They are sepa‐
rated out to allow them to be rewritten in assembler for each architec‐
ture. There is also a portable C version for each one.
mpdigdiv
quotient = dividend[0:1] / divisor.
mpvecadd
sum[0:alen] = a[0:alen-1] + b[0:blen-1]. We assume alen >= blen
and that sum has room for alen+1 digits.
mpvecsub
diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]. We assume that alen
>= blen and that diff has room for alen digits.
mpvecdigmuladd
p[0:n] += m * b[0:n-1]. This multiplies a an array of digits
times a scalar and adds it to another array. We assume p has
room for n+1 digits.
mpvecdigmulsub
p[0:n] -= m * b[0:n-1]. This multiplies a an array of digits
times a scalar and subtracts it fromo another array. We assume
p has room for n+1 digits. It returns +1 is the result is posi‐
tive and -1 if negative.
mpvecmul
p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]. We assume that p
has room for alen*blen+1 digits.
mpveccmp
This returns -1, 0, or +1 as a - b is negative, 0, or positive.
mptwo, mpone and mpzero are the constants 2, 1 and 0. These cannot be
freed.
Chinese remainder theorem
When computing in a non-prime modulus, n, it is possible to perform the
computations on the residues modulo the prime factors of n instead.
Since these numbers are smaller, multiplication and exponentiation can
be much faster.
Crtin computes the residues of x and returns them in a newly allocated
structure:
typedef struct CRTres CRTres;
{
int n; /* number of residues */
mpint *r[n]; /* residues */
};
Crtout takes a residue representation of a number and converts it back
into the number. It also frees the residue structure.
Crepre saves a copy of the factors and precomputes the constants neces‐
sary for converting the residue form back into a number modulo the
product of the factors. It returns a newly allocated structure con‐
taining values.
Crtprefree and crtresfree free CRTpre and CRTres structures respec‐
tively.
SOURCE
/sys/src/libmp
MP(2)