Scribd
Upload
14 views

Integer Factorization - Wikipedia

The document discusses integer factorization, an unsolved problem in computer science. It describes factorization as decomposing a positive integer into prime factors. While small numbers can be factored mentally, larger numbers require more sophisticated algorithms. Efficiently factoring arbitrary integers would break cryptography like RSA, but no efficient algorithm is currently known.

Uploaded by

darnit2703
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views

Integer Factorization - Wikipedia

The document discusses integer factorization, an unsolved problem in computer science. It describes factorization as decomposing a positive integer into prime factors. While small numbers can be factored mentally, larger numbers require more sophisticated algorithms. Efficiently factoring arbitrary integers would break cryptography like RSA, but no efficient algorithm is currently known.

Uploaded by

darnit2703
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Integer factorization

Unsolved problem in computer science:

Can integer factorization be solved in polynomial time on a classical computer?

(more unsolved problems in computer science)

In number theory, integer factorization is the decomposition of a positive integer into a product
of integers. Every positive integer greater than 1 is either the product of two or more integer
factors, in which case it is called a composite number, or it is not, in which case it is called a
prime number. For example, 15 is a composite number because 15 = 3 · 5, but 7 is a prime
number because it cannot be decomposed in this way. If one of the factors is composite, it can
in turn be written as a product of smaller factors, for example 60 = 3 · 20 = 3 · (5 · 4). Continuing
this process until every factor is prime is called prime factorization; the result is always unique
up to the order of the factors by the prime factorization theorem.

To factorize a small integer n using mental or pen-and-paper arithmetic, the simplest method is
trial division: checking if the number is divisible by prime numbers 2, 3, 5, and so on, up to the
square root of n. For larger numbers, especially when using a computer, various more
sophisticated factorization algorithms are more efficient. A prime factorization algorithm
typically involves testing whether each factor is prime each time a factor is found.

When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm
is known. However, it has not been proven that such an algorithm does not exist. The presumed
difficulty of this problem is important for the algorithms used in cryptography such as RSA
public-key encryption and the RSA digital signature.[1] Many areas of mathematics and computer
science have been brought to bear on the problem, including elliptic curves, algebraic number
theory, and quantum computing.

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 chosen, 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 number 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. An algorithm that efficiently factors an
arbitrary integer would render RSA-based public-key cryptography insecure.

Prime decomposition

Prime decomposition of n = 864 as


2 5 × 33

By the fundamental theorem of arithmetic, every positive integer has a unique prime
factorization. (By convention, 1 is the empty product.) Testing whether the integer is prime can
be done in polynomial time, for example, by the AKS primality test. If composite, however, the
polynomial time tests give no insight into how to obtain the factors.

Given a general algorithm for integer factorization, any integer can be factored into its
constituent prime factors by repeated application of this algorithm. The situation is more
complicated with special-purpose factorization algorithms, whose benefits may not be realized
as well or even at all with the factors produced during decomposition. For example, if
n = 171 × p × q where p < q are very large primes, trial division will quickly produce the factors 3
and 19 but will take p divisions to find the next factor. As a contrasting example, if n is the
product of the primes 13729, 1372933, and 18848997161, where
13729 × 1372933 = 18848997157, Fermat's factorization method will begin with
⌈√ n ⌉ = 18848997159 which immediately yields b = √ a2 − n = √ 4 = 2 and hence the factors
a − b = 18848997157 and a + b = 18848997161. While these are easily recognized as composite
and prime respectively, Fermat's method will take much longer to factor the composite number
because the starting value of ⌈√ 18848997157 ⌉ = 137292 for a is a factor of 10 from 1372933.

Current state of the art

Among the b-bit numbers, the most difficult to factor in practice using existing algorithms are
those semiprimes whose factors are of similar size. For this reason, these are the integers used
in cryptographic applications.

In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and
Paul Zimmermann factored a 240-digit (795-bit) number (RSA-240) utilizing approximately 900
core-years of computing power.[2] The researchers estimated that a 1024-bit RSA modulus would
take about 500 times as long.[3]

You might also like