Section 12.5 Introduction to Factorization
Subsection 12.5.1 Factorization and the RSA
Let's look at another toy RSA problem to get a sense of what is going on. First, I choose a modulusxxxxxxxxxx
n=899
print("There are %s prime factors and their powers are %s and %s."%(len(n.factor()), n.factor()[0][1], n.factor()[1][1]))
xxxxxxxxxx
e=13
print("We choose n=%s and exponent e=%s, and verify that gcd(e,phi(n))=1: %s"%(n,e,1==gcd(e,euler_phi(n))))
xxxxxxxxxx
x=11
message=mod(x,n)^e
message
euler_phi(899)
directly.) Well, we do know Question 12.5.1.
Can you quickly now factor
Hint: be smart about it. Think strategically; how should I have chosen a public modulus \(n\) to make this hard to do? How should \(p\) and \(q\) relate?
Sage note 12.5.2. Trying your primes yourself.
You can fill in the values you got for p
and q
here to make things work. Try it!
xxxxxxxxxx
p=
q=
f=inverse_mod(e,(p-1)*(q-1))
f
When we decrypt, we should get the original message
xxxxxxxxxx
message^f
Fact 12.5.3.
If I know
Proof.
Of course, if we know \(\phi(n)\text{,}\) we already can crack the code, but who cares; maybe we are given \(\phi(n)\) and \(n\) and want the factorization. Here is the short proof.
Suppose the (as yet unknown) primes are \(p\) and \(q\text{.}\) Then expand our formula to
We now can represent both \(p+q\) and \(pq\) as formulas in \(n\) and \(\phi(n)\text{:}\)
\(\displaystyle p+q=n-\phi(n)+1\)
\(\displaystyle pq=n\)
Where might we have a formula with \(p+q\) and \(pq\text{?}\) That should seem familiar …
So we can simply use the quadratic formula on this expression to get the values for \(p\) and \(q\text{!}\)
Example 12.5.4.
Continuing the example above,
gives
Subsection 12.5.2 Trial division
The first, and oldest, method of factoring is one you already know, and maybe used a few minutes ago – trial factorization, or trial division. It is the method we used with the Sieve of Eratosthenes; you just try each prime number, one by one. In Algorithm 6.2.3, do you remember what the highest number you would have to try is in order to factor a givenSage note 12.5.5. Code for trial division.
This is one of the few places where it really is important to follow the code. That said, the details of the syntax are not as important as the algorithm – unless you want to harness the power of computers more effectively!
xxxxxxxxxx
def TrialDivFactor(n): # We define the function
p = next_prime(1) # We start off by testing the next prime after 1
top = ceil(math.sqrt(n)) # This was proved to be the biggest number we need
while p < top: # As long as the prime is less than that bound, we keep going
if mod(n,p)==0: # In this case, p divides n and we're done!
break # This is Python's way of saying we are done searching
p=next_prime(p) # Otherwise, we try the next prime until we're done looking
if n==1: # We probably could have checked for this right away
print("1 is not prime") # Well, 1 is not a prime!
elif p==n: # If we get all the way through and end with a prime...
print(n,"is prime") # Then our number was prime
elif mod(n,p)==0: # But otherwise... (!)
print(n,"factors as",p,"times",n/p) # We have a factorization!
else: # And finally...
print(n,"is prime") # We must have gotten lucky.
Algorithm 12.5.6. Trial Factorization.
To factor
xxxxxxxxxx
for z in range(1,18):
TrialDivFactor(z)
timeit
in an interact properly.xxxxxxxxxx
TrialDivFactor(6739815371)
timeit('TrialDivFactor(6739815371)')
xxxxxxxxxx
print(6739815371.trial_division())
timeit('6739815371.trial_division()')
xxxxxxxxxx
print(6739815371.factor())
timeit('6739815371.factor()')
xxxxxxxxxx
timeit('TrialDivFactor(997*991)')
xxxxxxxxxx
timeit('(997*991).trial_division()')
xxxxxxxxxx
timeit('(997*991).factor()')
Subsection 12.5.3 Starting in the middle
So much for trial division! But we have other tools at our disposal. Some of you might have tried something other than straight trial factorization when attackingFact 12.5.7.
Write
Proof.
Namely, \(n\) is the difference of the squares of \(s=\frac{a+b}{2}\) and \(t=\frac{a-b}{2}\text{:}\)
Remark 12.5.8.
Why is it fine to assume
Algorithm 12.5.9. The Fermat factorization algorithm.
To find a factor for a number
Check whether
is itself a perfect square-
That means we essentially turned
Once you succeed, then
Proof.
It should be clear why \(a\) and \(b\) are the factors. But how do we know this algorithm terminates?
Assuming you started with \(s\) as instructed, eventually you will reach \(s=(n+1)/2\text{,}\) which is much larger than \(\sqrt{n}\text{.}\) But then \(((n+1)/2)^2-n=\frac{n^2+2n+1-4n}{4}=((n-1)/2)^2\text{.}\) You should check that this gives us the trivial factorization \(n=n\cdot 1\text{,}\) though! (See Exercise 12.7.11)
xxxxxxxxxx
def FermatFactor(n,verbose=False):
if n%2==0:
raise TypeError("Input must be odd!")
s=ceil(math.sqrt(n))
top=(n+1)/2
while is_square(s^2-n)==0:
if verbose:
print(s,"squared minus",n,"is",s^2-n,"which is not a perfect square")
s=s+1
t=sqrt(s^2-n)
print("Fermat found that",s,"squared minus",t,"squared equals",n)
if s^2==n:
print("So",n,"was already a perfect square,",s,"times",s)
elif s<top:
print("So",s+t,"times",s-t,"equals",(s-t)*(s+t),"which is",n)
elif s==top:
print("So Fermat did not find a factor, which means",n,"is prime!")
Example 12.5.10.
Before we move on, let's try to factor
After you attempt this by hand, you can see what Sage does with them to check.
xxxxxxxxxx
FermatFactor(143,verbose=True)
Well, we struck gold on the first try here! That happens if your number is the product of two primes which are two apart. (Such primes are known as twin primes, and have some interesting stories. Among other things, calculating with them helped find a bug in the Pentium computer chip in 1995; see Subsection 22.3.2.)
xxxxxxxxxx
FermatFactor(93,verbose=True)
As you can see, we probably would have been better off with trial division for