| Line 6... |
Line 6... |
| 6 |
#define __LIBMP_H_
|
6 |
#define __LIBMP_H_
|
| 7 |
|
7 |
|
| 8 |
#pragma src "/sys/src/ape/lib/mp"
|
8 |
#pragma src "/sys/src/ape/lib/mp"
|
| 9 |
#pragma lib "/$M/lib/ape/libmp.a"
|
9 |
#pragma lib "/$M/lib/ape/libmp.a"
|
| 10 |
|
10 |
|
| - |
|
11 |
#include <u.h>
|
| - |
|
12 |
#include <fmt.h>
|
| - |
|
13 |
|
| 11 |
typedef unsigned int mpdigit; /* from /$objtype/include/u.h */
|
14 |
typedef unsigned int mpdigit; /* from /$objtype/include/u.h */
|
| 12 |
|
15 |
|
| 13 |
#define _MPINT 1
|
16 |
#define _MPINT 1
|
| 14 |
|
17 |
|
| 15 |
/*
|
18 |
/*
|
| 16 |
* the code assumes mpdigit to be at least an int
|
19 |
* the code assumes mpdigit to be at least an int
|
| 17 |
* mpdigit must be an atomic type. mpdigit is defined
|
20 |
* mpdigit must be an atomic type. mpdigit is defined
|
| 18 |
* in the architecture specific u.h
|
21 |
* in the architecture specific u.h
|
| 19 |
*/
|
22 |
*/
|
| 20 |
|
- |
|
| 21 |
typedef struct mpint mpint;
|
23 |
typedef struct mpint mpint;
|
| 22 |
|
24 |
|
| 23 |
struct mpint
|
25 |
struct mpint
|
| 24 |
{
|
26 |
{
|
| 25 |
int sign; /* +1 or -1 */
|
27 |
int sign; /* +1 or -1 */
|
| Line 29... |
Line 31... |
| 29 |
char flags;
|
31 |
char flags;
|
| 30 |
};
|
32 |
};
|
| 31 |
|
33 |
|
| 32 |
enum
|
34 |
enum
|
| 33 |
{
|
35 |
{
|
| 34 |
MPstatic= 0x01,
|
36 |
MPstatic= 0x01, /* static constant */
|
| - |
|
37 |
MPnorm= 0x02, /* normalization status */
|
| - |
|
38 |
MPtimesafe= 0x04, /* request time invariant computation */
|
| - |
|
39 |
MPfield= 0x08, /* this mpint is a field modulus */
|
| - |
|
40 |
|
| 35 |
Dbytes= sizeof(mpdigit), /* bytes per digit */
|
41 |
Dbytes= sizeof(mpdigit), /* bytes per digit */
|
| 36 |
Dbits= Dbytes*8 /* bits per digit */
|
42 |
Dbits= Dbytes*8 /* bits per digit */
|
| 37 |
};
|
43 |
};
|
| 38 |
|
44 |
|
| 39 |
/* allocation */
|
45 |
/* allocation */
|
| 40 |
void mpsetminbits(int n); /* newly created mpint's get at least n bits */
|
46 |
void mpsetminbits(int n); /* newly created mpint's get at least n bits */
|
| 41 |
mpint* mpnew(int n); /* create a new mpint with at least n bits */
|
47 |
mpint* mpnew(int n); /* create a new mpint with at least n bits */
|
| 42 |
void mpfree(mpint *b);
|
48 |
void mpfree(mpint *b);
|
| 43 |
void mpbits(mpint *b, int n); /* ensure that b has at least n bits */
|
49 |
void mpbits(mpint *b, int n); /* ensure that b has at least n bits */
|
| 44 |
void mpnorm(mpint *b); /* dump leading zeros */
|
50 |
mpint* mpnorm(mpint *b); /* dump leading zeros */
|
| 45 |
mpint* mpcopy(mpint *b);
|
51 |
mpint* mpcopy(mpint *b);
|
| 46 |
void mpassign(mpint *old, mpint *new);
|
52 |
void mpassign(mpint *old, mpint *new);
|
| 47 |
|
53 |
|
| 48 |
/* random bits */
|
54 |
/* random bits */
|
| 49 |
mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b);
|
55 |
mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b);
|
| - |
|
56 |
/* return uniform random [0..n-1] */
|
| - |
|
57 |
mpint* mpnrand(mpint *n, void (*gen)(uchar*, int), mpint *b);
|
| 50 |
|
58 |
|
| 51 |
/* conversion */
|
59 |
/* conversion */
|
| 52 |
mpint* strtomp(char*, char**, int, mpint*); /* ascii */
|
60 |
mpint* strtomp(char*, char**, int, mpint*); /* ascii */
|
| 53 |
int mpfmt(Fmt*);
|
61 |
int mpfmt(Fmt*);
|
| 54 |
char* mptoa(mpint*, int, char*, int);
|
62 |
char* mptoa(mpint*, int, char*, int);
|
| 55 |
mpint* letomp(uchar*, uint, mpint*); /* byte array, little-endian */
|
63 |
mpint* letomp(uchar*, uint, mpint*); /* byte array, little-endian */
|
| 56 |
int mptole(mpint*, uchar*, uint, uchar**);
|
64 |
int mptole(mpint*, uchar*, uint, uchar**);
|
| - |
|
65 |
void mptolel(mpint *b, uchar *p, int n);
|
| 57 |
mpint* betomp(uchar*, uint, mpint*); /* byte array, little-endian */
|
66 |
mpint* betomp(uchar*, uint, mpint*); /* byte array, big-endian */
|
| 58 |
int mptobe(mpint*, uchar*, uint, uchar**);
|
67 |
int mptobe(mpint*, uchar*, uint, uchar**);
|
| - |
|
68 |
void mptober(mpint *b, uchar *p, int n);
|
| 59 |
uint mptoui(mpint*); /* unsigned int */
|
69 |
uint mptoui(mpint*); /* unsigned int */
|
| 60 |
mpint* uitomp(uint, mpint*);
|
70 |
mpint* uitomp(uint, mpint*);
|
| 61 |
int mptoi(mpint*); /* int */
|
71 |
int mptoi(mpint*); /* int */
|
| 62 |
mpint* itomp(int, mpint*);
|
72 |
mpint* itomp(int, mpint*);
|
| 63 |
uvlong mptouv(mpint*); /* unsigned vlong */
|
73 |
uvlong mptouv(mpint*); /* unsigned vlong */
|
| 64 |
mpint* uvtomp(uvlong, mpint*);
|
74 |
mpint* uvtomp(uvlong, mpint*);
|
| 65 |
vlong mptov(mpint*); /* vlong */
|
75 |
vlong mptov(mpint*); /* vlong */
|
| 66 |
mpint* vtomp(vlong, mpint*);
|
76 |
mpint* vtomp(vlong, mpint*);
|
| - |
|
77 |
double mptod(mpint*); /* double */
|
| - |
|
78 |
mpint* dtomp(double, mpint*);
|
| 67 |
|
79 |
|
| 68 |
/* divide 2 digits by one */
|
80 |
/* divide 2 digits by one */
|
| 69 |
void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
|
81 |
void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
|
| 70 |
|
82 |
|
| 71 |
/* in the following, the result mpint may be */
|
83 |
/* in the following, the result mpint may be */
|
| Line 75... |
Line 87... |
| 75 |
void mpleft(mpint *b, int shift, mpint *res); /* res = b<<shift */
|
87 |
void mpleft(mpint *b, int shift, mpint *res); /* res = b<<shift */
|
| 76 |
void mpright(mpint *b, int shift, mpint *res); /* res = b>>shift */
|
88 |
void mpright(mpint *b, int shift, mpint *res); /* res = b>>shift */
|
| 77 |
void mpmul(mpint *b1, mpint *b2, mpint *prod); /* prod = b1*b2 */
|
89 |
void mpmul(mpint *b1, mpint *b2, mpint *prod); /* prod = b1*b2 */
|
| 78 |
void mpexp(mpint *b, mpint *e, mpint *m, mpint *res); /* res = b**e mod m */
|
90 |
void mpexp(mpint *b, mpint *e, mpint *m, mpint *res); /* res = b**e mod m */
|
| 79 |
void mpmod(mpint *b, mpint *m, mpint *remainder); /* remainder = b mod m */
|
91 |
void mpmod(mpint *b, mpint *m, mpint *remainder); /* remainder = b mod m */
|
| - |
|
92 |
|
| - |
|
93 |
/* logical operations */
|
| - |
|
94 |
void mpand(mpint *b1, mpint *b2, mpint *res);
|
| - |
|
95 |
void mpbic(mpint *b1, mpint *b2, mpint *res);
|
| - |
|
96 |
void mpor(mpint *b1, mpint *b2, mpint *res);
|
| - |
|
97 |
void mpnot(mpint *b, mpint *res);
|
| - |
|
98 |
void mpxor(mpint *b1, mpint *b2, mpint *res);
|
| - |
|
99 |
void mptrunc(mpint *b, int n, mpint *res);
|
| - |
|
100 |
void mpxtend(mpint *b, int n, mpint *res);
|
| - |
|
101 |
|
| - |
|
102 |
/* modular arithmetic, time invariant when 0≤b1≤m-1 and 0≤b2≤m-1 */
|
| - |
|
103 |
void mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum); /* sum = b1+b2 % m */
|
| - |
|
104 |
void mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff); /* diff = b1-b2 % m */
|
| - |
|
105 |
void mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod); /* prod = b1*b2 % m */
|
| 80 |
|
106 |
|
| 81 |
/* quotient = dividend/divisor, remainder = dividend % divisor */
|
107 |
/* quotient = dividend/divisor, remainder = dividend % divisor */
|
| 82 |
void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder);
|
108 |
void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder);
|
| 83 |
|
109 |
|
| 84 |
/* return neg, 0, pos as b1-b2 is neg, 0, pos */
|
110 |
/* return neg, 0, pos as b1-b2 is neg, 0, pos */
|
| 85 |
int mpcmp(mpint *b1, mpint *b2);
|
111 |
int mpcmp(mpint *b1, mpint *b2);
|
| - |
|
112 |
|
| - |
|
113 |
/* res = s != 0 ? b1 : b2 */
|
| - |
|
114 |
void mpsel(int s, mpint *b1, mpint *b2, mpint *res);
|
| 86 |
|
115 |
|
| 87 |
/* extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d */
|
116 |
/* extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d */
|
| 88 |
void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);
|
117 |
void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);
|
| 89 |
|
118 |
|
| 90 |
/* res = b**-1 mod m */
|
119 |
/* res = b**-1 mod m */
|
| Line 111... |
Line 140... |
| 111 |
|
140 |
|
| 112 |
/* p[0:n] -= m * b[0:n-1] */
|
141 |
/* p[0:n] -= m * b[0:n-1] */
|
| 113 |
/* prereq: p has room for n+1 digits */
|
142 |
/* prereq: p has room for n+1 digits */
|
| 114 |
int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);
|
143 |
int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);
|
| 115 |
|
144 |
|
| 116 |
/* p[0:alen*blen-1] = a[0:alen-1] * b[0:blen-1] */
|
145 |
/* p[0:alen+blen-1] = a[0:alen-1] * b[0:blen-1] */
|
| 117 |
/* prereq: alen >= blen, p has room for m*n digits */
|
146 |
/* prereq: alen >= blen, p has room for m*n digits */
|
| 118 |
void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
|
147 |
void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
|
| - |
|
148 |
void mpvectsmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
|
| 119 |
|
149 |
|
| 120 |
/* sign of a - b or zero if the same */
|
150 |
/* sign of a - b or zero if the same */
|
| 121 |
int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);
|
151 |
int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);
|
| - |
|
152 |
int mpvectscmp(mpdigit *a, int alen, mpdigit *b, int blen);
|
| 122 |
|
153 |
|
| 123 |
/* divide the 2 digit dividend by the one digit divisor and stick in quotient */
|
154 |
/* divide the 2 digit dividend by the one digit divisor and stick in quotient */
|
| 124 |
/* we assume that the result is one digit - overflow is all 1's */
|
155 |
/* we assume that the result is one digit - overflow is all 1's */
|
| 125 |
void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
|
156 |
void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
|
| 126 |
|
157 |
|
| Line 146... |
Line 177... |
| 146 |
CRTres* crtin(CRTpre*, mpint*); /* convert mpint to residues */
|
177 |
CRTres* crtin(CRTpre*, mpint*); /* convert mpint to residues */
|
| 147 |
void crtout(CRTpre*, CRTres*, mpint*); /* convert residues to mpint */
|
178 |
void crtout(CRTpre*, CRTres*, mpint*); /* convert residues to mpint */
|
| 148 |
void crtprefree(CRTpre*);
|
179 |
void crtprefree(CRTpre*);
|
| 149 |
void crtresfree(CRTres*);
|
180 |
void crtresfree(CRTres*);
|
| 150 |
|
181 |
|
| - |
|
182 |
/* fast field arithmetic */
|
| - |
|
183 |
typedef struct Mfield Mfield;
|
| - |
|
184 |
|
| - |
|
185 |
struct Mfield
|
| - |
|
186 |
{
|
| - |
|
187 |
mpint;
|
| - |
|
188 |
int (*reduce)(Mfield*, mpint*, mpint*);
|
| - |
|
189 |
};
|
| - |
|
190 |
|
| - |
|
191 |
mpint *mpfield(mpint*);
|
| - |
|
192 |
|
| - |
|
193 |
Mfield *gmfield(mpint*);
|
| - |
|
194 |
Mfield *cnfield(mpint*);
|
| 151 |
|
195 |
|
| 152 |
#pragma varargck type "B" mpint*
|
196 |
#pragma varargck type "B" mpint*
|
| - |
|
197 |
|
| 153 |
#endif
|
198 |
#endif
|