What’s the big deal in the math world regarding prime numbers. For example, the number 19 is divisible by whole numbers by only one and itself. Besides math geeks…who cares?
Is there any practical use of prime numbers?
Most modern encryption mechanisms are based on the difficulty of factoring the products of large prime numbers.
See the RSA algorithm.
“most modern encryption mechanisms” is a little strong, but there are a couple notable ones. Verifying that a large prime is in fact prime also serves as a good benchmark for a supercomputer.
Most modern encryption mechanisms are based on the difficulty of factoring the products of large prime numbers.
See the RSA algorithm.
Essentially, I generate two prime numbers. I multiply them together, and distribute their product to the world at large. When someone wants to send a message to me, they use the product to do something mathematical (see the link for more details) to their message.
When I receive their encrypted message, the only way I can retrieve the original message text is by knowing what the two primes were. Since there is no known way, other than brute force, of factoring large numbers into their prime factors, this encryption mechanism is considered safe.
There are a lot of situations where it’s helpful to know if a number is prime or can be factored, besides encryption.
It could be as simple as reducing fractions, or complex as celestial dynamics (orbital resonances) or population biology (there’s a reason you have seven-year and thirteen-year locusts – both prime numbers).
IMHO asking if prime numbers matter is like asking if vowels have a purpose or if starch is necessary in food. Prime numbers are simply a named part of the whole, they exist and have their uses.
I’m not criticizing the question, but I wanted to make sure that it was considered that they’re simply there whether they have a purpose or not - like the dongle on the back of the throat 
Primes are used in encryption as stated above, as well as some number theory if I recall… I don’t have any cites on that, but that’s also a math geek thing so it isn’t what you’re looking for.
If P != NP, prime factorization is known to be outside of P and the class of NP-complete problems, and if P = NP, there is a relatively fast algorithm for factorization. To be really secure, you’d want an encryption method that’s based on a problem known to be outside of NP.
posted by ronincyberpunk-
*IMHO asking if prime numbers matter is like asking if vowels have a purpose or if starch is necessary in food. *
I disagree. I know what purpose vowels serve (pronunciation), and I know that starch serves a purpose (carbohydrates/calories). My question was whether prime numbers are actually used for any purpose. Apparently they are.
Prime numbers are a SETI standard for sending/receiving detectable pulses using extrasolar radio signals as proof of sentient life in the universe.
Did you mean outside of NP-complete? I don’t think anything is outside of NP, NP is simply all problems that are not P. And why would you want it out of NP-complete? All NP complete algorithms are equally as strong and many years of research has not managed to crack them. Other NP algorithms on the other hand are simply classified as NP because nobody has managed to find a P time algorithm for them. They are potentially much easier to crack.
Prime factorization can be used to find the least common denominator of two or more numbers. You just find the prime factors and multiply them all together, using common factors only once. I can’t remember what the least common demoninator is used for, but I remember using it in high school. (You can use it in division of fractions, but there’s no advantage over just multiplying the two denominators together.) It’s also useful for reducing fractions. Prime factor both the numerator and denominator, scratch out any common factors, and multiple the factors together again. It’s useful having a program to prime factor numbers when you need to reduce large fractions.
This is not known; the current algorithms are outside of P, but there may be undiscovered polynomial factoring algorithms even if P != NP.
This is true, since factoring is in both NP and coNP.
I’m not sure that this is meaningful. All encryption algorithms are (trivially) in NP, since a brute-force search of the keyspace can trivially be performed nondeterministically in a time polynomial in the size of the key (NP algorithm: guess the key, then decode). You can still base the algorithm on a harder problem, which I guess gives you more confidence that there are no attacks on the underlying problem structure; but if P=NP then any compact-key algorithms are doomed anyway.
(For Shalmanese: NP is the class of algorithms which terminate in polynomial time on a nondeterministic computer: that is, algorithms which are allowed to make polynomially many correct guesses on their way to finding a solution. There are problems which are not in NP.)
Slight nitpick, but methods using RSA and other prime number-based encryption schemes generally use relative pseudoprime numbers, as finding prime numbers long enough to satisfy a large key is extremely difficult; however, a composite number that is comprised of prime factors that are extremely large (or, at least large enough not to be easily determined by any known method of factorization) is virtually as good as an actual prime of the same wordlength.
Prime numbers also have many characteristics that cause them to show up in natural phenomena; for instance, it is widely speculated that the evolutionary cause for the various species of cicada which emergy en masse in years numbered in intervals of prime numbers (7, 13, and 17) do so as an adaptation both to keep from overforaging (detrimental to both species) and to dodge predators that emerge on more numerically factorized alterations. (A species that emerges every 12 years, for instance, will be cycically prone to depletion by predators who emege on 2, 3, 4, and 6 year intervals, while those that emege on, say, a 13 year cycle, will only meet up with their relative attackers every 26, 39, 52, and 78 years, respectively.)
Relative primes or relatively prime fractions–two numbers that share no common factors other than one–are also very valuable in vibrations and signal theory, as such systems tend to avoid resonances that occur when you have evenly-factored quantities. Stable dynamic systems often tend to have numbers that are prime or relatively prime for this reason. In particle physics, prime numbers and relatively prime fractions figure strongly into how different particles interact with each other. And prime numbers figure heavily into computational information theory, aside from the previously stated applications with cryptography.
BTW, “primeness” is a universal property of specific integers, regardless of its representation or base. 101[sub]2[/sub] is just as prime as 5[sub]10[/sub], the fact of which you can convince yourself if you divide it by 10[sub]2[/sub] and 11[sub]2[/sub] (2[sub]10[/sub] and 3[sub]10[/sub], respectively).
So…eat your prime numbers. They’re good for you.
Stranger
What?
Yes, they do; for example the prime number 7 serves the purpose of stopping 6 and 8 from chafing against each other.
A prime number doesn’t do anything. That’s the beauty of it!
That is definitely not true .
NP is the set of all problems that can be verified in P time, once you have a possible answer. (Or ‘checked’ might be a better word.) There are a number of problems, extremely arcane ones, that have not yet been shown to be NP. (I’m not sure if anyone’s found a way of proving that a problem is decideable but not NP, or if any such problem could be used as an encryption basis. In fact, I would tend to think that the problems outside of NP would be on the infeasible side for encryption, since the task of using a solution would probably be about as difficult as verifying it.
(Note that in the case of number factorization, verification would be taken to mean verifying a particular factorization once you have proved that all of the numbers involved are prime, I think. Not sure - I never actually studied an NP-complete proof for number factorization or anything like that.)
There are even problems that are fundamentally uncomputable, though they’re generally complex and hinge on technicalities. (That means not computable in all possible cases… there are algorithms for most of these that will solve 99.9% of the subproblems but either return no answer or freeze on a critical subset. And I may have the technical term wrong… it’s been a LONG time since I studied computability theory.)
Prime numbers are to number theory as the elements are to chemistry.
Primes are what numbers are “made of,” in the sense that every whole number (greater than 1) is either a prime itself, or is made up of primes multiplied together in one particular way. (That is, for any number, there’s only one group of primes you can multiply together to get that number). Lots of other things you might want to know about a number (like what it’s divisible by) or the relationship between numbers depend on their prime factorizations.
To take your example, knowing that 19 is prime tells me[ul]
[li]I can’t divide 19 marbles equally among a group of people, unless there are 19 people in the group.[/li][li]I can’t arrange 19 chairs or cookies or whatever in a rectangular array (unless it’s a 19 by 1 rectangle).[/li][li]19 has no factors in common with any other number, unless that number is a multiple of 19. So a fraction with a 19 as either the numerator or the denominator can’t be reduced, unless the other part is a multiple of 19.[/li][li]If I’m trying to cut a cake or a pizza into 19 equal pieces, I can’t do it but first cutting it in halves or thirds or something and then further dividing those pieces.[/li][/ul]
Many more advanced facts (some of which, admittedly, only math geeks would care about) depend on whether the numbers involved are prime, or on what prime factors they have.
I suggest you read the following article and some of its links.
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
People have done a lot better than brute force for quite some time now. Note that the recent successes in the RSA challenge have used such methods. People are becoming less and less optimistic about RSA due to this and other breakthroughs.
Note that other crypto systems like those based on discrete logs and quadratic residues as Mathematically based on the special properties of primes.
In Computer Science primes are used in a lot of algorithms. Take hashing for example.
Asking “what are primes good for” is really a lot like asking “what are electrons good for.” You might not be aware of them but they’re all around and can be harnessed for all sorts of useful things.
I recently wrote a password generator. I couldn’t find a random number generator for it that meant all of my needs. So I had to write one. This involved finding some large primes that met certain conditions.
Precisely. Of course I thought of encryption applications, but to me, primes are important because of The Fundamental Theorem of Arithmetic that says that every positive integer (except 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes. Also called The Unique Factorization Theorem, this is not called a “fundamental theorem” for no reason.