Factors of a Mersenne number: Difference between revisions

Content added Content deleted
Line 880: Line 880:


def mersenne_factor(p)
def mersenne_factor(p)
mp_num = 2.to_big_i ** p - 1
mers_num = 2.to_big_i ** p - 1
k = 1.to_big_i
kp2 = p2 = 2.to_big_i * p
while (k * 2 * p - 1) ** 2 < mp_num
while (kp2 - 1) ** 2 < mers_num
q = k * 2 * p + 1
q = kp2 + 1
if prime?(q) && [1, 7].includes?(q % 8) && (powmod(2, p, q) == 1)
if prime?(q) && [1, 7].includes?(q % 8) && (powmod(2, p, q) == 1)
# q is a factor of 2**p-1
# q is a factor of 2**p-1
return q
return q
end
end
k += 1
kp2 += p2
end
end
true # could also set to `0` value to check for
true # could also set to `0` value to check for
Retrieved from "https://rosettacode.org/wiki/Factors_of_a_Mersenne_number"