HOME

TheInfoList




In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen ...

number theory
, integer factorization is the decomposition of a
composite number A composite number is a positive integer In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calcul ...
into a product of smaller integers. If these
factors
factors
are further restricted to
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s, the process is called prime factorization. When the numbers are sufficiently large, no efficient,
non-quantum
non-quantum
integer
factorization In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

factorization
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

algorithm
is known. However, it has not been proven that no efficient algorithm exists. The presumed difficulty of this problem is at the heart of widely used algorithms in
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia ''-logy'' is a suffix in the English language, used with words originally adapted from Ancient Greek ending in (''- ...

cryptography
such as RSA. Many areas of
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
and
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , and . Computer science ...
have been brought to bear on the problem, including
elliptic curve In mathematics, an elliptic curve is a Nonsingular variety, smooth, Projective variety, projective, algebraic curve of Genus of an algebraic curve, genus one, on which there is a specified point ''O''. An elliptic curve is defined over a field ...
s,
algebraic number theory Algebraic number theory is a branch of number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is th ...
, and
quantum computing Quantum computing is a type of computation Computation is any type of that includes both al and non-arithmetical steps and which follows a well-defined model (e.g. an ). Mechanical or electronic devices (or, , people) that perform computatio ...

quantum computing
. In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240-digit (795-bit) number (
RSA-240 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...
) utilizing approximately 900 core-years of computing power. The researchers estimated that a 1024-bit RSA modulus would take about 500 times as long. Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are
semiprime In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
s, the product of two prime numbers. When they are both large, for instance more than two thousand
bit The bit is a basic unit of information in computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithm of an algorithm (Euclid's algo ...
s 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 primes 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 In cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia ''-logy'' is a suffix in the English language, used with words originally adapted from Ancient Gree ...
. An algorithm that efficiently factors an arbitrary integer would render RSA-based
public-key File:Private key signing.svg, 250px, In this example the message is digital signature, digitally signed, but not encrypted. 1) Alice signs a message with her private key. 2) Bob can verify that Alice sent the message and that the message has ...
cryptography insecure.


Prime decomposition

By the
fundamental theorem of arithmetic In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "wh ...
, every positive integer has a unique
prime factor A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
ization. (By convention, 1 is the
empty product In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
.) Testing whether the integer is prime can be done in
polynomial time In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of com ...
, for example, by the
AKS primality test The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic Determinism is the Philosophy, philosophical view that all events are determined completely by previously existing causes ...
. 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 factor A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s 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 where are very large primes,
trial division Trial division is the most laborious but easiest to understand of the integer factorization algorithms. 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 th ...

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 , Fermat's factorization method will begin with \lceil\sqrt\rceil = 18848997159 which immediately yields b = \sqrt = \sqrt = 2b and hence the factors and . 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 \lceil\sqrt\rceil = 137292 for ''a'' is nowhere near 1372933.


Current state of the art

Among the ''b''-bit numbers, the most difficult to factor in practice using existing algorithms are those that are products of two primes of similar size. For this reason, these are the integers used in cryptographic applications. The largest such semiprime yet factored was
RSA-250 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...
, a 829-bit number with 250 decimal digits, in February 2020. The total computation time was roughly 2700 core-years of computing using
Intel Intel Corporation is an American multinational corporation A multinational company (MNC) is a corporate A corporation is an organization—usually a group of people or a company A company, abbreviated as co., is a Legal personalit ...

Intel
Xeon Xeon ( ) is a brand of x86 x86 is a family of instruction set architecture In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes ins ...
Gold 6130 at 2.1 GHz. Like all recent factorization records, this factorization was completed with a highly optimized implementation of the
general number field sieve In number theory, the general number field sieve (GNFS) is the most algorithmic efficiency, efficient classical algorithm known for integer factorization, factoring integers larger than . Heuristically, its Computational complexity theory, complexi ...
run on hundreds of machines.


Difficulty and complexity

No
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

algorithm
has been published that can factor all integers in
polynomial time In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of com ...
, that is, that can factor a ''b''-bit number ''n'' in time O(''b''''k'') 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 and hence that the problem is not in class P. The problem is clearly in class NP, but it is generally suspected that it is not
NP-complete In computational complexity theory Computational complexity theory focuses on classifying computational problem In theoretical computer science An artistic representation of a Turing machine. Turing machines are used to model general computi ...
, though this has not been proven. There are published algorithms that are faster than O((1 + ''ε'')''b'') for all positive ''ε'', that is, sub-exponential. As of 2021-03-12, the algorithm with best theoretical asymptotic running time is the general number field sieve ( GNFS), first published in 1993, running on a ''b''-bit number ''n'' in time: :\exp\left( \left(\sqrt + o(1)\right)(\ln n)^(\ln \ln n)^\right). For current computers, GNFS is the best published algorithm for large ''n'' (more than about 400 bits). For a
quantum computer Quantum computing is a type of computation Computation is any type of that includes both al and non-arithmetical steps and which follows a well-defined model (e.g. an ). Mechanical or electronic devices (or, , people) that perform computatio ...
, however,
Peter Shor Peter Williston Shor (born August 14, 1959) is an American professor of applied mathematics Applied mathematics is the application of mathematical methods by different fields such as physics Physics (from grc, φυσική (ἐπισ ...
discovered an algorithm in 1994 that solves it in polynomial time. This will have significant implications for cryptography if quantum computation becomes scalable.
Shor's algorithm Shor's algorithm is a polynomial-time quantum algorithm, quantum computer algorithm for integer factorization. Informally, it solves the following problem: Given an integer N , find its prime factors. It was discovered in 1994 by the American mat ...

Shor's algorithm
takes only time and O(''b'') space on ''b''-bit number inputs. In 2001, Shor's algorithm was implemented for the first time, by using
NMR Nuclear magnetic resonance (NMR) is a physical phenomenon A phenomenon (; plural phenomena) is an observable In physics Physics (from grc, φυσική (ἐπιστήμη), physikḗ (epistḗmē), knowledge of nature, from ...
techniques on molecules that provide 7 qubits. It is not known exactly which
complexity class Complexity characterises the behaviour of a system or model (disambiguation), model whose components interaction, interact in multiple ways and follow local rules, meaning there is no reasonable higher instruction to define the various possible i ...
es contain the decision version of the integer factorization problem (that is: does have a factor smaller than ?). It is known to be in both NP and
co-NP In computational complexity theory Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. ...
, meaning that both "yes" and "no" answers can be verified in polynomial time. An answer of "yes" can be certified by exhibiting a factorization with . An answer of "no" can be certified by exhibiting the factorization of ''n'' into distinct primes, all larger than ''k''; one can verify their primality using the
AKS primality test The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic Determinism is the Philosophy, philosophical view that all events are determined completely by previously existing causes ...
, and then multiply them to obtain ''n''. The
fundamental theorem of arithmetic In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "wh ...
guarantees that there is only one possible string of increasing primes that will be accepted, which shows that the problem is in both UP and co-UP. It is known to be in
BQP In computational complexity theory Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. ...
because of Shor's algorithm. The problem is suspected to be outside all three of the complexity classes P, NP-complete, and
co-NP-complete In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP In computational complexity theory Computational complexity theory focuses on classifying computational problem In theoretical ...
. It is therefore a candidate for the
NP-intermediate In Computational complexity theory, computational complexity, problems that are in the complexity class NP (complexity), NP but are neither in the class P (complexity), P nor NP-complete are called NP-intermediate, and the class of such problems i ...
complexity class. If it could be proved to be either NP-complete or co-NP-complete, this would imply NP = co-NP, a very surprising result, and therefore integer factorization is widely suspected to be outside both these classes. Many people have tried to find classical polynomial-time algorithms for it and failed, and therefore it is widely suspected to be outside P. In contrast, the decision problem "Is ''n'' a composite number?" (or equivalently: "Is ''n'' a prime number?") appears to be much easier than the problem of specifying factors of ''n''. The composite/prime problem can be solved in polynomial time (in the number ''b'' of digits of ''n'') with the
AKS primality test The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic Determinism is the Philosophy, philosophical view that all events are determined completely by previously existing causes ...
. In addition, there are several
probabilistic algorithm A ''randomized algorithm'' is an algorithm of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers ''a'' and ''b'' in locations named A and B. The algorithm proceeds by successive subtractions in ...
s that can test primality very quickly in practice if one is willing to accept a vanishingly small possibility of error. The ease of
primality test A primality test is an algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specification ...
ing is a crucial part of the RSA algorithm, as it is necessary to find large prime numbers to start with.


Factoring algorithms


Special-purpose

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. The parameters which determine the running time vary among algorithms. An important subclass of special-purpose factoring algorithms is the ''Category 1'' or ''First Category'' algorithms, whose running time depends on the size of smallest prime factor. Given an integer of unknown form, these methods are usually applied before general-purpose methods to remove small factors. For example, naive
trial division Trial division is the most laborious but easiest to understand of the integer factorization algorithms. 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 th ...

trial division
is a Category 1 algorithm. *
Trial division Trial division is the most laborious but easiest to understand of the integer factorization algorithms. 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 th ...

Trial division
*
Wheel factorization Wheel factorization is an improvement of the trial division method for integer factorization. The trial division method consists of dividing the number to be factorized successively by the first integers (2, 3, 4, 5, ...) until finding a divisor. ...
*
Pollard's rho algorithm Pollard's rho algorithm is an algorithm of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers ''a'' and ''b'' in locations named A and B. The algorithm proceeds by successive subtractions in two ...
* Algebraic-group factorisation algorithms, among which are Pollard's ''p'' − 1 algorithm, Williams' ''p'' + 1 algorithm, and
Lenstra elliptic curve factorization The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose computer, general-purpose fa ...
* Fermat's factorization method *
Euler's factorization methodEuler Leonhard Euler ( ; ; 15 April 170718 September 1783) was a Swiss mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topi ...
*
Special number field sieve In number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number the ...


General-purpose

A general-purpose factoring algorithm, also known as a ''Category 2'', ''Second Category'', or ''Kraitchik'' ''family'' algorithm, has a running time which depends solely on the size of the integer to be factored. This is the type of algorithm used to factor
RSA number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...
s. Most general-purpose factoring algorithms are based on the
congruence of squares In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms. Derivation Given a positive integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "whole") is colloquially def ...
method. * Dixon's algorithm *
Continued fraction factorizationIn number theory, the continued fraction factorization method (CFRAC) is an integer factorization algorithm of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers ''a'' and ''b'' in locations nam ...
(CFRAC) *
Quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considera ...
* Rational sieve *
General number field sieve In number theory, the general number field sieve (GNFS) is the most algorithmic efficiency, efficient classical algorithm known for integer factorization, factoring integers larger than . Heuristically, its Computational complexity theory, complexi ...
* Shanks's square forms factorization (SQUFOF)


Other notable algorithms

*
Shor's algorithm Shor's algorithm is a polynomial-time quantum algorithm, quantum computer algorithm for integer factorization. Informally, it solves the following problem: Given an integer N , find its prime factors. It was discovered in 1994 by the American mat ...

Shor's algorithm
, for quantum computers


Heuristic running time

In number theory, there are many integer factoring algorithms that heuristically have expected
running time In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of com ...
:L_n\left tfrac12,1+o(1)\righte^ in little-o and
L-notation''L''-notation is an asymptotic 250px, A curve intersecting an asymptote infinitely many times. In analytic geometry In classical mathematics, analytic geometry, also known as coordinate geometry or Cartesian geometry, is the study of geometry ...
. Some examples of those algorithms are the
elliptic curve method The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose computer, general-purpose fa ...
and the
quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considera ...
. Another such algorithm is the class group relations method proposed by Schnorr, Seysen, and Lenstra, which they proved only assuming the unproved Generalized Riemann Hypothesis (GRH).


Rigorous running time

The Schnorr–Seysen–Lenstra probabilistic algorithm has been rigorously proven by Lenstra and Pomerance to have expected running time L_n\left tfrac12,1+o(1)\right/math> by replacing the GRH assumption with the use of multipliers. The algorithm uses the
class group In number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number t ...
of positive binary
quadratic form In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...
s of
discriminant In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
Δ denoted by ''G''Δ. ''G''Δ is the set of triples of integers (''a'', ''b'', ''c'') in which those integers are relative prime.


Schnorr–Seysen–Lenstra Algorithm

Given an integer ''n'' that will be factored, where ''n'' is an odd positive integer greater than a certain constant. In this factoring algorithm the discriminant Δ is chosen as a multiple of ''n'', , where ''d'' is some positive multiplier. The algorithm expects that for one ''d'' there exist enough
smooth Smooth may refer to: Mathematics * Smooth function, a function that is infinitely differentiable; used in calculus and topology * Smooth manifold, a differentiable manifold for which all the transition maps are smooth functions * Smooth algebraic ...
forms in ''G''Δ. Lenstra and Pomerance show that the choice of ''d'' can be restricted to a small set to guarantee the smoothness result. Denote by ''P''Δ the set of all primes ''q'' with
Kronecker symbol In number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number ...
\left(\tfrac\right)=1. By constructing a set of generators of ''G''Δ and prime forms ''f''q of ''G''Δ with ''q'' in ''P''Δ a sequence of relations between the set of generators and ''f''q are produced. The size of ''q'' can be bounded by c_0(\log, \Delta, )^2 for some constant c_0. The relation that will be used is a relation between the product of powers that is equal to the
neutral element In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
of ''G''Δ. These relations will be used to construct a so-called ambiguous form of ''G''Δ, which is an element of ''G''Δ of order dividing 2. By calculating the corresponding factorization of Δ and by taking a , this ambiguous form provides the complete prime factorization of ''n''. This algorithm has these main steps: Let ''n'' be the number to be factored. # Let Δ be a negative integer with , where ''d'' is a multiplier and Δ is the negative discriminant of some quadratic form. # Take the ''t'' first primes p_1=2,p_2=3,p_3=5, \dots ,p_t, for some t\in. # Let f_q be a random prime form of ''G''Δ with \left(\tfrac\right)=1. # Find a generating set ''X'' of ''G''Δ # Collect a sequence of relations between set ''X'' and satisfying: \left(\prod_ x^\right).\left(\prod_ f^_\right) = 1 # Construct an ambiguous form that is an element ''f'' ∈ ''G''Δ of order dividing 2 to obtain a coprime factorization of the largest odd divisor of Δ in which \Delta = -4ac \text a(a - 4c) \text (b - 2a)(b + 2a) # If the ambiguous form provides a factorization of ''n'' then stop, otherwise find another ambiguous form until the factorization of ''n'' is found. In order to prevent useless ambiguous forms from generating, build up the 2-Sylow group Sll2(Δ) of ''G''(Δ). To obtain an algorithm for factoring any positive integer, it is necessary to add a few steps to this algorithm such as trial division, and the Jacobi sum test.


Expected running time

The algorithm as stated is a
probabilistic algorithm A ''randomized algorithm'' is an algorithm of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers ''a'' and ''b'' in locations named A and B. The algorithm proceeds by successive subtractions in ...
as it makes random choices. Its expected running time is at most L_n\left tfrac12,1+o(1)\right/math>.


See also

* Bach's algorithm for generating random numbers with their factorizations *
Canonical representation of a positive integer In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "wh ...
*
Factorization In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

Factorization
*
Multiplicative partitionIn number theory, a multiplicative partition or unordered factorization of an integer ''n'' is a way of writing ''n'' as a product of integers greater than 1, treating two products as equivalent if they differ only in the ordering of the factors. Th ...
*
p-adic order In basic number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and num ...
*
Partition (number theory) In number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number ...
– a way of writing a number as a sum of positive integers.


Notes


References

* Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313. *
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist A computer scientist is a person who has acquired the knowledge of computer science Computer science deals with the theoretical foundations of information, ...
. ''
The Art of Computer Programming ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph A monograph is a specialist work of writing (in contrast to reference work A reference work is a work, such as a book A book is a medium for recording inf ...
'', Volume 2: ''Seminumerical Algorithms'', Third Edition. Addison-Wesley, 1997. . Section 4.5.4: Factoring into Primes, pp. 379–417. * . *


External links


msieve
- SIQS and NFS - has helped complete some of the largest public factorizations known *Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", ''Computing and Combinatorics"'', 2000, pp. 3–22

*
Manindra Agrawal Manindra Agrawal (born 20 May 1966) is a professor at the Department of Computer Science and Engineering and the Deputy Director at the Indian Institute of Technology, Kanpur. He was also the recipient of the first Infosys Prize for Mathematics ...
, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781-793 (2004)
August 2005 version PDF
* Eric W. Weisstein
“RSA-640 Factored” ''MathWorld Headline News'', November 8, 2005
{{Authority control Computational hardness assumptions Unsolved problems in computer science