Commits

Anonymous committed 2ae85b0

Introduce fermats_factorization_method.

Comments (0)

Files changed (1)

 #!/usr/bin/env python
 
+import math
 from utils import dez_bin
 
 def square(base, c):
     # print 'It took %d times' % times
     return res
 
+def is_square(a):
+    """Is `a` the square of one number? If so, return number. Else None"""
+    return math.sqrt(a) % 1 == 0 and int(math.sqrt(a)) or None
+
+def fermats_factorization_method(n):
+    a = int(math.ceil(math.sqrt(n)))
+    b = a**2 - n
+    while not is_square(b):
+        a += 1
+        b = a**2 - n
+    return a - math.sqrt(b)
+
+
 if __name__ == '__main__':
     a = 12334 # 2
     c = 8402 # 11