Miller–Rabin primality test: Difference between revisions

Content added Content deleted
Line 1,042: Line 1,042:
# Compute b**e mod m
# Compute b**e mod m
private def powmod(b, e, m)
private def powmod(b, e, m)
r = 1.to_big_i
r, b = 1, b.to_big_i
b = b.to_big_i % m
while e > 0
while e > 0
r = (r * b) % m if e.odd?
r = (b * r) % m if e.odd?
b = (b * b) % m
b = (b * b) % m
e >>= 1
e >>= 1
Line 1,123: Line 1,122:
# Compute b**e mod m
# Compute b**e mod m
private def powmod(b, e, m)
private def powmod(b, e, m)
r = 1.to_big_i
r, b = 1, b.to_big_i
b = b.to_big_i % m
while e > 0
while e > 0
r = (r * b) % m if e.odd?
r = (b * r) % m if e.odd?
b = (b * b) % m
b = (b * b) % m
e >>= 1
e >>= 1