1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
|
<head>
<title>mp(3) - Plan 9 from User Space</title>
<meta content="text/html; charset=utf-8" http-equiv=Content-Type>
</head>
<body bgcolor=#ffffff>
<table border=0 cellpadding=0 cellspacing=0 width=100%>
<tr height=10><td>
<tr><td width=20><td>
<tr><td width=20><td><b>MP(3)</b><td align=right><b>MP(3)</b>
<tr><td width=20><td colspan=2>
<br>
<p><font size=+1><b>NAME </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
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<br>
</table>
<p><font size=+1><b>SYNOPSIS </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
<tt><font size=+1>#include <u.h><br>
#include <libc.h><br>
#include <mp.h>
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* mpnew(int n)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpfree(mpint *b)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpsetminbits(int n)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpbits(mpint *b, int n)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpnorm(mpint *b)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* mpcopy(mpint *b)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpassign(mpint *old, mpint *new)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>char* mptoa(mpint *b, int base, char *buf, int blen)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mpfmt(Fmt*)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* betomp(uchar *buf, uint blen, mpint *b)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* letomp(uchar *buf, uint blen, mpint *b)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>uint mptoui(mpint*)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* uitomp(uint, mpint*)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mptoi(mpint*)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* itomp(int, mpint*)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* vtomp(vlong, mpint*)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>vlong mptov(mpint*)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* uvtomp(uvlong, mpint*)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>uvlong mptouv(mpint*)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpadd(mpint *b1, mpint *b2, mpint *sum)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpmagadd(mpint *b1, mpint *b2, mpint *sum)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpsub(mpint *b1, mpint *b2, mpint *diff)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpmagsub(mpint *b1, mpint *b2, mpint *diff)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpleft(mpint *b, int shift, mpint *res)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpright(mpint *b, int shift, mpint *res)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpmul(mpint *b1, mpint *b2, mpint *prod)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpmod(mpint *b, mpint *m, mpint *remainder)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint
*remainder)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint* mpfactorial(ulong n)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mpcmp(mpint *b1, mpint *b2)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mpmagcmp(mpint *b1, mpint *b2)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint
*y)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpinvert(mpint *b, mpint *m, mpint *res)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mpsignif(mpint *b)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mplowbits0(mpint *b)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit
*sum)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit
*diff)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit
*p)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>CRTpre* crtpre(int nfactors, mpint **factors)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>CRTres* crtin(CRTpre *crt, mpint *x)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void crtout(CRTpre *crt, CRTres *r, mpint *x)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void crtprefree(CRTpre *cre)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>void crtresfree(CRTres *res)
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
<tt><font size=+1>mpint *mpzero, *mpone, *mptwo<br>
</font></tt>
</table>
<p><font size=+1><b>DESCRIPTION </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
These routines perform extended precision integer arithmetic.
The basic type is <tt><font size=+1>mpint</font></tt>, which points to an array of <tt><font size=+1>mpdigit</font></tt>s,
stored in little-endian order:<br>
<tt><font size=+1>typedef struct mpint mpint;<br>
struct mpint<br>
{<br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
int sign; /* +1 or −1 */<br>
int size; /* allocated digits */<br>
int top; /* significant digits */<br>
mpdigit *p;<br>
char flags;<br>
</table>
};<br>
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
The sign of 0 is +1.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
The size of <tt><font size=+1>mpdigit</font></tt> is architecture-dependent and defined in <tt><font size=+1>/$cputype/include/u.h</font></tt>.
<tt><font size=+1>Mpint</font></tt>s are dynamically allocated and must be explicitly freed.
Operations grow the array of digits as needed.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
In general, the result parameters are last in the argument list.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
Routines that return an <tt><font size=+1>mpint</font></tt> will allocate the <tt><font size=+1>mpint</font></tt> if the result
parameter is <tt><font size=+1>nil</font></tt>. This includes <i>strtomp</i>, <i>itomp</i>, <i>uitomp</i>, and <i>btomp</i>.
These functions, in addition to <i>mpnew</i> and <i>mpcopy</i>, will return
<tt><font size=+1>nil</font></tt> if the allocation fails.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
Input and result parameters may point to the same <tt><font size=+1>mpint</font></tt>. The routines
check and copy where necessary.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Mpnew</i> creates an <tt><font size=+1>mpint</font></tt> with an initial allocation of <i>n</i> bits. If
<i>n</i> is zero, the allocation will be whatever was specified in the
last call to <i>mpsetminbits</i> or to the initial value, 1056. <i>Mpfree</i>
frees an <tt><font size=+1>mpint</font></tt>. <i>Mpbits</i> grows the allocation of <i>b</i> to fit at least
<i>n</i> bits. If <tt><font size=+1>b−>top</font></tt> doesn’t cover <i>n</i> bits it increases it to do so.
Unless
you are writing new basic operations, you can restrict yourself
to <tt><font size=+1>mpnew(0)</font></tt> and <tt><font size=+1>mpfree(b)</font></tt>.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Mpnorm</i> normalizes the representation by trimming any high order
zero digits. All routines except <tt><font size=+1>mpbits</font></tt> return normalized results.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Mpcopy</i> creates a new <tt><font size=+1>mpint</font></tt> with the same value as <i>b</i> while <i>mpassign</i>
sets the value of <i>new</i> to be that of <i>old</i>.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Mprand</i> creates an <i>n</i> bit random number using the generator <i>gen</i>.
<i>Gen</i> takes a pointer to a string of uchar’s and the number to fill
in.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Strtomp</i> and <i>mptoa</i> convert between ASCII and <tt><font size=+1>mpint</font></tt> representations
using the base indicated. Only the bases 10, 16, 32, and 64 are
supported. Anything else defaults to 16. <i>Strtomp</i> skips any leading
spaces or tabs. <i>Strtomp</i>’s scan stops when encountering a digit
not valid in the base. If <i>rptr</i> is not zero, <i>*rptr</i> is
set to point to the character immediately after the string converted.
If the parse pterminates before any digits are found, <i>strtomp</i>
return <tt><font size=+1>nil</font></tt>. <i>Mptoa</i> returns a pointer to the filled buffer. If the
parameter <i>buf</i> is <tt><font size=+1>nil</font></tt>, the buffer is allocated. <i>Mpfmt</i> can be used
with <a href="../man3/fmtinstall.html"><i>fmtinstall</i>(3)</a> and <a href="../man3/print.html"><i>print</i>(3)</a> to print hexadecimal
representations of <tt><font size=+1>mpint</font></tt>s.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Mptobe</i> and <i>mptole</i> convert an <i>mpint</i> to a byte array. The former
creates a big endian representation, the latter a little endian
one. If the destination <i>buf</i> is not <tt><font size=+1>nil</font></tt>, it specifies the buffer
of length <i>blen</i> for the result. If the representation is less than
<i>blen</i> bytes, the rest of the buffer is zero filled. If <i>buf</i> is <tt><font size=+1>nil</font></tt>,
then a
buffer is allocated and a pointer to it is deposited in the location
pointed to by <i>bufp</i>. Sign is ignored in these conversions, i.e.,
the byte array version is always positive.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Betomp</i>, and <i>letomp</i> convert from a big or little endian byte array
at <i>buf</i> of length <i>blen</i> to an <i>mpint</i>. If <i>b</i> is not <i>nil</i>, it refers
to a preallocated <i>mpint</i> for the result. If <i>b</i> is <tt><font size=+1>nil</font></tt>, a new integer
is allocated and returned as the result.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
The integer conversions are:<br>
<i>mptoui</i><tt><font size=+1> mpint</font></tt>-><tt><font size=+1>unsigned int<br>
</font></tt><i>uitomp</i><tt><font size=+1> unsigned int</font></tt>-><tt><font size=+1>mpint<br>
</font></tt><i>mptoi</i><tt><font size=+1> mpint</font></tt>-><tt><font size=+1>int<br>
</font></tt><i>itomp</i><tt><font size=+1> int</font></tt>-><tt><font size=+1>mpint<br>
</font></tt><i>mptouv</i><tt><font size=+1> mpint</font></tt>-><tt><font size=+1>unsigned vlong<br>
</font></tt><i>uvtomp</i><tt><font size=+1> unsigned vlong</font></tt>-><tt><font size=+1>mpint<br>
</font></tt><i>mptov</i><tt><font size=+1> mpint</font></tt>-><tt><font size=+1>vlong<br>
</font></tt><i>vtomp</i><tt><font size=+1> vlong</font></tt>-><tt><font size=+1>mpint
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
When converting to the base integer types, if the integer is too
large, the largest integer of the appropriate sign and size is
returned.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
The mathematical functions are:<br>
<i>mpadd</i><tt><font size=+1> sum = b1 + b2</font></tt>.<br>
<i>mpmagadd</i><tt><font size=+1> sum = abs(b1) + abs(b2)</font></tt>.<br>
<i>mpsub</i><tt><font size=+1> diff = b1 − b2</font></tt>.<br>
<i>mpmagsub</i><tt><font size=+1> diff = abs(b1) − abs(b2)</font></tt>.<br>
<i>mpleft</i><tt><font size=+1> res = b<<shift</font></tt>.<br>
<i>mpright</i><tt><font size=+1> res = b>>shift</font></tt>.<br>
<i>mpmul</i><tt><font size=+1> prod = b1*b2</font></tt>.<br>
<i>mpexp</i> if <i>m</i> is nil, <tt><font size=+1>res = b**e</font></tt>. Otherwise, <tt><font size=+1>res = b**e mod m</font></tt>.<br>
<i>mpmod</i><tt><font size=+1> remainder = b % m</font></tt>.<br>
<i>mpdiv</i><tt><font size=+1> quotient = dividend/divisor</font></tt>. <tt><font size=+1>remainder = dividend % divisor</font></tt>.<br>
<i>mpfactorial</i> returns factorial of <i>n</i>.<br>
<i>mpcmp</i> returns -1, 0, or +1 as <i>b1</i> is less than, equal to, or greater
than <i>b2</i>.<br>
<i>mpmagcmp</i> the same as <i>mpcmp</i> but ignores the sign and just compares
magnitudes.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Mpextendedgcd</i> computes the greatest common denominator, <i>d</i>, of
<i>a</i> and <i>b</i>. It also computes <i>x</i> and <i>y</i> such that <tt><font size=+1>a*x + b*y = d</font></tt>. Both
<i>a</i> and <i>b</i> are required to be positive. If called with negative arguments,
it will return a gcd of 0.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Mpinverse</i> computes the multiplicative inverse of <i>b</i> <tt><font size=+1>mod</font></tt> <i>m</i>.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Mpsignif</i> returns the bit offset of the left most 1 bit in <i>b</i>. <i>Mplowbits0</i>
returns the bit offset of the right most 1 bit. For example, for
0x14, <i>mpsignif</i> would return 4 and <i>mplowbits0</i> would return 2.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
The remaining routines all work on arrays of <tt><font size=+1>mpdigit</font></tt> rather than
<tt><font size=+1>mpint</font></tt>’s. They are the basis of all the other routines. They are
separated out to allow them to be rewritten in assembler for each
architecture. There is also a portable C version for each one.<br>
<i>mpdigdiv</i><tt><font size=+1> quotient = dividend[0:1] / divisor</font></tt>.<br>
<i>mpvecadd</i><tt><font size=+1> sum[0:alen] = a[0:alen−1] + b[0:blen−1]</font></tt>. We assume alen
>= blen and that sum has room for alen+1 digits.<br>
<i>mpvecsub</i><tt><font size=+1> diff[0:alen−1] = a[0:alen−1] − b[0:blen−1]</font></tt>. We assume
that alen >= blen and that diff has room for alen digits.<br>
<i>mpvecdigmuladd</i><tt><font size=+1> p[0:n] += m * b[0:n−1]</font></tt>. 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.<br>
<i>mpvecdigmulsub</i><tt><font size=+1> p[0:n] −= m * b[0:n−1]</font></tt>. 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 positive and -1 if negative.<br>
<i>mpvecmul</i><tt><font size=+1> p[0:alen*blen] = a[0:alen−1] * b[0:blen−1]</font></tt>. We assume
that p has room for alen*blen+1 digits.<br>
<i>mpveccmp</i> This returns -1, 0, or +1 as a - b is negative, 0, or
positive.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>mptwo</i>, <i>mpone</i> and <i>mpzero</i> are the constants 2, 1 and 0. These cannot
be freed.<br>
<p><font size=+1><b>Chinese remainder theorem </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
When computing in a non-prime modulus, <i>n,</i> it is possible to perform
the computations on the residues modulo the prime factors of <i>n</i>
instead. Since these numbers are smaller, multiplication and exponentiation
can be much faster.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Crtin</i> computes the residues of <i>x</i> and returns them in a newly allocated
structure:<br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
<tt><font size=+1>typedef struct CRTres CRTres; <br>
{<br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
int n; // number of residues<br>
mpint *r[n]; // residues<br>
</table>
};<br>
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
</font></tt>
</table>
<i>Crtout</i> takes a residue representation of a number and converts
it back into the number. It also frees the residue structure.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Crepre</i> saves a copy of the factors and precomputes the constants
necessary for converting the residue form back into a number modulo
the product of the factors. It returns a newly allocated structure
containing values.
<table border=0 cellpadding=0 cellspacing=0><tr height=5><td></table>
<i>Crtprefree</i> and <i>crtresfree</i> free <i>CRTpre</i> and <i>CRTres</i> structures respectively.<br>
</table>
<p><font size=+1><b>SOURCE </b></font><br>
<table border=0 cellpadding=0 cellspacing=0><tr height=2><td><tr><td width=20><td>
<tt><font size=+1>/usr/local/plan9/src/libmp<br>
</font></tt>
</table>
<td width=20>
<tr height=20><td>
</table>
<!-- TRAILER -->
<table border=0 cellpadding=0 cellspacing=0 width=100%>
<tr height=15><td width=10><td><td width=10>
<tr><td><td>
<center>
<a href="../../"><img src="../../dist/spaceglenda100.png" alt="Space Glenda" border=1></a>
</center>
</table>
<!-- TRAILER -->
</body></html>
|