Integer Factorization
ASSIGNMENT 2
Bachelor of Technology
in
Engineering Physics
by
Jatin Lather
(210150006)
Under the Supervision of
Scientist Saibal Kumar
DRDO
Contents
Contents
1 Introduction 1
1.1 What is Integer Factorization . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Decision Version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 What is different in Integer Factorization Problem ? . . . . . . . . . . . . 2
2 Deterministic Algorithms for Integer Factorization 3
2.1 Time Complexity of Algorithm solvable in P class . . . . . . . . . . . . . 3
2.2 Trial Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Fermat’s factorization method . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Pollard’s Rho Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Quadratic Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.6 Best Algorithm for Integer Factorization : General number field sieve . . 8
3 Real Life application of Integer Factorization 11
3.1 What if it is solved ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Is it even ideal ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Chapter 1
Introduction
1.1 What is Integer Factorization
• In number theory, integer factorization is the decomposition of a positive integer
into a product of integers.
– Composite Numbers :Every positive integer greater than 1 is product of two
or more integer factors, in which case it is called a composite number
– Prime Number : If not the product of more than 2 integers and factors include
1 and itself , then integer is prime number .
• In integer factorization we are trying to write an integer as a product of prime num-
bers .
– Prime Factorization Theorem: For each natural number n, there is a unique
factorization n = pa11 pa22 . . . pak k , where exponents ai are positive integers and
p1 < p2 < . . . < pk are primes.
– A prime factorization algorithm typically involves testing whether each factor
is prime each time a factor is found.
1
Chapter I. Introduction 2
1.2 Decision Version
For every natural numbers n and k , does n have a factor smaller than k besides 1 ?
• Let us first define what is co-NP :While an NP problem asks whether a given in-
stance is a yes-instance, its complement asks whether an instance is a no-instance,
which means the complement is in co-NP. Any yes-instance for the original NP
problem becomes a no-instance for its complement, and vice versa.
• A problem L is co-NP-complete if and only if L is in co-NP and for any problem
in co-NP, there exists a polynomial-time reduction from that problem to L.
Integer Factorization belongs to both NP and co-NP class meaning that both ”yes” and
”no” answers can be verified in polynomial time while does not belong to P class . No
algorithm has been published that can factor all integers in polynomial time .
1.3 What is different in Integer Factorization Problem ?
”Easy Decision Problem , Hard Search Problem ”
One novel problem in mathematics and theorotical computer science is to find determin-
istic algorithms that are polynomially time solvable for integer factorization .
Chapter 2
Deterministic Algorithms for Integer
Factorization
2.1 Time Complexity of Algorithm solvable in P class
An algorithm that can factor all integers in polynomial time , that is, that can factor a b-bit
number n in time O(bk ) for some constant k. Neither the existence nor non-existence of
such algorithms has been proved, but it is generally suspected that they do not exist.
Before discussing some deterministic algorithm , we should know what is :
• Special -Purpose Algorithm :A special-purpose factoring algorithm’s running time
depends on the properties of the number to be factored or on one of its unknown
factors: size, special form, etc.
• General -Purpose Algorithm:It has a running time which depends solely on the
size of the integer to be factored.
3
Chapter II. Deterministic Algorithms for Integer Factorization 4
2.2 Trial Division
The essential idea behind trial division tests to see if an integer n, the integer to be factored,
can be divided by each number in turn that is less than the square root of n.
def trial_d ivision ( n : int ) -> list [ int ]:
a = []
while n % 2 == 0:
a . append (2)
n //= 2
f = 3
while f * f <= n :
if n % f == 0:
a . append ( f )
n //= f
else :
f += 2
if n != 1: a . append ( n )
# Only odd number is p o s s i b l e
return a
This version of trial division is guaranteed to find a factor of n if there is one since they
check all possible factors of n — and if n is a prime number, this means trial factors all
the way up to n.
It is a Special Purpose Algorithm whose running time depends on the size of smallest
prime factor.
√
Time complexity = O( n)
Chapter II. Deterministic Algorithms for Integer Factorization 5
2.3 Fermat’s factorization method
The idea of the method is to represent an odd integer as the difference of two squares.
That is, we search for integers a such that a2 − n is a square .
An old strategy to factor a number is to express it as the difference of two non-consecutive
squares. If one can write n in the form a2 − b2 where a and b are nonnegative integers,
then one can immediately factor n as (a + b)(a − b)
FermatFactor ( N ): // N should be odd
a = ceiling ( sqrt ( N ))
b2 = a * a - N
repeat until b2 is a square :
a = a + 1
b2 = a * a - N
// equivalently :
// b2 = b2 + 2* a + 1
// a = a + 1
return a - sqrt ( b2 ) // or a + sqrt ( b2 )
√
Time Complexity = O((n + 1)/2 − n)
2.4 Pollard’s Rho Algorithm
The Pollards rho method performs a random search using the cyclical properties of some
sequence .
It uses only a small amount of space, and its expected running time is proportional to the
square root of the smallest prime factor of the composite number being factorized. The
Pollards rho method is based on the combination of two ideas called the
Chapter II. Deterministic Algorithms for Integer Factorization 6
• Birthday paradox:In a group of just 23 people, there is a greater than 50% chance
that two people will share the same birthday.In both scenarios—Pollard’s Rho algo-
rithm and the Birthday Paradox—the idea is to exploit the fact that in certain random
processes, collisions occur more frequently than one might expect intuitively.
• Pigeonhole principle: It states that if you have more ”pigeons” (objects) than ”pi-
geonholes” (categories), then at least one pigeonhole must contain more than one
pigeon.In Pollard’s Rho algorithm, the algorithm generates a sequence of values
through repeated applications of a function. These values belong to a finite group.
However, the number of possible values in the group is finite, whereas the number
of values generated by the algorithm may be infinite. This discrepancy between the
size of the group and the number of outputs creates the possibility of collisions.
The algorithm takes as its inputs n, the integer to be factored; and g(x) a polynomial in x
computed modulo n. g(x) = (x2 + 1)mod(n)
a=c(mod(n)) can also be written as n/(a − c), which means ”n divides the difference
between a and c.”
Algorithm starts by initializing X0 =1 and then generating sequence according to g(x).
x = 1 // starting value
y = x
d = 1
while d = 1:
x = g ( x )// moves forward by one node
y = g ( g ( y ))// moves forward by 2 nodes
d = gcd (| x - y | , n )
if d = n :
return failure
else :
return d
Chapter II. Deterministic Algorithms for Integer Factorization 7
We use almost no storage on verge of extra computation as everytime sequence xi is
generated , another sequence yi =g(g(yi −1)) .
Then every time we apply g to generate the next element of the xi sequence we will apply
g twice to also generate the next yi element in the sequence.
√
Time Complexity:O( p) here p is the smallest prime factor
2.5 Quadratic Sieve
B-smooth numbers: A positive integer n is said to be y-smooth if it does not have
any prime factor exceeding y . B is the set of all such factors.
The algorithm attempts to set up a congruence of squares modulo n (the integer to be
factorized), which often leads to a factorization of n. The algorithm works in two phases:
the data collection phase, where it collects information that may lead to a congruence of
squares; and the data processing phase, where it puts all the data it has collected into a
matrix and solves it to obtain a congruence of squares.
The quadratic sieve factorization method is an algorithm for finding integers a and b such
that a2 ≡ b2 (mod n) (Congruence of Square )
√
To factorize the integer n, Fermat’s method entails a search for a single number a , n<
a < n − 1 such that the remainder of a2 divided by n is a square. But these a are hard
to find. The quadratic sieve consists of computing the remainder of a2 /n for several a,
then finding a subset of these whose product is a square. This will yield a congruence of
squares.
No. of such a’s is the no. of prime factors in the smoothness bound (π(B)) + 1.
Chapter II. Deterministic Algorithms for Integer Factorization 8
In general we can say that we specifically look for numbers such that b = a2 mod(n) has
only small prime factors, smaller than B, that is, Bsmooth numbers.
Output = gcd(a+b,n),gcd(a-b,n).
Example : n = 1649. We begin as in Fermat’s method and for xi2 we take the numbers
√
just above n.
412 = 1681 ≡ 32 (mod 1649)
422 = 1764 ≡ 115 (mod 1649)
432 = 1849 ≡ 200 (mod 1649)
Unlike the Fermat method which would require further computation, with this new ap-
proach of combining congruences we can stop here. Since 32 × 200 = 6400 = 802 , we
have found that (41 × 43)2 ≡ 802 (mod 1649).
(43.41) ≡ 114 (mod 1649)
1142 ≡ 802 (mod 1649)
Hence Output = gcd(114+80,1649),gcd(114-80,1649) = 194*17
1
Time Complexity: O(B 2 +o(1) ) where B is parameter representing the size of the factor
base(Smoothness Bound )
2.6 Best Algorithm for Integer Factorization : General
number field sieve
When using quadratic sieve to factor a large number n, it is necessary to search for smooth
√
numbers (i.e. numbers with small prime factors) of order n. The size of these values is
exponential in the size of n . The general number field sieve, on the other hand, manages to
Chapter II. Deterministic Algorithms for Integer Factorization 9
search for smooth numbers that are subexponential in the size of n. Since these numbers
are smaller, they are more likely to be smooth than the numbers inspected in previous
algorithms. This is the key to the efficiency of the number field sieve.
Time Complexity: O(exp((c + o(1))(log n)1/3 (log log n)2/3 )) In this expression, n repre-
sents the integer to be factorized, and c is a constant specific to the GNFS algorithm.
Chapter 3
Real Life application of Integer
Factorization
3.1 What if it is solved ?
Not all numbers of a given length are equally hard to factor. The hardest instances of these
problems (for currently known techniques) are semiprimes, the product of two prime
numbers.
When they are both large, for instance more than two thousand bits long, randomly cho-
sen, and about the same size (but not too close, for example, to avoid efficient factorization
by Fermat’s factorization method), even the fastest prime factorization algorithms on the
fastest computers can take enough time to make the search impractical; that is, as the num-
ber of digits of the integer being factored increases, the number of operations required to
perform the factorization on any computer increases drastically.
Many cryptographic protocols are based on the difficulty of factoring large composite
integers or a related problem—for example, the RSA problem.
11
References 12
An algorithm that efficiently factors an arbitrary integer would render RSA-based public-
key cryptography insecure.
3.2 Is it even ideal ?
If a quantum computer with a sufficient number of qubits could operate without succumb-
ing to quantum noise and other quantum-decoherence phenomena, then Shor’s algorithm
could be used to break public-key cryptography schemes.
RSA is based on the assumption that factoring large integers is computationally intractable.
As far as is known, this assumption is valid for classical (non-quantum) computers; no
classical algorithm is known that can factor integers in polynomial time. However, Shor’s
algorithm shows that factoring integers is efficient on an ideal quantum computer, so it
may be feasible to defeat RSA by constructing a large quantum computer.
