4 cfa37a7b 2004-04-10 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, mpcmp, mpextendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree \- extended precision arithmetic
5 cfa37a7b 2004-04-10 devnull .SH SYNOPSIS
6 cfa37a7b 2004-04-10 devnull .B #include <u.h>
8 cfa37a7b 2004-04-10 devnull .B #include <libc.h>
10 cfa37a7b 2004-04-10 devnull .B #include <mp.h>
13 cfa37a7b 2004-04-10 devnull mpint* mpnew(int n)
16 cfa37a7b 2004-04-10 devnull void mpfree(mpint *b)
19 cfa37a7b 2004-04-10 devnull void mpsetminbits(int n)
22 cfa37a7b 2004-04-10 devnull void mpbits(mpint *b, int n)
25 cfa37a7b 2004-04-10 devnull void mpnorm(mpint *b)
28 cfa37a7b 2004-04-10 devnull mpint* mpcopy(mpint *b)
31 cfa37a7b 2004-04-10 devnull void mpassign(mpint *old, mpint *new)
34 cfa37a7b 2004-04-10 devnull mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
37 cfa37a7b 2004-04-10 devnull mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
40 cfa37a7b 2004-04-10 devnull char* mptoa(mpint *b, int base, char *buf, int blen)
43 cfa37a7b 2004-04-10 devnull int mpfmt(Fmt*)
46 cfa37a7b 2004-04-10 devnull mpint* betomp(uchar *buf, uint blen, mpint *b)
49 cfa37a7b 2004-04-10 devnull int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
52 cfa37a7b 2004-04-10 devnull mpint* letomp(uchar *buf, uint blen, mpint *b)
55 cfa37a7b 2004-04-10 devnull int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
58 cfa37a7b 2004-04-10 devnull uint mptoui(mpint*)
61 cfa37a7b 2004-04-10 devnull mpint* uitomp(uint, mpint*)
64 cfa37a7b 2004-04-10 devnull int mptoi(mpint*)
67 cfa37a7b 2004-04-10 devnull mpint* itomp(int, mpint*)
70 cfa37a7b 2004-04-10 devnull mpint* vtomp(vlong, mpint*)
73 cfa37a7b 2004-04-10 devnull vlong mptov(mpint*)
76 cfa37a7b 2004-04-10 devnull mpint* uvtomp(uvlong, mpint*)
79 cfa37a7b 2004-04-10 devnull uvlong mptouv(mpint*)
82 cfa37a7b 2004-04-10 devnull void mpadd(mpint *b1, mpint *b2, mpint *sum)
85 cfa37a7b 2004-04-10 devnull void mpmagadd(mpint *b1, mpint *b2, mpint *sum)
88 cfa37a7b 2004-04-10 devnull void mpsub(mpint *b1, mpint *b2, mpint *diff)
91 cfa37a7b 2004-04-10 devnull void mpmagsub(mpint *b1, mpint *b2, mpint *diff)
94 cfa37a7b 2004-04-10 devnull void mpleft(mpint *b, int shift, mpint *res)
97 cfa37a7b 2004-04-10 devnull void mpright(mpint *b, int shift, mpint *res)
100 cfa37a7b 2004-04-10 devnull void mpmul(mpint *b1, mpint *b2, mpint *prod)
103 cfa37a7b 2004-04-10 devnull void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
106 cfa37a7b 2004-04-10 devnull void mpmod(mpint *b, mpint *m, mpint *remainder)
109 cfa37a7b 2004-04-10 devnull void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder)
112 cfa37a7b 2004-04-10 devnull int mpcmp(mpint *b1, mpint *b2)
115 cfa37a7b 2004-04-10 devnull int mpmagcmp(mpint *b1, mpint *b2)
118 cfa37a7b 2004-04-10 devnull void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y)
121 cfa37a7b 2004-04-10 devnull void mpinvert(mpint *b, mpint *m, mpint *res)
124 cfa37a7b 2004-04-10 devnull int mpsignif(mpint *b)
127 cfa37a7b 2004-04-10 devnull int mplowbits0(mpint *b)
130 cfa37a7b 2004-04-10 devnull void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
133 cfa37a7b 2004-04-10 devnull void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum)
136 cfa37a7b 2004-04-10 devnull void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff)
139 cfa37a7b 2004-04-10 devnull void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
142 cfa37a7b 2004-04-10 devnull int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
145 cfa37a7b 2004-04-10 devnull void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p)
148 cfa37a7b 2004-04-10 devnull int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
151 cfa37a7b 2004-04-10 devnull CRTpre* crtpre(int nfactors, mpint **factors)
154 cfa37a7b 2004-04-10 devnull CRTres* crtin(CRTpre *crt, mpint *x)
157 cfa37a7b 2004-04-10 devnull void crtout(CRTpre *crt, CRTres *r, mpint *x)
160 cfa37a7b 2004-04-10 devnull void crtprefree(CRTpre *cre)
163 cfa37a7b 2004-04-10 devnull void crtresfree(CRTres *res)
166 cfa37a7b 2004-04-10 devnull mpint *mpzero, *mpone, *mptwo
167 cfa37a7b 2004-04-10 devnull .SH DESCRIPTION
169 cfa37a7b 2004-04-10 devnull These routines perform extended precision integer arithmetic.
170 cfa37a7b 2004-04-10 devnull The basic type is
171 cfa37a7b 2004-04-10 devnull .BR mpint ,
172 cfa37a7b 2004-04-10 devnull which points to an array of
173 cfa37a7b 2004-04-10 devnull .BR mpdigit s,
174 cfa37a7b 2004-04-10 devnull stored in little-endian order:
177 cfa37a7b 2004-04-10 devnull typedef struct mpint mpint;
178 cfa37a7b 2004-04-10 devnull struct mpint
180 cfa37a7b 2004-04-10 devnull int sign; /* +1 or -1 */
181 cfa37a7b 2004-04-10 devnull int size; /* allocated digits */
182 cfa37a7b 2004-04-10 devnull int top; /* significant digits */
183 cfa37a7b 2004-04-10 devnull mpdigit *p;
184 cfa37a7b 2004-04-10 devnull char flags;
188 cfa37a7b 2004-04-10 devnull The sign of 0 is +1.
190 cfa37a7b 2004-04-10 devnull The size of
191 cfa37a7b 2004-04-10 devnull .B mpdigit
192 cfa37a7b 2004-04-10 devnull is architecture-dependent and defined in
193 cfa37a7b 2004-04-10 devnull .BR /$cputype/include/u.h .
194 cfa37a7b 2004-04-10 devnull .BR Mpint s
195 cfa37a7b 2004-04-10 devnull are dynamically allocated and must be explicitly freed. Operations
196 cfa37a7b 2004-04-10 devnull grow the array of digits as needed.
198 cfa37a7b 2004-04-10 devnull In general, the result parameters are last in the
199 cfa37a7b 2004-04-10 devnull argument list.
201 cfa37a7b 2004-04-10 devnull Routines that return an
202 cfa37a7b 2004-04-10 devnull .B mpint
203 cfa37a7b 2004-04-10 devnull will allocate the
204 cfa37a7b 2004-04-10 devnull .B mpint
205 cfa37a7b 2004-04-10 devnull if the result parameter is
206 cfa37a7b 2004-04-10 devnull .BR nil .
207 cfa37a7b 2004-04-10 devnull This includes
208 cfa37a7b 2004-04-10 devnull .IR strtomp ,
209 cfa37a7b 2004-04-10 devnull .IR itomp ,
210 cfa37a7b 2004-04-10 devnull .IR uitomp ,
212 cfa37a7b 2004-04-10 devnull .IR btomp .
213 cfa37a7b 2004-04-10 devnull These functions, in addition to
214 cfa37a7b 2004-04-10 devnull .I mpnew
216 cfa37a7b 2004-04-10 devnull .IR mpcopy ,
217 cfa37a7b 2004-04-10 devnull will return
219 cfa37a7b 2004-04-10 devnull if the allocation fails.
221 cfa37a7b 2004-04-10 devnull Input and result parameters may point to the same
222 cfa37a7b 2004-04-10 devnull .BR mpint .
223 cfa37a7b 2004-04-10 devnull The routines check and copy where necessary.
225 cfa37a7b 2004-04-10 devnull .I Mpnew
226 cfa37a7b 2004-04-10 devnull creates an
227 cfa37a7b 2004-04-10 devnull .B mpint
228 cfa37a7b 2004-04-10 devnull with an initial allocation of
233 cfa37a7b 2004-04-10 devnull is zero, the allocation will be whatever was specified in the
234 cfa37a7b 2004-04-10 devnull last call to
235 cfa37a7b 2004-04-10 devnull .I mpsetminbits
236 cfa37a7b 2004-04-10 devnull or to the initial value, 1056.
237 cfa37a7b 2004-04-10 devnull .I Mpfree
238 cfa37a7b 2004-04-10 devnull frees an
239 cfa37a7b 2004-04-10 devnull .BR mpint .
240 cfa37a7b 2004-04-10 devnull .I Mpbits
241 cfa37a7b 2004-04-10 devnull grows the allocation of
243 cfa37a7b 2004-04-10 devnull to fit at least
245 cfa37a7b 2004-04-10 devnull bits. If
246 cfa37a7b 2004-04-10 devnull .B b->top
247 cfa37a7b 2004-04-10 devnull doesn't cover
249 cfa37a7b 2004-04-10 devnull bits it increases it to do so.
250 cfa37a7b 2004-04-10 devnull Unless you are writing new basic operations, you
251 cfa37a7b 2004-04-10 devnull can restrict yourself to
252 cfa37a7b 2004-04-10 devnull .B mpnew(0)
254 cfa37a7b 2004-04-10 devnull .BR mpfree(b) .
256 cfa37a7b 2004-04-10 devnull .I Mpnorm
257 cfa37a7b 2004-04-10 devnull normalizes the representation by trimming any high order zero
258 cfa37a7b 2004-04-10 devnull digits. All routines except
259 cfa37a7b 2004-04-10 devnull .B mpbits
260 cfa37a7b 2004-04-10 devnull return normalized results.
262 cfa37a7b 2004-04-10 devnull .I Mpcopy
263 cfa37a7b 2004-04-10 devnull creates a new
264 cfa37a7b 2004-04-10 devnull .B mpint
265 cfa37a7b 2004-04-10 devnull with the same value as
268 cfa37a7b 2004-04-10 devnull .I mpassign
269 cfa37a7b 2004-04-10 devnull sets the value of
271 cfa37a7b 2004-04-10 devnull to be that of
272 cfa37a7b 2004-04-10 devnull .IR old .
274 cfa37a7b 2004-04-10 devnull .I Mprand
275 cfa37a7b 2004-04-10 devnull creates an
277 cfa37a7b 2004-04-10 devnull bit random number using the generator
278 cfa37a7b 2004-04-10 devnull .IR gen .
280 cfa37a7b 2004-04-10 devnull takes a pointer to a string of uchar's and the number
281 cfa37a7b 2004-04-10 devnull to fill in.
283 cfa37a7b 2004-04-10 devnull .I Strtomp
285 cfa37a7b 2004-04-10 devnull .I mptoa
286 cfa37a7b 2004-04-10 devnull convert between
287 cfa37a7b 2004-04-10 devnull .SM ASCII
289 cfa37a7b 2004-04-10 devnull .B mpint
290 cfa37a7b 2004-04-10 devnull representations using the base indicated.
291 cfa37a7b 2004-04-10 devnull Only the bases 10, 16, 32, and 64 are
292 cfa37a7b 2004-04-10 devnull supported. Anything else defaults to 16.
293 cfa37a7b 2004-04-10 devnull .IR Strtomp
294 cfa37a7b 2004-04-10 devnull skips any leading spaces or tabs.
295 cfa37a7b 2004-04-10 devnull .IR Strtomp 's
296 cfa37a7b 2004-04-10 devnull scan stops when encountering a digit not valid in the
297 cfa37a7b 2004-04-10 devnull base. If
299 cfa37a7b 2004-04-10 devnull is not zero,
300 cfa37a7b 2004-04-10 devnull .I *rptr
301 cfa37a7b 2004-04-10 devnull is set to point to the character immediately after the
302 cfa37a7b 2004-04-10 devnull string converted.
303 cfa37a7b 2004-04-10 devnull If the parse pterminates before any digits are found,
304 cfa37a7b 2004-04-10 devnull .I strtomp
306 cfa37a7b 2004-04-10 devnull .BR nil .
307 cfa37a7b 2004-04-10 devnull .I Mptoa
308 cfa37a7b 2004-04-10 devnull returns a pointer to the filled buffer.
309 cfa37a7b 2004-04-10 devnull If the parameter
312 cfa37a7b 2004-04-10 devnull .BR nil ,
313 cfa37a7b 2004-04-10 devnull the buffer is allocated.
314 cfa37a7b 2004-04-10 devnull .I Mpfmt
315 cfa37a7b 2004-04-10 devnull can be used with
316 bf8a59fa 2004-04-11 devnull .IR fmtinstall (3)
318 bf8a59fa 2004-04-11 devnull .IR print (3)
319 cfa37a7b 2004-04-10 devnull to print hexadecimal representations of
320 cfa37a7b 2004-04-10 devnull .BR mpint s.
322 cfa37a7b 2004-04-10 devnull .I Mptobe
324 cfa37a7b 2004-04-10 devnull .I mptole
325 cfa37a7b 2004-04-10 devnull convert an
326 cfa37a7b 2004-04-10 devnull .I mpint
327 cfa37a7b 2004-04-10 devnull to a byte array. The former creates a big endian representation,
328 cfa37a7b 2004-04-10 devnull the latter a little endian one.
329 cfa37a7b 2004-04-10 devnull If the destination
332 cfa37a7b 2004-04-10 devnull .BR nil ,
333 cfa37a7b 2004-04-10 devnull it specifies the buffer of length
335 cfa37a7b 2004-04-10 devnull for the result. If the representation
336 cfa37a7b 2004-04-10 devnull is less than
338 cfa37a7b 2004-04-10 devnull bytes, the rest of the buffer is zero filled.
342 cfa37a7b 2004-04-10 devnull .BR nil ,
343 cfa37a7b 2004-04-10 devnull then a buffer is allocated and a pointer to it is
344 cfa37a7b 2004-04-10 devnull deposited in the location pointed to by
345 cfa37a7b 2004-04-10 devnull .IR bufp .
346 cfa37a7b 2004-04-10 devnull Sign is ignored in these conversions, i.e., the byte
347 cfa37a7b 2004-04-10 devnull array version is always positive.
349 cfa37a7b 2004-04-10 devnull .IR Betomp ,
351 cfa37a7b 2004-04-10 devnull .I letomp
352 cfa37a7b 2004-04-10 devnull convert from a big or little endian byte array at
354 cfa37a7b 2004-04-10 devnull of length
357 cfa37a7b 2004-04-10 devnull .IR mpint .
361 cfa37a7b 2004-04-10 devnull .IR nil ,
362 cfa37a7b 2004-04-10 devnull it refers to a preallocated
363 cfa37a7b 2004-04-10 devnull .I mpint
364 cfa37a7b 2004-04-10 devnull for the result.
368 cfa37a7b 2004-04-10 devnull .BR nil ,
369 cfa37a7b 2004-04-10 devnull a new integer is allocated and returned as the result.
371 cfa37a7b 2004-04-10 devnull The integer conversions are:
372 cfa37a7b 2004-04-10 devnull .TF Mptouv
374 cfa37a7b 2004-04-10 devnull .I mptoui
375 cfa37a7b 2004-04-10 devnull .BR mpint -> "unsigned int"
377 cfa37a7b 2004-04-10 devnull .I uitomp
378 cfa37a7b 2004-04-10 devnull .BR "unsigned int" -> mpint
380 cfa37a7b 2004-04-10 devnull .I mptoi
381 cfa37a7b 2004-04-10 devnull .BR mpint -> "int"
383 cfa37a7b 2004-04-10 devnull .I itomp
384 cfa37a7b 2004-04-10 devnull .BR "int" -> mpint
386 cfa37a7b 2004-04-10 devnull .I mptouv
387 cfa37a7b 2004-04-10 devnull .BR mpint -> "unsigned vlong"
389 cfa37a7b 2004-04-10 devnull .I uvtomp
390 cfa37a7b 2004-04-10 devnull .BR "unsigned vlong" -> mpint
392 cfa37a7b 2004-04-10 devnull .I mptov
393 cfa37a7b 2004-04-10 devnull .BR mpint -> "vlong"
395 cfa37a7b 2004-04-10 devnull .I vtomp
396 cfa37a7b 2004-04-10 devnull .BR "vlong" -> mpint
399 cfa37a7b 2004-04-10 devnull When converting to the base integer types, if the integer is too large,
400 cfa37a7b 2004-04-10 devnull the largest integer of the appropriate sign
401 cfa37a7b 2004-04-10 devnull and size is returned.
403 cfa37a7b 2004-04-10 devnull The mathematical functions are:
404 cfa37a7b 2004-04-10 devnull .TF mpmagadd
406 cfa37a7b 2004-04-10 devnull .I mpadd
407 cfa37a7b 2004-04-10 devnull .BR "sum = b1 + b2" .
409 cfa37a7b 2004-04-10 devnull .I mpmagadd
410 cfa37a7b 2004-04-10 devnull .BR "sum = abs(b1) + abs(b2)" .
412 cfa37a7b 2004-04-10 devnull .I mpsub
413 cfa37a7b 2004-04-10 devnull .BR "diff = b1 - b2" .
415 cfa37a7b 2004-04-10 devnull .I mpmagsub
416 cfa37a7b 2004-04-10 devnull .BR "diff = abs(b1) - abs(b2)" .
418 cfa37a7b 2004-04-10 devnull .I mpleft
419 cfa37a7b 2004-04-10 devnull .BR "res = b<<shift" .
421 cfa37a7b 2004-04-10 devnull .I mpright
422 cfa37a7b 2004-04-10 devnull .BR "res = b>>shift" .
424 cfa37a7b 2004-04-10 devnull .I mpmul
425 cfa37a7b 2004-04-10 devnull .BR "prod = b1*b2" .
427 cfa37a7b 2004-04-10 devnull .I mpexp
431 cfa37a7b 2004-04-10 devnull .BR "res = b**e" .
432 cfa37a7b 2004-04-10 devnull Otherwise,
433 cfa37a7b 2004-04-10 devnull .BR "res = b**e mod m" .
435 cfa37a7b 2004-04-10 devnull .I mpmod
436 cfa37a7b 2004-04-10 devnull .BR "remainder = b % m" .
438 cfa37a7b 2004-04-10 devnull .I mpdiv
439 cfa37a7b 2004-04-10 devnull .BR "quotient = dividend/divisor" .
440 cfa37a7b 2004-04-10 devnull .BR "remainder = dividend % divisor" .
442 cfa37a7b 2004-04-10 devnull .I mpcmp
443 cfa37a7b 2004-04-10 devnull returns -1, 0, or +1 as
445 cfa37a7b 2004-04-10 devnull is less than, equal to, or greater than
446 cfa37a7b 2004-04-10 devnull .IR b2 .
448 cfa37a7b 2004-04-10 devnull .I mpmagcmp
449 cfa37a7b 2004-04-10 devnull the same as
450 cfa37a7b 2004-04-10 devnull .I mpcmp
451 cfa37a7b 2004-04-10 devnull but ignores the sign and just compares magnitudes.
454 cfa37a7b 2004-04-10 devnull .I Mpextendedgcd
455 cfa37a7b 2004-04-10 devnull computes the greatest common denominator,
461 cfa37a7b 2004-04-10 devnull It also computes
465 cfa37a7b 2004-04-10 devnull such that
466 cfa37a7b 2004-04-10 devnull .BR "a*x + b*y = d" .
471 cfa37a7b 2004-04-10 devnull are required to be positive.
472 cfa37a7b 2004-04-10 devnull If called with negative arguments, it will
473 cfa37a7b 2004-04-10 devnull return a gcd of 0.
475 cfa37a7b 2004-04-10 devnull .I Mpinverse
476 cfa37a7b 2004-04-10 devnull computes the multiplicative inverse of
481 cfa37a7b 2004-04-10 devnull .I Mpsignif
482 cfa37a7b 2004-04-10 devnull returns the bit offset of the left most 1 bit in
484 cfa37a7b 2004-04-10 devnull .I Mplowbits0
485 cfa37a7b 2004-04-10 devnull returns the bit offset of the right most 1 bit.
486 cfa37a7b 2004-04-10 devnull For example, for 0x14,
487 cfa37a7b 2004-04-10 devnull .I mpsignif
488 cfa37a7b 2004-04-10 devnull would return 4 and
489 cfa37a7b 2004-04-10 devnull .I mplowbits0
490 cfa37a7b 2004-04-10 devnull would return 2.
492 cfa37a7b 2004-04-10 devnull The remaining routines all work on arrays of
493 cfa37a7b 2004-04-10 devnull .B mpdigit
494 cfa37a7b 2004-04-10 devnull rather than
495 cfa37a7b 2004-04-10 devnull .BR mpint 's.
496 cfa37a7b 2004-04-10 devnull They are the basis of all the other routines. They are separated out
497 cfa37a7b 2004-04-10 devnull to allow them to be rewritten in assembler for each architecture. There
498 cfa37a7b 2004-04-10 devnull is also a portable C version for each one.
499 cfa37a7b 2004-04-10 devnull .TF mpvecdigmuladd
501 cfa37a7b 2004-04-10 devnull .I mpdigdiv
502 cfa37a7b 2004-04-10 devnull .BR "quotient = dividend[0:1] / divisor" .
504 cfa37a7b 2004-04-10 devnull .I mpvecadd
505 cfa37a7b 2004-04-10 devnull .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
506 cfa37a7b 2004-04-10 devnull We assume alen >= blen and that sum has room for alen+1 digits.
508 cfa37a7b 2004-04-10 devnull .I mpvecsub
509 cfa37a7b 2004-04-10 devnull .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
510 cfa37a7b 2004-04-10 devnull We assume that alen >= blen and that diff has room for alen digits.
512 cfa37a7b 2004-04-10 devnull .I mpvecdigmuladd
513 cfa37a7b 2004-04-10 devnull .BR "p[0:n] += m * b[0:n-1]" .
514 cfa37a7b 2004-04-10 devnull This multiplies a an array of digits times a scalar and adds it to another array.
515 cfa37a7b 2004-04-10 devnull We assume p has room for n+1 digits.
517 cfa37a7b 2004-04-10 devnull .I mpvecdigmulsub
518 cfa37a7b 2004-04-10 devnull .BR "p[0:n] -= m * b[0:n-1]" .
519 cfa37a7b 2004-04-10 devnull This multiplies a an array of digits times a scalar and subtracts it fromo another array.
520 cfa37a7b 2004-04-10 devnull We assume p has room for n+1 digits. It returns +1 is the result is positive and
521 cfa37a7b 2004-04-10 devnull -1 if negative.
523 cfa37a7b 2004-04-10 devnull .I mpvecmul
524 cfa37a7b 2004-04-10 devnull .BR "p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]" .
525 cfa37a7b 2004-04-10 devnull We assume that p has room for alen*blen+1 digits.
527 cfa37a7b 2004-04-10 devnull .I mpveccmp
528 cfa37a7b 2004-04-10 devnull This returns -1, 0, or +1 as a - b is negative, 0, or positive.
531 cfa37a7b 2004-04-10 devnull .IR mptwo ,
532 cfa37a7b 2004-04-10 devnull .I mpone
534 cfa37a7b 2004-04-10 devnull .I mpzero
535 cfa37a7b 2004-04-10 devnull are the constants 2, 1 and 0. These cannot be freed.
536 cfa37a7b 2004-04-10 devnull .SS "Chinese remainder theorem
538 cfa37a7b 2004-04-10 devnull When computing in a non-prime modulus,
540 cfa37a7b 2004-04-10 devnull it is possible to perform the computations on the residues modulo the prime
541 cfa37a7b 2004-04-10 devnull factors of
543 cfa37a7b 2004-04-10 devnull instead. Since these numbers are smaller, multiplication and exponentiation
544 cfa37a7b 2004-04-10 devnull can be much faster.
546 cfa37a7b 2004-04-10 devnull .I Crtin
547 cfa37a7b 2004-04-10 devnull computes the residues of
549 cfa37a7b 2004-04-10 devnull and returns them in a newly allocated structure:
551 cfa37a7b 2004-04-10 devnull typedef struct CRTres CRTres;
553 cfa37a7b 2004-04-10 devnull int n; // number of residues
554 cfa37a7b 2004-04-10 devnull mpint *r[n]; // residues
558 cfa37a7b 2004-04-10 devnull .I Crtout
559 cfa37a7b 2004-04-10 devnull takes a residue representation of a number and converts it back into
560 cfa37a7b 2004-04-10 devnull the number. It also frees the residue structure.
562 cfa37a7b 2004-04-10 devnull .I Crepre
563 cfa37a7b 2004-04-10 devnull saves a copy of the factors and precomputes the constants necessary
564 cfa37a7b 2004-04-10 devnull for converting the residue form back into a number modulo
565 cfa37a7b 2004-04-10 devnull the product of the factors. It returns a newly allocated structure
566 cfa37a7b 2004-04-10 devnull containing values.
568 cfa37a7b 2004-04-10 devnull .I Crtprefree
570 cfa37a7b 2004-04-10 devnull .I crtresfree
572 cfa37a7b 2004-04-10 devnull .I CRTpre
574 cfa37a7b 2004-04-10 devnull .I CRTres
575 cfa37a7b 2004-04-10 devnull structures respectively.
576 cfa37a7b 2004-04-10 devnull .SH SOURCE
577 cfa37a7b 2004-04-10 devnull .B /sys/src/libmp
