-
Notifications
You must be signed in to change notification settings - Fork 1
/
fermats_factorization.py
80 lines (69 loc) · 2.22 KB
/
fermats_factorization.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# -*- coding: utf-8 -*-
from factorization_function import *
from benchmark import *
# Fermats Factorization
class FermatsFactorization(FactorizationFunction):
@classmethod
def getCharacteristics(self):
c = FactorizationFunctionCharacteristics()
c.canFactorizePrimeComposites = True
c.canFactorizeEvenComposites = False
return c
@classmethod
def getOneFactor(self, n, benchmark = Benchmark()):
# Edge case even numbers except 2
if n % 2 == 0 and n != 2:
return None
elif n == 2:
return [1, 2]
# Setup
factors = []
a = ceil(sqrt(n))
b2 = a**2 - n
# Start of algorithm
benchmark.start()
while not b2.is_square():
benchmark.iterate()
a += 1
benchmark.start("square")
b2 = a**2 - n
benchmark.stop("square")
b = int(sqrt(b2))
p = a - b
q = a + b
if p != 1:
factors.append(p)
if q != 1:
factors.append(q)
# End of algorithm
benchmark.stop()
return factors
@classmethod
def factorize(self, n, returnBenchmark=False):
# Edge case (constant time)
if n == 1:
return ([1], Benchmark()) if returnBenchmark else [1]
# Setup
benchmark = Benchmark()
factors = [1]
# Numbers to factor
stack = [n]
P = Primes()
# Start of algorithm
while len(stack) > 0:
a = stack.pop()
benchmark.start("primalityTest")
isPrime = a in P
benchmark.stop("primalityTest")
if isPrime:
# a is a prime, append to found factors
factors.append(a)
else:
# a is not a prime, factorize
benchmark.iterate("algorithm iterations")
possibleFactors = self.getOneFactor(a, benchmark)
if possibleFactors is not None:
# Factor is a true factor, append it and a / factor to found factors
stack += possibleFactors
# End of algorithm
return (factors, benchmark) if returnBenchmark else factors