139
edits
Changes
Jump to navigation
Jump to search
Line 25:
Line 25: − There is no effective algorithm for finding a certain integer's unique factorization, and finding the prime factors for large numbers can take considerable time (millions of years) even with the most advanced computers. This is referred to as the prime factorization problem, and it is believed to be NP-complete.+
→Unique Factorization: Was untrue as stated. Perhaps you need to define "effective" or just rephrase.
This means that every integer larger than 1, can be expressed as a product of one or more [[prime|primes]] in only one way. For example, 132 = 2 * 2 * 3 * 11. There is no other product of primes that equals 132.
This means that every integer larger than 1, can be expressed as a product of one or more [[prime|primes]] in only one way. For example, 132 = 2 * 2 * 3 * 11. There is no other product of primes that equals 132.
Finding the prime factors for large numbers can take considerable time (millions of years) even with the most advanced computers. This is referred to as the prime factorization problem, and it is believed to be NP-complete.
==Primality testing==
==Primality testing==