| 2 |
- |
1 |
#pragma src "/sys/src/libmp"
|
|
|
2 |
#pragma lib "libmp.a"
|
|
|
3 |
|
|
|
4 |
#define _MPINT 1
|
|
|
5 |
|
|
|
6 |
/*
|
|
|
7 |
* the code assumes mpdigit to be at least an int
|
|
|
8 |
* mpdigit must be an atomic type. mpdigit is defined
|
|
|
9 |
* in the architecture specific u.h
|
|
|
10 |
*/
|
|
|
11 |
|
|
|
12 |
typedef struct mpint mpint;
|
|
|
13 |
|
|
|
14 |
struct mpint
|
|
|
15 |
{
|
|
|
16 |
int sign; /* +1 or -1 */
|
|
|
17 |
int size; /* allocated digits */
|
|
|
18 |
int top; /* significant digits */
|
|
|
19 |
mpdigit *p;
|
|
|
20 |
char flags;
|
|
|
21 |
};
|
|
|
22 |
|
|
|
23 |
enum
|
|
|
24 |
{
|
|
|
25 |
MPstatic= 0x01,
|
|
|
26 |
Dbytes= sizeof(mpdigit), /* bytes per digit */
|
|
|
27 |
Dbits= Dbytes*8 /* bits per digit */
|
|
|
28 |
};
|
|
|
29 |
|
|
|
30 |
/* allocation */
|
|
|
31 |
void mpsetminbits(int n); /* newly created mpint's get at least n bits */
|
|
|
32 |
mpint* mpnew(int n); /* create a new mpint with at least n bits */
|
|
|
33 |
void mpfree(mpint *b);
|
|
|
34 |
void mpbits(mpint *b, int n); /* ensure that b has at least n bits */
|
|
|
35 |
void mpnorm(mpint *b); /* dump leading zeros */
|
|
|
36 |
mpint* mpcopy(mpint *b);
|
|
|
37 |
void mpassign(mpint *old, mpint *new);
|
|
|
38 |
|
|
|
39 |
/* random bits */
|
|
|
40 |
mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b);
|
|
|
41 |
|
|
|
42 |
/* conversion */
|
|
|
43 |
mpint* strtomp(char*, char**, int, mpint*); /* ascii */
|
|
|
44 |
int mpfmt(Fmt*);
|
|
|
45 |
char* mptoa(mpint*, int, char*, int);
|
|
|
46 |
mpint* letomp(uchar*, uint, mpint*); /* byte array, little-endian */
|
|
|
47 |
int mptole(mpint*, uchar*, uint, uchar**);
|
|
|
48 |
mpint* betomp(uchar*, uint, mpint*); /* byte array, little-endian */
|
|
|
49 |
int mptobe(mpint*, uchar*, uint, uchar**);
|
|
|
50 |
uint mptoui(mpint*); /* unsigned int */
|
|
|
51 |
mpint* uitomp(uint, mpint*);
|
|
|
52 |
int mptoi(mpint*); /* int */
|
|
|
53 |
mpint* itomp(int, mpint*);
|
|
|
54 |
uvlong mptouv(mpint*); /* unsigned vlong */
|
|
|
55 |
mpint* uvtomp(uvlong, mpint*);
|
|
|
56 |
vlong mptov(mpint*); /* vlong */
|
|
|
57 |
mpint* vtomp(vlong, mpint*);
|
|
|
58 |
|
|
|
59 |
/* divide 2 digits by one */
|
|
|
60 |
void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
|
|
|
61 |
|
|
|
62 |
/* in the following, the result mpint may be */
|
|
|
63 |
/* the same as one of the inputs. */
|
|
|
64 |
void mpadd(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
|
|
|
65 |
void mpsub(mpint *b1, mpint *b2, mpint *diff); /* diff = b1-b2 */
|
|
|
66 |
void mpleft(mpint *b, int shift, mpint *res); /* res = b<<shift */
|
|
|
67 |
void mpright(mpint *b, int shift, mpint *res); /* res = b>>shift */
|
|
|
68 |
void mpmul(mpint *b1, mpint *b2, mpint *prod); /* prod = b1*b2 */
|
|
|
69 |
void mpexp(mpint *b, mpint *e, mpint *m, mpint *res); /* res = b**e mod m */
|
|
|
70 |
void mpmod(mpint *b, mpint *m, mpint *remainder); /* remainder = b mod m */
|
|
|
71 |
|
|
|
72 |
/* quotient = dividend/divisor, remainder = dividend % divisor */
|
|
|
73 |
void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder);
|
|
|
74 |
|
|
|
75 |
/* return neg, 0, pos as b1-b2 is neg, 0, pos */
|
|
|
76 |
int mpcmp(mpint *b1, mpint *b2);
|
|
|
77 |
|
|
|
78 |
/* extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d */
|
|
|
79 |
void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);
|
|
|
80 |
|
|
|
81 |
/* res = b**-1 mod m */
|
|
|
82 |
void mpinvert(mpint *b, mpint *m, mpint *res);
|
|
|
83 |
|
|
|
84 |
/* bit counting */
|
|
|
85 |
int mpsignif(mpint*); /* number of sigificant bits in mantissa */
|
|
|
86 |
int mplowbits0(mpint*); /* k, where n = 2**k * q for odd q */
|
|
|
87 |
|
|
|
88 |
/* well known constants */
|
|
|
89 |
extern mpint *mpzero, *mpone, *mptwo;
|
|
|
90 |
|
|
|
91 |
/* sum[0:alen] = a[0:alen-1] + b[0:blen-1] */
|
|
|
92 |
/* prereq: alen >= blen, sum has room for alen+1 digits */
|
|
|
93 |
void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum);
|
|
|
94 |
|
|
|
95 |
/* diff[0:alen-1] = a[0:alen-1] - b[0:blen-1] */
|
|
|
96 |
/* prereq: alen >= blen, diff has room for alen digits */
|
|
|
97 |
void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff);
|
|
|
98 |
|
|
|
99 |
/* p[0:n] += m * b[0:n-1] */
|
|
|
100 |
/* prereq: p has room for n+1 digits */
|
|
|
101 |
void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p);
|
|
|
102 |
|
|
|
103 |
/* p[0:n] -= m * b[0:n-1] */
|
|
|
104 |
/* prereq: p has room for n+1 digits */
|
|
|
105 |
int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);
|
|
|
106 |
|
|
|
107 |
/* p[0:alen*blen-1] = a[0:alen-1] * b[0:blen-1] */
|
|
|
108 |
/* prereq: alen >= blen, p has room for m*n digits */
|
|
|
109 |
void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
|
|
|
110 |
|
|
|
111 |
/* sign of a - b or zero if the same */
|
|
|
112 |
int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);
|
|
|
113 |
|
|
|
114 |
/* divide the 2 digit dividend by the one digit divisor and stick in quotient */
|
|
|
115 |
/* we assume that the result is one digit - overflow is all 1's */
|
|
|
116 |
void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
|
|
|
117 |
|
|
|
118 |
/* playing with magnitudes */
|
|
|
119 |
int mpmagcmp(mpint *b1, mpint *b2);
|
|
|
120 |
void mpmagadd(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
|
|
|
121 |
void mpmagsub(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
|
|
|
122 |
|
|
|
123 |
/* chinese remainder theorem */
|
|
|
124 |
typedef struct CRTpre CRTpre; /* precomputed values for converting */
|
|
|
125 |
/* twixt residues and mpint */
|
|
|
126 |
typedef struct CRTres CRTres; /* residue form of an mpint */
|
|
|
127 |
|
|
|
128 |
#pragma incomplete CRTpre
|
|
|
129 |
|
|
|
130 |
struct CRTres
|
|
|
131 |
{
|
|
|
132 |
int n; /* number of residues */
|
|
|
133 |
mpint *r[1]; /* residues */
|
|
|
134 |
};
|
|
|
135 |
|
|
|
136 |
CRTpre* crtpre(int, mpint**); /* precompute conversion values */
|
|
|
137 |
CRTres* crtin(CRTpre*, mpint*); /* convert mpint to residues */
|
|
|
138 |
void crtout(CRTpre*, CRTres*, mpint*); /* convert residues to mpint */
|
|
|
139 |
void crtprefree(CRTpre*);
|
|
|
140 |
void crtresfree(CRTres*);
|
|
|
141 |
|
|
|
142 |
|
|
|
143 |
#pragma varargck type "B" mpint*
|