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
|
/*
* Some number-theoretic algorithms
*
* Copyright © 1999 Bart Massey.
* All Rights Reserved. See the file COPYING in this directory
* for licensing information.
*
* Bart Massey 1999/1
*
* bigpowmod(b,e,m): returns (b**e) mod m
* [gcd(a,b): accelerated greatest-common-divisor (built-in)]
* extgcd(a,b): extended GCD returns struct coeff
* zminv(a,n): inverse of a in Z*n
*/
namespace Numbers {
public int bigpowmod(int b, int e, int m) {
if (e == 0)
return 1;
if (e == 1)
return b % m;
int tmp = bigpowmod(b, e // 2, m);
int tmp2 = (tmp * tmp) % m;
if (e % 2 == 0)
return tmp2;
return (tmp2 * b) % m;
}
public typedef struct { int d, x, y; } coeff;
/* Extended Euclid's Algorithm */
public coeff extgcd(int a, int b) {
if (b == 0)
return (coeff) { .d = a, .x = 1, .y = 0};
coeff t = extgcd(b, a % b);
int x = t.x;
t.x = t.y;
t.y = x - (a // b) * t.y;
return t;
}
/* multiplicative inverse of a mod n */
public int zminv(int a, int n) {
coeff e = extgcd(a, n);
if (e.x < 0)
return n + e.x;
return e.x;
}
}
|
