Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def fermat_factor(n):
- assert n % 2 != 0 # Odd integers only
- a = gmpy2.ceil(gmpy2.sqrt(n))
- b2 = gmpy2.square(a) - n
- while not is_square(b2):
- a += 1
- b2 = gmpy2.square(a) - n
- factor1 = a + gmpy2.sqrt(b2)
- factor2 = a - gmpy2.sqrt(b2)
- return int(factor1), int(factor2)
- def is_square(n):
- root = gmpy2.sqrt(n)
- return root % 1 == 0 # '4.0' will pass, '4.1212' won't
- factor1 = a + gmpy2.sqrt(b2)
- factor2 = a - gmpy2.sqrt(b2)
- factor1 = factor2 = gmpy2.sqrt(b2)
- factor1 += a
- factor2 -= a
Add Comment
Please, Sign In to add comment