|
In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. When the numbers are very large, no efficient algorithm is known; a recent effort which factored a 200 digit number (RSA-200) took eighteen months and used over half a century of computer time. The supposed difficulty of this problem is at the heart of certain algorithms in cryptography such as RSA. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing. Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers. ...
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...
A composite number is a positive integer that can be factored as a product of two or more prime numbers. ...
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...
Flowcharts are often used to represent algorithms. ...
Wikinews has a news story related to this article: Two hundred digit number factored In mathematics, RSA-200 is one of the RSA numbers, large semiprimes that are part of the RSA Factoring Challenge. ...
Cryptography has had a long and colourful history. ...
In cryptography, RSA is an algorithm for public key encryption. ...
Mathematics is the study of quantity, structure, space and change. ...
Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate Categories: Computer science ...
In mathematics, elliptic curves are defined by certain cubic (the superscript exponent is three, a. ...
In mathematics, an algebraic number field (or simply number field) is a finite field extension of the rational numbers Q. That is, it is a field which contains Q and has finite dimension when considered as a vector space over Q. The study of algebraic number fields, and these days...
Molecule of alanine used in NMR implementation of error correction. ...
Prime decomposition
By the fundamental theorem of arithmetic, every integer has a unique prime factorization. Given an algorithm for integer factorization, one can factor any integer down to its constituent primes by repeated application of this algorithm. In mathematics, and in particular number theory, the fundamental theorem of arithmetic or unique factorization theorem is the statement that every positive integer greater than 1 can be written as a product of prime numbers in only one way. ...
Practical applications The hardness of this problem is at the heart of several important cryptographic systems. A fast integer factorization algorithm would mean that the RSA public-key algorithm was insecure. Some cryptographic systems, such as the Rabin public-key algorithm and the Blum Blum Shub pseudo-random number generator can make a stronger guarantee - any means of breaking them can be used to build a fast integer factorization algorithm, so if integer factorization is hard then they are strong. In contrast, it may turn out that there are attacks on the RSA problem more efficient than integer factorization, though none are currently known. In cryptography, RSA is an algorithm for public key encryption. ...
PKC, see PKC (disambiguation) Public-key cryptography is a form of modern cryptography which allows users to communicate securely without previously agreeing on a shared secret key. ...
The Rabin cryptosystem is an asymmetric cryptographic technique, which like RSA is based on the difficulty of factorization. ...
Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986). ...
A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ...
In cryptography, the RSA problem is the task of finding eth roots modulo a composite number N whose factors are not known. ...
A similar hard problem with cryptographic applications is the discrete logarithm problem. In abstract algebra and its applications, the discrete logarithms are defined in group theory in analogy to ordinary logarithms. ...
Current state of the art As of 2005, the largest semiprime factored using general-purpose methods as part of public research is RSA-200, which is 663 bits long. This was done using a network of computers running in parallel between Christmas 2003 and May 2005, and used very approximately 75 years total computer time. The method used was the general number field sieve. 2005 is a common year starting on Saturday of the Gregorian calendar and is the current year. ...
In mathematics, a semiprime (also called biprime or 2-almost prime) is a natural number that is the product of two (not necessarily distinct) prime numbers. ...
Wikinews has a news story related to this article: Two hundred digit number factored In mathematics, RSA-200 is one of the RSA numbers, large semiprimes that are part of the RSA Factoring Challenge. ...
2003 is a common year starting on Wednesday of the Gregorian calendar. ...
2005 is a common year starting on Saturday of the Gregorian calendar and is the current year. ...
In mathematics, the general number field sieve is the most efficient algorithm known for factoring integers. ...
Difficulty and complexity If a large, n-bit number is the product of two primes that are roughly the same size, then no algorithm is known that can factor in polynomial time. That means there is no known algorithm that can factor it in time O(nk) for any constant k. There are algorithms, however, that are faster than Θ(en). In other words, the best known algorithms are sub-exponential, but super-polynomial. In particular, the best known asymptotic running time is for the general number field sieve (GNFS) algorithm, which is: A bit (abbreviated b) is the most basic information unit used in computing and information theory. ...
Flowcharts are often used to represent algorithms. ...
The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...
The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...
In mathematics, the general number field sieve is the most efficient algorithm known for factoring integers. ...
For an ordinary computer, GNFS is the best known algorithm for large n. For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time. This will have significant implications for cryptography if a large quantum computer is ever built. Shor's algorithm takes only O(n3) time and O(n) space. Forms of the algorithm are known that use only about 2n qubits. In 2001, the first 7-qubit quantum computer became the first to run Shor's algorithm. It factored the number 15. Molecule of alanine used in NMR implementation of error correction. ...
Peter Shor (born August 14, 1959) is an American theoretical computer scientist most famous for his work on quantum computation, in particular for devising a quantum algorithm for factoring exponentially faster than the best currently-known algorithm running on a classical computer (see Shors algorithm). ...
In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...
Shors algorithm is a quantum algorithm for factoring a number N in O((log N)3) time and O(log N) space, named after Peter Shor. ...
It is not known exactly which complexity classes contain the integer factorization problem. The decision-problem form of it ("does N have a factor less than M?") is known to be in both NP and co-NP. This is because both YES and NO answers can be checked if given the prime factors along with their primality proofs. It is known to be in BQP because of Shor's algorithm. It is suspected to be outside of all three of the complexity classes P, NP-Complete, and co-NP-Complete. If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, therefore integer factorization is widely suspected to be outside both of those classes. Many people have tried to find polynomial-time algorithms for it and failed, therefore it is widely suspected to be outside P. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ...
In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ...
In the complexity theory, co-NP is the complexity class that contains the complements of decision problems in the complexity class NP. The complement of a decision problem is here defined as the problem with the yes and no answers reversed, or if we define decision problems as sets of...
BQP, in computational complexity theory, stands for Bounded error, Quantum, Polynomial time. It denotes the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances. ...
Shors algorithm is a quantum algorithm for factoring a number N in O((log N)3) time and O(log N) space, named after Peter Shor. ...
In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ...
In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
In complexity theory, the complexity class Co-NP-complete is the set of problems that are the hardest problems in Co-NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve a Co-NP-complete problem...
Interestingly, the decision problem "is N a composite number?" (or equivalently: "is N a prime number?") appears to be much easier than the problem of actually finding the factors of N. Specifically, the former can be solved in polynomial time (in the number n of digits of N), according to a recent preprint given in the references, below. In addition, there are a number of probabilistic algorithms that can test primality very quickly if one is willing to accept the small possibility of error. The easiness of primality testing is a crucial part of the RSA algorithm, as it is necessary to find large prime numbers to start with. A composite number is a positive integer that can be factored as a product of two or more prime numbers. ...
In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. ...
A randomized algorithm is an algorithm which is allowed to flip a truly random coin. ...
A primality test is an algorithm for determining whether an input number is prime. ...
In cryptography, RSA is an algorithm for public key encryption. ...
Factoring algorithms
Special-purpose A special-purpose factoring algorithm's running time depends on the properties of its unknown factors: size, special form, etc. Exactly what the running time depends on varies between algorithms. Trial division is the simplest and easiest to understand of the integer factorization algorithms. ...
Pollards rho algorithm is a special-purpose integer factorization algorithm. ...
Pollards p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. ...
An Integer factorization algorithm invented by H.C. Williams that works well if the number N to be factored contains one or more prime factors p such that p+1 is smooth, i. ...
The Lenstra elliptic curve factorization is a fast probabilistic algorithm for integer factorization which employs elliptic curves. ...
With Fermats factoring method, one tries to represent an odd integer as the difference of two squares: . That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N. Furthermore, each odd number has such a representation. ...
The special number field sieve (SNFS) is a special-purpose integer factorization algorithm. ...
Joness factoring-by-period-proxy algorithm is a number theoretic integer factorization algorithm, invented by R.C. Jones in 1964. ...
General-purpose A general-purpose factoring algorithm's running time depends solely on the size of the integer to be factored. This is the type of algorithm used to factor RSA numbers. Most general-purpose factoring algorithms are based on the congruence of squares method. The RSA numbers, listed by security company RSA Security, are certain large semiprime numbers (i. ...
In number theory, a congruence of squares modulo an integer n is an equality . Such a relationship carries information useful in trying to factor the integer n: finding a congruence of squares modulo n is something sought after in integer factorization. ...
In number theory, Dixons factorization method (also Dixons algorithm) is a general-purpose integer factorization algorithm. ...
In number theory, the continued fraction factorization method is an integer factorization algorithm. ...
The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known. ...
In mathematics, the general number field sieve is the most efficient algorithm known for factoring integers. ...
Other notable algorithms Shors algorithm is a quantum algorithm for factoring a number N in O((log N)3) time and O(log N) space, named after Peter Shor. ...
Molecule of alanine used in NMR implementation of error correction. ...
External links - Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics", 2000, pp.3-22. download
- Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002, http://www.cse.iitk.ac.in/news/primality.html
- The "PRIMES is in P" FAQ http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html
- ftp://ftp.computing.dcu.ie/pub/crypto/factor.exe is a public-domain integer factorization program for Windows. It claims to handle 80-digit numbers. See also the web site for MIRACL
- http://www.alpertron.com.ar/ECM.HTM is an integer factorization Java applet that uses the Elliptic Curve Method and the Self Initializing Quadratic Sieve.
- The RSA Challenge Numbers - a factoring challenge.
|
Feeds |
Contact