Citizendia

"Prime decomposition" redirects here. For the prime decomposition theorem for 3-manifolds, see Prime decomposition (3-manifold). In Mathematics, the prime decomposition theorem for 3-manifolds states that every compact orientable 3-manifold is the Connected sum of a unique (up to

In number theory, integer factorization is the process of breaking down a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer. Number theory is the branch of Pure mathematics concerned with the properties of Numbers in general and Integers in particular as well as the wider classes A composite number is a positive Integer which has a positive Divisor other than one or itself In Mathematics, a divisor of an Integer n, also called a factor of n, is an integer which evenly divides n without

When the numbers are very large, no efficient integer factorization algorithm is publicly known; a recent effort which factored a 200-digit number (RSA-200) took eighteen months and used over half a century of computer time. In Mathematics, factorization ( also factorisation in British English) or factoring is the decomposition of an object (for In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation In Mathematics, the RSA numbers are a set of large Semiprimes (numbers with exactly two Prime factors that are part of the RSA Factoring Challenge The presumed difficulty of this problem is at the heart of certain algorithms in cryptography such as RSA. Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" In Cryptography, RSA is an Algorithm for Public-key cryptography. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their In Mathematics, an elliptic curve is a smooth, projective Algebraic curve of genus one on which there is a specified point O In Mathematics, algebraic number theory is a major branch of Number theory which studies the Algebraic structures related to Algebraic integers A quantum computer is a device for Computation that makes direct use of distinctively Quantum mechanical Phenomena, such as superposition

Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, i. In Mathematics, a semiprime (also called biprime or 2- Almost prime, or pq number) is a Natural number that is the product e. the product of two distinct prime numbers. In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1 When they are both large, randomly chosen, and about the same size (but not too close), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical.

Contents

Prime decomposition

By the fundamental theorem of arithmetic, every positive integer greater than one has a unique prime factorization. In Number theory, the fundamental theorem of arithmetic (or unique-prime-factorization theorem) states that every Natural number greater than 1 can be written However, the fundamental theorem of arithmetic gives no insight into how to obtain an integer's prime factorization; it only guarantees its existence.

Given an algorithm for integer factorization, one can factor any integer down to its constituent prime factors by repeated application of this algorithm. In Number theory, the prime factors of a positive Integer are the Prime numbers that divide into that integer exactly without leaving a remainder

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 is insecure. In Cryptography, RSA is an Algorithm for Public-key cryptography. Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key 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; if integer factorization is hard, then they are strong. The Rabin cryptosystem is an asymmetric Cryptographic technique whose security like that of RSA, is related to 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 A pseudorandom number generator ( PRNG) is an Algorithm for generating a sequence of numbers that approximates the properties of random numbers In contrast, it may turn out that there are attacks on the RSA problem more efficient than integer factorization, though none is currently published. In Cryptography, the RSA problem is the task of finding e th roots modulo a Composite number N whose factors

A similar hard problem with cryptographic applications is the discrete logarithm problem. In Mathematics, specifically in Abstract algebra and its applications discrete logarithms are group-theoretic analogues of ordinary Logarithms

Even in the absence of cryptographic systems based on its hardness, integer factorization also has many positive applications in algorithms. For example, once an integer n is placed in its prime factorization representation, it enables the rapid computation of multiplicative functions on n. Outside number theory the term multiplicative function is usually used for Completely multiplicative functions This article discusses number theoretic multiplicative It can also be used to save storage, since any multiset of prime numbers can be stored without loss of information as its product; this was exploited, for example, by the Arecibo message. In Mathematics, a multiset (or bag) is a generalization of a set. The Arecibo message was beamed via frequency modulated Radio waves into space at a ceremony to mark the remodeling of the Arecibo radio telescope

Current state of the art

See also: integer factorization records

A team at the German Federal Agency for Information Technology Security (BSI) holds the record for factorization of semiprimes in the series proposed by the RSA Factoring Challenge sponsored by RSA Security. Numbers of a general form The first very large distributed factorisation was RSA129 a challenge number described in the Scientific American article of 1977 which first popularised The Bundesamt für Sicherheit in der Informationstechnik (abbreviated BSI - in English Federal Office for Information Security) is the German government In Mathematics, a semiprime (also called biprime or 2- Almost prime, or pq number) is a Natural number that is the product The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18 1991 to encourage research into Computational number theory RSA The Security Division of EMC Corporation, is headquartered in Bedford Massachusetts, United States and maintains offices in Ireland, Israel On May 9, 2005, this team announced factorization of RSA-200, a 663-bit number (200 decimal digits), using the general number field sieve. Events 1457 BC - Battle of Megiddo (15th century BC between Thutmose III and a large Canaanite coalition under the King of Year 2005 ( MMV) was a Common year starting on Saturday (link displays full calendar of the Gregorian calendar. In Mathematics, the RSA numbers are a set of large Semiprimes (numbers with exactly two Prime factors that are part of the RSA Factoring Challenge In Mathematics, the general number field sieve (GNFS is the most efficient classical Algorithm known for factoring integers larger than 100

The same team later announced factorization of RSA-640, a smaller number containing 193 decimal digits (640 bits), on November 4, 2005. In Mathematics, the RSA numbers are a set of large Semiprimes (numbers with exactly two Prime factors that are part of the RSA Factoring Challenge Events 1333 - Flood of the Arno River, causing massive damage in Florence as recorded by the Florentine chronicler Giovanni Villani Year 2005 ( MMV) was a Common year starting on Saturday (link displays full calendar of the Gregorian calendar.

Both factorizations required several months of computer time using the combined power of 80 AMD Opteron CPUs. The Opteron is AMD 's X86 server processor line and was the first processor to implement the AMD64 Instruction set architecture (known

Difficulty and complexity

If a large, b-bit number is the product of two primes that are roughly the same size, then no algorithm has been published that can factor in polynomial time, i. A bit is a binary digit, taking a value of either 0 or 1 Binary digits are a basic unit of Information storage and communication In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation e. , that can factor it in time O(bk) for some constant k. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments There are published algorithms that are faster than O((1+ε)b) for all positive ε, i. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments e. , sub-exponential.

The best published asymptotic running time is for the general number field sieve (GNFS) algorithm, which, for a b-bit number n, is:

O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right).

For an ordinary computer, GNFS is the best published algorithm for large n (more than about 100 digits). In Mathematics, the general number field sieve (GNFS is the most efficient classical Algorithm known for factoring integers larger than 100 For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time. A quantum computer is a device for Computation that makes direct use of distinctively Quantum mechanical Phenomena, such as superposition Peter Williston Shor (born August 14, 1959) is an American theoretical computer scientist most famous for his work on Quantum computation This will have significant implications for cryptography if a large quantum computer is ever built. Shor's algorithm takes only O(b3) time and O(b) space on b-bit number inputs. Shor's algorithm, first introduced by mathematician Peter Shor, is a quantum Algorithm for Integer factorization. In 2001, the first 7-qubit quantum computer became the first to run Shor's algorithm. It factored the number 15.

When discussing what complexity classes the integer factorization problem falls into, it's necessary to distinguish two slightly different versions of the problem:

It is not known exactly which complexity classes contain the decision version of the integer factorization problem. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources It is known to be in both NP and co-NP. In Computational complexity theory, NP is one of the most fundamental Complexity classes The abbreviation NP refers to " N on-deterministic In Computational complexity theory, co-NP is a Complexity class. This is because both YES and NO answers can be trivially verified given the prime factors (we can verify their primality using the AKS primality test, and that their product is N by multiplication). The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving It is known to be in BQP because of Shor's algorithm. In Computational complexity theory BQP stands for " B ounded error Q uantum '''P'''olynomial time " Shor's algorithm, first introduced by mathematician Peter Shor, is a quantum Algorithm for Integer factorization. It is suspected to be outside of all three of the complexity classes P, NP-Complete, and co-NP-Complete. In Computational complexity theory, P, also known as PTIME or DTIME ( n O(1 is one of the most fundamental Complexity In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties In complexity theory, computational problems that are Co-NP-complete are those that are the hardest problems in Co-NP, in the sense that they are the ones most likely 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, and therefore integer factorization is widely suspected to be outside both of those 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 actually finding the factors of N. A composite number is a positive Integer which has a positive Divisor other than one or itself In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1 Specifically, the former can be solved in polynomial time (in the number n 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 primality-proving 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. A randomized algorithm or probabilistic algorithm is an Algorithm which employs a degree of randomness as part of its logic The ease of primality testing is a crucial part of the RSA algorithm, as it is necessary to find large prime numbers to start with. A primality test is an Algorithm for determining whether an input number is prime. In Cryptography, RSA is an Algorithm for Public-key cryptography.

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.

General-purpose

A general-purpose factoring algorithm's running time depends solely on the size of the integer to be factored. Trial division is the most laborious but easiest to understand of the Integer factorization algorithms Pollard's rho algorithm is a special-purpose Integer factorization Algorithm. Algebraic-group factorisation algorithms are algorithms for factoring an integer N by working in an Algebraic group defined modulo N Pollard's p &minus 1 algorithm is a number theoretic Integer factorization Algorithm, invented by John Pollard in 1974 In Computational number theory, Williams' p + 1 algorithm is an Integer factorization algorithm one of the family of Algebraic-group factorisation The Lenstra elliptic curve factorization or the elliptic curve factorization method ( ECM) is a fast sub- Exponential running time algorithm for Integer Fermat 's factorization method is based on the representation of an odd Integer as the Difference of two squares: N = a^2 - Euler's factorization method is a method of factorization based upon representing a positive integer N as the sum of two squares The special number field sieve (SNFS is a special-purpose Integer factorization algorithm This is the type of algorithm used to factor RSA numbers. In Mathematics, the RSA numbers are a set of large Semiprimes (numbers with exactly two Prime factors that are part of the RSA Factoring Challenge Most general-purpose factoring algorithms are based on the congruence of squares method. In Number theory, a congruence of squares is a congruence commonly used in Integer factorization algorithms

Other notable algorithms

External links

References

Dictionary

integer factorization

-noun

  1. prime factorization
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic