The following methods would be useful for cryptography work:
bool isEven();
static BigInt? pow(BigInt? x, BigInt? y);
static BigInt? modPow(BigInt? x, BigInt? y, BigInt? m);
bool isPrime();
static BigInt? rand(BigInt? n); // returns a value 0 to (n-1)
static BigInt? gcd(BigInt? a, BigInt? b);
I have already built all of these, though I'd recommend double checking them.
bool isEven(); -- There's almost certainly a better way to do this with access to internals:
bool isEven(BigInt n) {
return cast(bool)(((n >> 1) << 1) == n);
}
static BigInt? pow(BigInt? x, BigInt? y); -- Adapted from http://en.wikipedia.org/wiki/Exponentiation_by_squaring:
BigInt bigPow(BigInt x, BigInt n) {
BigInt ret;
if (n == 0) {
ret = 1;
}
else if (n == 1) {
ret = x;
}
else if (n == 2) {
ret = x * x;
}
else if (isEven(n)) { // even
ret = bigPow(x, n >> 1);
ret *= ret;
}
else { // odd
ret = bigPow(x, ((n - 1) >> 1));
ret *= ret;
ret *= x;
}
return ret;
}
static BigInt? modPow(BigInt? x, BigInt? y, BigInt? m); -- Adapted from http://en.wikipedia.org/wiki/Modular_exponentiation:
BigInt modPow(BigInt base, BigInt exp, BigInt mod) {
BigInt ret = 1;
BigInt lexp = exp;
while (lexp > 0) {
if (!isEven(lexp)) {
ret = (ret * base) % mod;
}
lexp >>= 1;
base = (base * base) % mod;
}
return ret;
}
bool isPrime(); -- Adapted from http://en.literateprograms.org/Miller-Rabin_primality_test_%28C%2C_GMP%29:
public {
bool isPrime(BigInt n) {
if (n < 2) return false;
else if (n == 2) return true;
BigInt a;
int repeat;
for(repeat=0; repeat<20; repeat++) {
do {
a = bigRand(n);
} while (a == 0);
if (!miller_rabin_pass(a, n)) {
return false;
}
}
return true;
}
}
private {
bool miller_rabin_pass(BigInt a, BigInt n) {
int i, s;
BigInt a_to_power, d, n_minus_one;
n_minus_one = n - 1;
s = 0;
d = n_minus_one;
while (isEven(d)) {
d >>= 1;
s++;
}
a_to_power = modPow(a, d, n);
if (a_to_power == 1) {
return true;
}
for(i = 0; i < (s-1); i++) {
if (a_to_power == n_minus_one) {
return true;
}
a_to_power = (a_to_power * a_to_power) % n;
}
if (a_to_power == n_minus_one) {
return true;
}
return false;
}
}
static BigInt? rand(BigInt? n); -- Original methodology. Should be checked:
BigInt bigRand(BigInt n) {
if (n < 0) throw new Exception("Parameter must be positive");
BigInt ret;
Random r = new Random();
ret = r.uniform!(uint);
while (ret < n) {
ret *= r.uniform!(uint);
}
ret %= n;
return ret;
}
static BigInt? gcd(BigInt? a, BigInt? b); -- Adapted from http://en.wikipedia.org/wiki/Greatest_common_divisor (Euclid's Algorithm):
BigInt gcd(BigInt a, BigInt b) {
BigInt ret;
if (b == 0) {
ret = a;
}
else {
ret = gcd( b, a - (b * (a / b)) );
}
return ret;
}
