Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
MP(3)			   Library Functions Manual			 MP(3)

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, mpfactorial, mpcmp,	 mpex-
       tendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmul-
       sub, mpvecadd, mpvecsub,	mpveccmp, mpvecmul, mpmagcmp, mpmagadd,	mpmag-
       sub, 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)

       mpint*	 mpfactorial(ulong n)

       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 it 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(3) and print(3) to print
       hexadecimal representations of mpints.

       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.

       mpfactorial
	      returns factorial	of n.

       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 bit	offset of the left most	1 bit  in  b.	Mplow-
       bits0 returns the bit offset of the right most 1	bit.  For example, for
       0x14, mpsignif would return 4 and mplowbits0 would return 2.

       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
       /usr/local/plan9/src/libmp

									 MP(3)

NAME | SYNOPSIS | DESCRIPTION | SOURCE

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=mp&sektion=3&manpath=FreeBSD+12.0-RELEASE+and+Ports>

home | help