CryptoBook
Search…
Integer Factorization

Overview

Given a composite integer
nn
, can it be decomposed as a product of smaller integers (hopefully as a unique product of prime factors)?
As easy as it may sound, integer factorization in polynomial time on a classical computer stands one of the unsolved problems in computation for centuries!
Lets start dumb, all we need to do is check all the numbers
1<p<n1 < p < n
such that
pnp|n
or programmatically n%p==0
1
def factors(n):
2
divisors = []
3
for p in range(1,n):
4
if n%p==0:
5
divisors.append(p)
6
return divisors
Copied!
Seems like its an
O(n)O(n)
algorithm! whats all the deal about? By polynomial time, we mean polynomial time in
bb
when
nn
is a b-bit number, so what we looking at is actually a
O(2b)O(2^b)
which is actually exponential (which everyone hates)
Now taking a better look at it, one would realize that a factor of
nn
can't be bigger than
n\sqrt{n}
Other observation would be, if we already checked a number (say 2) to not be a divisor, we dont need to check any multiple of that number since it would not be a factor.
Last modified 5mo ago
Export as PDF
Copy link