.TH MP 2
.SH 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, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree \- extended precision arithmetic
+mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy, mpassign, mprand, mpnrand, strtomp, mpfmt, mptoa, betomp, mptobe, mptober, letomp, mptole, mptolel, mptoui, uitomp, mptoi, itomp, uvtomp, mptouv, vtomp, mptov, mptod, dtomp, mpdigdiv, mpadd, mpsub, mpleft, mpright, mpmul, mpexp, mpmod, mpmodadd, mpmodsub, mpmodmul, mpdiv, mpcmp, mpsel, mpfactorial, mpextendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree \- extended precision arithmetic
.SH SYNOPSIS
.B #include <u.h>
.br
void mpbits(mpint *b, int n)
.PP
.B
-void mpnorm(mpint *b)
+mpint* mpnorm(mpint *b)
.PP
.B
mpint* mpcopy(mpint *b)
mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
.PP
.B
+mpint* mpnrand(mpint *n, void (*gen)(uchar*, int), mpint *b)
+.PP
+.B
mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
.PP
.B
int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
.PP
.B
+void mptober(mpint *b, uchar *buf, int blen)
+.PP
+.B
mpint* letomp(uchar *buf, uint blen, mpint *b)
.PP
.B
int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
.PP
.B
+void mptolel(mpint *b, uchar *buf, int blen)
+.PP
+.B
uint mptoui(mpint*)
.PP
.B
uvlong mptouv(mpint*)
.PP
.B
+mpint* dtomp(double, mpint*)
+.PP
+.B
+double mptod(mpint*)
+.PP
+.B
void mpadd(mpint *b1, mpint *b2, mpint *sum)
.PP
.B
void mpright(mpint *b, int shift, mpint *res)
.PP
.B
+void mpand(mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+void mpbic(mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+void mpor(mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+void mpnot(mpint *b, mpint *res)
+.PP
+.B
+void mpxor(mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+void mptrunc(mpint *b, int n, mpint *res)
+.PP
+.B
+void mpxtend(mpint *b, int n, mpint *res)
+.PP
+.B
+void mpasr(mpint *b, int n, mpint *res)
+.PP
+.B
void mpmul(mpint *b1, mpint *b2, mpint *prod)
.PP
.B
mpint *remainder)
.PP
.B
+void mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum)
+.PP
+.B
+void mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff)
+.PP
+.B
+void mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod)
+.PP
+.B
int mpcmp(mpint *b1, mpint *b2)
.PP
.B
int mpmagcmp(mpint *b1, mpint *b2)
.PP
.B
+void mpsel(int s, mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+mpint* mpfactorial(ulong n)
+.PP
+.B
void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
.br
.B
.IR strtomp ,
.IR itomp ,
.IR uitomp ,
+.IR btomp ,
and
-.IR btomp .
+.IR dtomp .
These functions, in addition to
.I mpnew
and
takes a pointer to a string of uchar's and the number
to fill in.
.PP
+.I Mpnrand
+uses
+.I gen
+to generate a uniform random number
+.IR x ,
+.if t 0 ≤ \fIx\fR < \fIn\fR.
+.if n 0 ≤ x < n.
+.PP
.I Strtomp
and
.I mptoa
and
.B mpint
representations using the base indicated.
-Only the bases 10, 16, 32, and 64 are
-supported. Anything else defaults to 16.
+Only the bases 2, 4, 8, 10, 16, 32, and 64 are
+supported.
.IR Strtomp
skips any leading spaces or tabs.
.IR Strtomp 's
scan stops when encountering a digit not valid in the
base. If
+.I base
+is zero then C-style prefixes are interpreted to
+find the base:
+.B 0x
+for hexadecimal,
+.B 0b
+for binary and
+.B 0
+for octal. Otherwise decimal is assumed.
.I rptr
is not zero,
.I *rptr
return
.BR nil .
.I Mptoa
-returns a pointer to the filled buffer.
+returns a pointer to the
+.SM ASCII
+filled buffer.
If the parameter
.I buf
is
.BR nil ,
the buffer is allocated.
+Setting
+.I base
+to zero uses hexadecimal default.
.I Mpfmt
can be used with
.IR fmtinstall (2)
and
.IR print (2)
-to print hexadecimal representations of
+to print
+.SM ASCII
+representations of
.BR mpint s.
The conventional verb is
.LR B ,
.I mp.h
provides a
.LR pragma .
+The precision in the format string changes the base,
+defaulting to hexadecimal when omited.
.PP
.I Mptobe
and
Sign is ignored in these conversions, i.e., the byte
array version is always positive.
.PP
+.I Mptober
+and
+.I mptolel
+fill
+.I blen
+lower bytes of an
+.I mpint
+into a fixed length byte array.
+.I Mptober
+fills the bytes right adjusted in big endian order so that the least
+significant byte is at
+.I buf[blen-1]
+while
+.I mptolel
+fills in little endian order; left adjusted; so that the least
+significat byte is filled into
+.IR buf[0] .
+.PP
.IR Betomp ,
and
.I letomp
.BR nil ,
a new integer is allocated and returned as the result.
.PP
-The integer conversions are:
+The integer (and floating point) conversions are:
.TF Mptouv
.TP
.I mptoui
.TP
.I vtomp
.BR "vlong" -> mpint
+.TP
+.I mptod
+.BR mpint -> "double"
+.TP
+.I dtomp
+.BR "double" -> mpint
.PD
.PP
When converting to the base integer types, if the integer is too large,
the largest integer of the appropriate sign
and size is returned.
.PP
+When converting to and from floating point, results are rounded using IEEE 754 "round to nearest".
+If the integer is too large in magnitude,
+.I mptod
+returns infinity of the appropriate sign.
+.PP
The mathematical functions are:
-.TF mpmagadd
+.TF mpfactorial
.TP
.I mpadd
.BR "sum = b1 + b2" .
the same as
.I mpcmp
but ignores the sign and just compares magnitudes.
+.TP
+.I mpsel
+assigns
+.I b1
+to
+.I res
+when
+.I s
+is not zero, otherwise
+.I b2
+is assigned to
+.IR res .
+.TP
+.I mpfactorial
+returns \fIn\fR!.
+.PD
+.PP
+Logical operations (treating negative numbers using two's complement):
+.TF mpxtend_
+.TP
+.I mpand
+.BR "res = b1 & b2" .
+.TP
+.I mpbic
+.BR "res = b1 & ~b2" .
+.TP
+.I mpor
+.BR "res = b1 | b2" .
+.TP
+.I mpxor
+.BR "res = b1 ^ b2" .
+.TP
+.I mpnot
+.BR "res = ~b1" .
+.TP
+.I mpasr
+.BR "res = b>>shift"
+(\fImpasr\fR, unlike
+.IR mpright ,
+uses two's complement).
+.TP
+.I mptrunc
+truncates
+.I b
+to
+.I n
+bits and stores the result in
+.IR res .
+The result is never negative.
+.TP
+.I mpxtend
+truncates
+.I b
+to
+.I n
+bits, sign extends the MSB and stores the result in
+.IR res .
+.PD
+.PP
+Modular arithmetic:
+.TF mpmodmul_
+.TP
+.I mpmodadd
+.BR "sum = b1+b2 mod m" .
+.TP
+.I mpmodsub
+.BR "diff = b1-b2 mod m" .
+.TP
+.I mpmodmul
+.BR "prod = b1*b2 mod m" .
.PD
.PP
.I Mpextendedgcd
-1 if negative.
.TP
.I mpvecmul
-.BR "p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]" .
-We assume that p has room for alen*blen+1 digits.
+.BR "p[0:alen+blen] = a[0:alen-1] * b[0:blen-1]" .
+We assume that p has room for alen+blen+1 digits.
.TP
.I mpveccmp
This returns -1, 0, or +1 as a - b is negative, 0, or positive.
and
.I mpzero
are the constants 2, 1 and 0. These cannot be freed.
+.SS "Time invariant computation"
+.PP
+In the field of cryptography, it is sometimes neccesary to implement
+algorithms such that the runtime of the algorithm is not depdenent on
+the input data. This library provides partial support for time
+invariant computation with the
+.I MPtimesafe
+flag that can be set on input or destination operands to request timing
+safe operation. The result of a timing safe operation will also have the
+.I MPtimesafe
+flag set and is not normalized.
.SS "Chinese remainder theorem
.PP
When computing in a non-prime modulus,