3 c8b6342d 2005-01-13 devnull 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, mpextendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree \- extended precision arithmetic
4 cfa37a7b 2004-04-10 devnull .SH SYNOPSIS
5 cfa37a7b 2004-04-10 devnull .B #include <u.h>
7 cfa37a7b 2004-04-10 devnull .B #include <libc.h>
9 cfa37a7b 2004-04-10 devnull .B #include <mp.h>
12 cfa37a7b 2004-04-10 devnull mpint* mpnew(int n)
15 cfa37a7b 2004-04-10 devnull void mpfree(mpint *b)
18 cfa37a7b 2004-04-10 devnull void mpsetminbits(int n)
21 cfa37a7b 2004-04-10 devnull void mpbits(mpint *b, int n)
24 cfa37a7b 2004-04-10 devnull void mpnorm(mpint *b)
27 cfa37a7b 2004-04-10 devnull mpint* mpcopy(mpint *b)
30 cfa37a7b 2004-04-10 devnull void mpassign(mpint *old, mpint *new)
33 cfa37a7b 2004-04-10 devnull mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
36 cfa37a7b 2004-04-10 devnull mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
39 cfa37a7b 2004-04-10 devnull char* mptoa(mpint *b, int base, char *buf, int blen)
42 cfa37a7b 2004-04-10 devnull int mpfmt(Fmt*)
45 cfa37a7b 2004-04-10 devnull mpint* betomp(uchar *buf, uint blen, mpint *b)
48 cfa37a7b 2004-04-10 devnull int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
51 cfa37a7b 2004-04-10 devnull mpint* letomp(uchar *buf, uint blen, mpint *b)
54 cfa37a7b 2004-04-10 devnull int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
57 cfa37a7b 2004-04-10 devnull uint mptoui(mpint*)
60 cfa37a7b 2004-04-10 devnull mpint* uitomp(uint, mpint*)
63 cfa37a7b 2004-04-10 devnull int mptoi(mpint*)
66 cfa37a7b 2004-04-10 devnull mpint* itomp(int, mpint*)
69 cfa37a7b 2004-04-10 devnull mpint* vtomp(vlong, mpint*)
72 cfa37a7b 2004-04-10 devnull vlong mptov(mpint*)
75 cfa37a7b 2004-04-10 devnull mpint* uvtomp(uvlong, mpint*)
78 cfa37a7b 2004-04-10 devnull uvlong mptouv(mpint*)
81 cfa37a7b 2004-04-10 devnull void mpadd(mpint *b1, mpint *b2, mpint *sum)
84 cfa37a7b 2004-04-10 devnull void mpmagadd(mpint *b1, mpint *b2, mpint *sum)
87 cfa37a7b 2004-04-10 devnull void mpsub(mpint *b1, mpint *b2, mpint *diff)
90 cfa37a7b 2004-04-10 devnull void mpmagsub(mpint *b1, mpint *b2, mpint *diff)
93 cfa37a7b 2004-04-10 devnull void mpleft(mpint *b, int shift, mpint *res)
96 cfa37a7b 2004-04-10 devnull void mpright(mpint *b, int shift, mpint *res)
99 cfa37a7b 2004-04-10 devnull void mpmul(mpint *b1, mpint *b2, mpint *prod)
102 cfa37a7b 2004-04-10 devnull void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
105 cfa37a7b 2004-04-10 devnull void mpmod(mpint *b, mpint *m, mpint *remainder)
108 cfa37a7b 2004-04-10 devnull void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder)
111 c8b6342d 2005-01-13 devnull mpint* mpfactorial(ulong n)
114 cfa37a7b 2004-04-10 devnull int mpcmp(mpint *b1, mpint *b2)
117 cfa37a7b 2004-04-10 devnull int mpmagcmp(mpint *b1, mpint *b2)
120 cfa37a7b 2004-04-10 devnull void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y)
123 cfa37a7b 2004-04-10 devnull void mpinvert(mpint *b, mpint *m, mpint *res)
126 cfa37a7b 2004-04-10 devnull int mpsignif(mpint *b)
129 cfa37a7b 2004-04-10 devnull int mplowbits0(mpint *b)
132 cfa37a7b 2004-04-10 devnull void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
135 cfa37a7b 2004-04-10 devnull void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum)
138 cfa37a7b 2004-04-10 devnull void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff)
141 cfa37a7b 2004-04-10 devnull void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
144 cfa37a7b 2004-04-10 devnull int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
147 cfa37a7b 2004-04-10 devnull void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p)
150 cfa37a7b 2004-04-10 devnull int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
153 cfa37a7b 2004-04-10 devnull CRTpre* crtpre(int nfactors, mpint **factors)
156 cfa37a7b 2004-04-10 devnull CRTres* crtin(CRTpre *crt, mpint *x)
159 cfa37a7b 2004-04-10 devnull void crtout(CRTpre *crt, CRTres *r, mpint *x)
162 cfa37a7b 2004-04-10 devnull void crtprefree(CRTpre *cre)
165 cfa37a7b 2004-04-10 devnull void crtresfree(CRTres *res)
168 cfa37a7b 2004-04-10 devnull mpint *mpzero, *mpone, *mptwo
169 cfa37a7b 2004-04-10 devnull .SH DESCRIPTION
171 cfa37a7b 2004-04-10 devnull These routines perform extended precision integer arithmetic.
172 cfa37a7b 2004-04-10 devnull The basic type is
173 cfa37a7b 2004-04-10 devnull .BR mpint ,
174 cfa37a7b 2004-04-10 devnull which points to an array of
175 cfa37a7b 2004-04-10 devnull .BR mpdigit s,
176 cfa37a7b 2004-04-10 devnull stored in little-endian order:
179 cfa37a7b 2004-04-10 devnull typedef struct mpint mpint;
180 cfa37a7b 2004-04-10 devnull struct mpint
182 cfa37a7b 2004-04-10 devnull int sign; /* +1 or -1 */
183 cfa37a7b 2004-04-10 devnull int size; /* allocated digits */
184 cfa37a7b 2004-04-10 devnull int top; /* significant digits */
185 cfa37a7b 2004-04-10 devnull mpdigit *p;
186 cfa37a7b 2004-04-10 devnull char flags;
190 cfa37a7b 2004-04-10 devnull The sign of 0 is +1.
192 cfa37a7b 2004-04-10 devnull The size of
193 cfa37a7b 2004-04-10 devnull .B mpdigit
194 cfa37a7b 2004-04-10 devnull is architecture-dependent and defined in
195 cfa37a7b 2004-04-10 devnull .BR /$cputype/include/u.h .
196 cfa37a7b 2004-04-10 devnull .BR Mpint s
197 cfa37a7b 2004-04-10 devnull are dynamically allocated and must be explicitly freed. Operations
198 cfa37a7b 2004-04-10 devnull grow the array of digits as needed.
200 cfa37a7b 2004-04-10 devnull In general, the result parameters are last in the
201 cfa37a7b 2004-04-10 devnull argument list.
203 cfa37a7b 2004-04-10 devnull Routines that return an
204 cfa37a7b 2004-04-10 devnull .B mpint
205 cfa37a7b 2004-04-10 devnull will allocate the
206 cfa37a7b 2004-04-10 devnull .B mpint
207 cfa37a7b 2004-04-10 devnull if the result parameter is
208 cfa37a7b 2004-04-10 devnull .BR nil .
209 cfa37a7b 2004-04-10 devnull This includes
210 cfa37a7b 2004-04-10 devnull .IR strtomp ,
211 cfa37a7b 2004-04-10 devnull .IR itomp ,
212 cfa37a7b 2004-04-10 devnull .IR uitomp ,
214 cfa37a7b 2004-04-10 devnull .IR btomp .
215 cfa37a7b 2004-04-10 devnull These functions, in addition to
216 cfa37a7b 2004-04-10 devnull .I mpnew
218 cfa37a7b 2004-04-10 devnull .IR mpcopy ,
219 cfa37a7b 2004-04-10 devnull will return
221 cfa37a7b 2004-04-10 devnull if the allocation fails.
223 cfa37a7b 2004-04-10 devnull Input and result parameters may point to the same
224 cfa37a7b 2004-04-10 devnull .BR mpint .
225 cfa37a7b 2004-04-10 devnull The routines check and copy where necessary.
227 cfa37a7b 2004-04-10 devnull .I Mpnew
228 cfa37a7b 2004-04-10 devnull creates an
229 cfa37a7b 2004-04-10 devnull .B mpint
230 cfa37a7b 2004-04-10 devnull with an initial allocation of
235 cfa37a7b 2004-04-10 devnull is zero, the allocation will be whatever was specified in the
236 cfa37a7b 2004-04-10 devnull last call to
237 cfa37a7b 2004-04-10 devnull .I mpsetminbits
238 cfa37a7b 2004-04-10 devnull or to the initial value, 1056.
239 cfa37a7b 2004-04-10 devnull .I Mpfree
240 cfa37a7b 2004-04-10 devnull frees an
241 cfa37a7b 2004-04-10 devnull .BR mpint .
242 cfa37a7b 2004-04-10 devnull .I Mpbits
243 cfa37a7b 2004-04-10 devnull grows the allocation of
245 cfa37a7b 2004-04-10 devnull to fit at least
247 cfa37a7b 2004-04-10 devnull bits. If
248 cfa37a7b 2004-04-10 devnull .B b->top
249 cfa37a7b 2004-04-10 devnull doesn't cover
251 cfa37a7b 2004-04-10 devnull bits it increases it to do so.
252 cfa37a7b 2004-04-10 devnull Unless you are writing new basic operations, you
253 cfa37a7b 2004-04-10 devnull can restrict yourself to
254 cfa37a7b 2004-04-10 devnull .B mpnew(0)
256 cfa37a7b 2004-04-10 devnull .BR mpfree(b) .
258 cfa37a7b 2004-04-10 devnull .I Mpnorm
259 cfa37a7b 2004-04-10 devnull normalizes the representation by trimming any high order zero
260 cfa37a7b 2004-04-10 devnull digits. All routines except
261 cfa37a7b 2004-04-10 devnull .B mpbits
262 cfa37a7b 2004-04-10 devnull return normalized results.
264 cfa37a7b 2004-04-10 devnull .I Mpcopy
265 cfa37a7b 2004-04-10 devnull creates a new
266 cfa37a7b 2004-04-10 devnull .B mpint
267 cfa37a7b 2004-04-10 devnull with the same value as
270 cfa37a7b 2004-04-10 devnull .I mpassign
271 cfa37a7b 2004-04-10 devnull sets the value of
273 cfa37a7b 2004-04-10 devnull to be that of
274 cfa37a7b 2004-04-10 devnull .IR old .
276 cfa37a7b 2004-04-10 devnull .I Mprand
277 cfa37a7b 2004-04-10 devnull creates an
279 cfa37a7b 2004-04-10 devnull bit random number using the generator
280 cfa37a7b 2004-04-10 devnull .IR gen .
282 cfa37a7b 2004-04-10 devnull takes a pointer to a string of uchar's and the number
283 cfa37a7b 2004-04-10 devnull to fill in.
285 cfa37a7b 2004-04-10 devnull .I Strtomp
287 cfa37a7b 2004-04-10 devnull .I mptoa
288 cfa37a7b 2004-04-10 devnull convert between
289 cfa37a7b 2004-04-10 devnull .SM ASCII
291 cfa37a7b 2004-04-10 devnull .B mpint
292 cfa37a7b 2004-04-10 devnull representations using the base indicated.
293 cfa37a7b 2004-04-10 devnull Only the bases 10, 16, 32, and 64 are
294 cfa37a7b 2004-04-10 devnull supported. Anything else defaults to 16.
295 cfa37a7b 2004-04-10 devnull .IR Strtomp
296 cfa37a7b 2004-04-10 devnull skips any leading spaces or tabs.
297 cfa37a7b 2004-04-10 devnull .IR Strtomp 's
298 cfa37a7b 2004-04-10 devnull scan stops when encountering a digit not valid in the
299 cfa37a7b 2004-04-10 devnull base. If
301 cfa37a7b 2004-04-10 devnull is not zero,
302 cfa37a7b 2004-04-10 devnull .I *rptr
303 cfa37a7b 2004-04-10 devnull is set to point to the character immediately after the
304 cfa37a7b 2004-04-10 devnull string converted.
305 cfa37a7b 2004-04-10 devnull If the parse pterminates before any digits are found,
306 cfa37a7b 2004-04-10 devnull .I strtomp
308 cfa37a7b 2004-04-10 devnull .BR nil .
309 cfa37a7b 2004-04-10 devnull .I Mptoa
310 cfa37a7b 2004-04-10 devnull returns a pointer to the filled buffer.
311 cfa37a7b 2004-04-10 devnull If the parameter
314 cfa37a7b 2004-04-10 devnull .BR nil ,
315 cfa37a7b 2004-04-10 devnull the buffer is allocated.
316 cfa37a7b 2004-04-10 devnull .I Mpfmt
317 cfa37a7b 2004-04-10 devnull can be used with
318 d32deab1 2020-08-16 rsc .MR fmtinstall (3)
320 d32deab1 2020-08-16 rsc .MR print (3)
321 cfa37a7b 2004-04-10 devnull to print hexadecimal representations of
322 cfa37a7b 2004-04-10 devnull .BR mpint s.
324 cfa37a7b 2004-04-10 devnull .I Mptobe
326 cfa37a7b 2004-04-10 devnull .I mptole
327 cfa37a7b 2004-04-10 devnull convert an
328 cfa37a7b 2004-04-10 devnull .I mpint
329 cfa37a7b 2004-04-10 devnull to a byte array. The former creates a big endian representation,
330 cfa37a7b 2004-04-10 devnull the latter a little endian one.
331 cfa37a7b 2004-04-10 devnull If the destination
334 cfa37a7b 2004-04-10 devnull .BR nil ,
335 cfa37a7b 2004-04-10 devnull it specifies the buffer of length
337 cfa37a7b 2004-04-10 devnull for the result. If the representation
338 cfa37a7b 2004-04-10 devnull is less than
340 cfa37a7b 2004-04-10 devnull bytes, the rest of the buffer is zero filled.
344 cfa37a7b 2004-04-10 devnull .BR nil ,
345 cfa37a7b 2004-04-10 devnull then a buffer is allocated and a pointer to it is
346 cfa37a7b 2004-04-10 devnull deposited in the location pointed to by
347 cfa37a7b 2004-04-10 devnull .IR bufp .
348 cfa37a7b 2004-04-10 devnull Sign is ignored in these conversions, i.e., the byte
349 cfa37a7b 2004-04-10 devnull array version is always positive.
351 cfa37a7b 2004-04-10 devnull .IR Betomp ,
353 cfa37a7b 2004-04-10 devnull .I letomp
354 cfa37a7b 2004-04-10 devnull convert from a big or little endian byte array at
356 cfa37a7b 2004-04-10 devnull of length
359 cfa37a7b 2004-04-10 devnull .IR mpint .
363 cfa37a7b 2004-04-10 devnull .IR nil ,
364 cfa37a7b 2004-04-10 devnull it refers to a preallocated
365 cfa37a7b 2004-04-10 devnull .I mpint
366 cfa37a7b 2004-04-10 devnull for the result.
370 cfa37a7b 2004-04-10 devnull .BR nil ,
371 cfa37a7b 2004-04-10 devnull a new integer is allocated and returned as the result.
373 cfa37a7b 2004-04-10 devnull The integer conversions are:
374 cfa37a7b 2004-04-10 devnull .TF Mptouv
376 cfa37a7b 2004-04-10 devnull .I mptoui
377 cfa37a7b 2004-04-10 devnull .BR mpint -> "unsigned int"
379 cfa37a7b 2004-04-10 devnull .I uitomp
380 cfa37a7b 2004-04-10 devnull .BR "unsigned int" -> mpint
382 cfa37a7b 2004-04-10 devnull .I mptoi
383 cfa37a7b 2004-04-10 devnull .BR mpint -> "int"
385 cfa37a7b 2004-04-10 devnull .I itomp
386 cfa37a7b 2004-04-10 devnull .BR "int" -> mpint
388 cfa37a7b 2004-04-10 devnull .I mptouv
389 cfa37a7b 2004-04-10 devnull .BR mpint -> "unsigned vlong"
391 cfa37a7b 2004-04-10 devnull .I uvtomp
392 cfa37a7b 2004-04-10 devnull .BR "unsigned vlong" -> mpint
394 cfa37a7b 2004-04-10 devnull .I mptov
395 cfa37a7b 2004-04-10 devnull .BR mpint -> "vlong"
397 cfa37a7b 2004-04-10 devnull .I vtomp
398 cfa37a7b 2004-04-10 devnull .BR "vlong" -> mpint
401 cfa37a7b 2004-04-10 devnull When converting to the base integer types, if the integer is too large,
402 cfa37a7b 2004-04-10 devnull the largest integer of the appropriate sign
403 cfa37a7b 2004-04-10 devnull and size is returned.
405 cfa37a7b 2004-04-10 devnull The mathematical functions are:
406 cfa37a7b 2004-04-10 devnull .TF mpmagadd
408 cfa37a7b 2004-04-10 devnull .I mpadd
409 cfa37a7b 2004-04-10 devnull .BR "sum = b1 + b2" .
411 cfa37a7b 2004-04-10 devnull .I mpmagadd
412 cfa37a7b 2004-04-10 devnull .BR "sum = abs(b1) + abs(b2)" .
414 cfa37a7b 2004-04-10 devnull .I mpsub
415 cfa37a7b 2004-04-10 devnull .BR "diff = b1 - b2" .
417 cfa37a7b 2004-04-10 devnull .I mpmagsub
418 cfa37a7b 2004-04-10 devnull .BR "diff = abs(b1) - abs(b2)" .
420 cfa37a7b 2004-04-10 devnull .I mpleft
421 cfa37a7b 2004-04-10 devnull .BR "res = b<<shift" .
423 cfa37a7b 2004-04-10 devnull .I mpright
424 cfa37a7b 2004-04-10 devnull .BR "res = b>>shift" .
426 cfa37a7b 2004-04-10 devnull .I mpmul
427 cfa37a7b 2004-04-10 devnull .BR "prod = b1*b2" .
429 cfa37a7b 2004-04-10 devnull .I mpexp
433 cfa37a7b 2004-04-10 devnull .BR "res = b**e" .
434 cfa37a7b 2004-04-10 devnull Otherwise,
435 cfa37a7b 2004-04-10 devnull .BR "res = b**e mod m" .
437 cfa37a7b 2004-04-10 devnull .I mpmod
438 cfa37a7b 2004-04-10 devnull .BR "remainder = b % m" .
440 cfa37a7b 2004-04-10 devnull .I mpdiv
441 cfa37a7b 2004-04-10 devnull .BR "quotient = dividend/divisor" .
442 cfa37a7b 2004-04-10 devnull .BR "remainder = dividend % divisor" .
444 c8b6342d 2005-01-13 devnull .I mpfactorial
445 c8b6342d 2005-01-13 devnull returns factorial of
448 cfa37a7b 2004-04-10 devnull .I mpcmp
449 cfa37a7b 2004-04-10 devnull returns -1, 0, or +1 as
451 cfa37a7b 2004-04-10 devnull is less than, equal to, or greater than
452 cfa37a7b 2004-04-10 devnull .IR b2 .
454 cfa37a7b 2004-04-10 devnull .I mpmagcmp
455 cfa37a7b 2004-04-10 devnull the same as
456 cfa37a7b 2004-04-10 devnull .I mpcmp
457 cfa37a7b 2004-04-10 devnull but ignores the sign and just compares magnitudes.
460 cfa37a7b 2004-04-10 devnull .I Mpextendedgcd
461 cfa37a7b 2004-04-10 devnull computes the greatest common denominator,
467 cfa37a7b 2004-04-10 devnull It also computes
471 cfa37a7b 2004-04-10 devnull such that
472 cfa37a7b 2004-04-10 devnull .BR "a*x + b*y = d" .
477 cfa37a7b 2004-04-10 devnull are required to be positive.
478 cfa37a7b 2004-04-10 devnull If called with negative arguments, it will
479 cfa37a7b 2004-04-10 devnull return a gcd of 0.
481 cfa37a7b 2004-04-10 devnull .I Mpinverse
482 cfa37a7b 2004-04-10 devnull computes the multiplicative inverse of
487 cfa37a7b 2004-04-10 devnull .I Mpsignif
488 cfa37a7b 2004-04-10 devnull returns the bit offset of the left most 1 bit in
490 cfa37a7b 2004-04-10 devnull .I Mplowbits0
491 cfa37a7b 2004-04-10 devnull returns the bit offset of the right most 1 bit.
492 cfa37a7b 2004-04-10 devnull For example, for 0x14,
493 cfa37a7b 2004-04-10 devnull .I mpsignif
494 cfa37a7b 2004-04-10 devnull would return 4 and
495 cfa37a7b 2004-04-10 devnull .I mplowbits0
496 cfa37a7b 2004-04-10 devnull would return 2.
498 cfa37a7b 2004-04-10 devnull The remaining routines all work on arrays of
499 cfa37a7b 2004-04-10 devnull .B mpdigit
500 cfa37a7b 2004-04-10 devnull rather than
501 cfa37a7b 2004-04-10 devnull .BR mpint 's.
502 cfa37a7b 2004-04-10 devnull They are the basis of all the other routines. They are separated out
503 cfa37a7b 2004-04-10 devnull to allow them to be rewritten in assembler for each architecture. There
504 cfa37a7b 2004-04-10 devnull is also a portable C version for each one.
505 cfa37a7b 2004-04-10 devnull .TF mpvecdigmuladd
507 cfa37a7b 2004-04-10 devnull .I mpdigdiv
508 cfa37a7b 2004-04-10 devnull .BR "quotient = dividend[0:1] / divisor" .
510 cfa37a7b 2004-04-10 devnull .I mpvecadd
511 cfa37a7b 2004-04-10 devnull .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
512 cfa37a7b 2004-04-10 devnull We assume alen >= blen and that sum has room for alen+1 digits.
514 cfa37a7b 2004-04-10 devnull .I mpvecsub
515 cfa37a7b 2004-04-10 devnull .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
516 cfa37a7b 2004-04-10 devnull We assume that alen >= blen and that diff has room for alen digits.
518 cfa37a7b 2004-04-10 devnull .I mpvecdigmuladd
519 cfa37a7b 2004-04-10 devnull .BR "p[0:n] += m * b[0:n-1]" .
520 cfa37a7b 2004-04-10 devnull This multiplies a an array of digits times a scalar and adds it to another array.
521 cfa37a7b 2004-04-10 devnull We assume p has room for n+1 digits.
523 cfa37a7b 2004-04-10 devnull .I mpvecdigmulsub
524 cfa37a7b 2004-04-10 devnull .BR "p[0:n] -= m * b[0:n-1]" .
525 cfa37a7b 2004-04-10 devnull This multiplies a an array of digits times a scalar and subtracts it fromo another array.
526 cfa37a7b 2004-04-10 devnull We assume p has room for n+1 digits. It returns +1 is the result is positive and
527 cfa37a7b 2004-04-10 devnull -1 if negative.
529 cfa37a7b 2004-04-10 devnull .I mpvecmul
530 cfa37a7b 2004-04-10 devnull .BR "p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]" .
531 cfa37a7b 2004-04-10 devnull We assume that p has room for alen*blen+1 digits.
533 cfa37a7b 2004-04-10 devnull .I mpveccmp
534 cfa37a7b 2004-04-10 devnull This returns -1, 0, or +1 as a - b is negative, 0, or positive.
537 cfa37a7b 2004-04-10 devnull .IR mptwo ,
538 cfa37a7b 2004-04-10 devnull .I mpone
540 cfa37a7b 2004-04-10 devnull .I mpzero
541 cfa37a7b 2004-04-10 devnull are the constants 2, 1 and 0. These cannot be freed.
542 cfa37a7b 2004-04-10 devnull .SS "Chinese remainder theorem
544 cfa37a7b 2004-04-10 devnull When computing in a non-prime modulus,
546 cfa37a7b 2004-04-10 devnull it is possible to perform the computations on the residues modulo the prime
547 cfa37a7b 2004-04-10 devnull factors of
549 cfa37a7b 2004-04-10 devnull instead. Since these numbers are smaller, multiplication and exponentiation
550 cfa37a7b 2004-04-10 devnull can be much faster.
552 cfa37a7b 2004-04-10 devnull .I Crtin
553 cfa37a7b 2004-04-10 devnull computes the residues of
555 cfa37a7b 2004-04-10 devnull and returns them in a newly allocated structure:
557 cfa37a7b 2004-04-10 devnull typedef struct CRTres CRTres;
559 cfa37a7b 2004-04-10 devnull int n; // number of residues
560 cfa37a7b 2004-04-10 devnull mpint *r[n]; // residues
564 cfa37a7b 2004-04-10 devnull .I Crtout
565 cfa37a7b 2004-04-10 devnull takes a residue representation of a number and converts it back into
566 cfa37a7b 2004-04-10 devnull the number. It also frees the residue structure.
568 cfa37a7b 2004-04-10 devnull .I Crepre
569 cfa37a7b 2004-04-10 devnull saves a copy of the factors and precomputes the constants necessary
570 cfa37a7b 2004-04-10 devnull for converting the residue form back into a number modulo
571 cfa37a7b 2004-04-10 devnull the product of the factors. It returns a newly allocated structure
572 cfa37a7b 2004-04-10 devnull containing values.
574 cfa37a7b 2004-04-10 devnull .I Crtprefree
576 cfa37a7b 2004-04-10 devnull .I crtresfree
578 cfa37a7b 2004-04-10 devnull .I CRTpre
580 cfa37a7b 2004-04-10 devnull .I CRTres
581 cfa37a7b 2004-04-10 devnull structures respectively.
582 cfa37a7b 2004-04-10 devnull .SH SOURCE
583 c3674de4 2005-01-11 devnull .B \*9/src/libmp
