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 * 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 * r) % m if e.odd? |
||
b = (b * b) % m |
b = (b * b) % m |
||
e >>= 1 |
e >>= 1 |