Skip to content

Instantly share code, notes, and snippets.

@nettok
Created May 7, 2015 05:08
Show Gist options
  • Save nettok/84e54e5e70fe3eb367c1 to your computer and use it in GitHub Desktop.
Save nettok/84e54e5e70fe3eb367c1 to your computer and use it in GitHub Desktop.
/// Exponenciación modular ((b^e) % m)
fn pow_mod(b: usize, mut e: usize, m: usize) -> usize {
// if e == 0 { return 1; }
// if e % 2 == 0 {
// pow_mod(b, e / 2, m).pow(2) % m
// } else {
// (b * pow_mod(b, e - 1, m)) % m
// }
// p < 0 && throw(DomainError())
// b = oftype(m,mod(b,m)) # this also checks for divide by zero
// p == 0 && return mod(one(b),m)
// (m == 1 || m == -1) && return zero(m)
// t = prevpow2(p)
// local r::T
// r = 1
// while true
// if p >= t
// r = mod(widemul(r,b),m)
// p -= t
// end
// t >>>= 1
// t <= 0 && break
// r = mod(widemul(r,r),m)
// end
// return r
//prevpow2(x::Unsigned) = (one(x)>>(x==0)) << ((sizeof(x)<<3)-leading_zeros(x)-1)
fn prev_power_of_two(n: usize) -> usize {
let bits = n.count_ones() + n.count_zeros();
n.wrapping_shr(bits - n.leading_zeros() - 1).wrapping_shl(bits - n.leading_zeros() - 2)
}
if e == 0 { return 1 % m; }
if m == 1 { return 0; }
let mut t = prev_power_of_two(e);
let mut r = 1;
loop {
if e >= t {
r = (r * b) % m;
e -= t;
}
t = t.shr(1);
if t <= 0 { break; }
r = (r * r) % m;
}
r
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment