Actually, the fundamental theorem can easily be extended to all integers: every integer is either 0, a unit, or the product of a unit and n (not necessarily distinct) primes.
Off topic, but I’d recommend any good crypto book for pseudo-random number generators. In particular, “Handbook of Applied Cryptography” by Menezes, van Oorschot and Vanstone has several different algorithms with a discussion of their statistical properties. The more frequently cited “Applied Cryptography” by Schneier has at least one algorithm, but Menezes’ book has more depth. I don’t know what your particular needs are and it’s certainly instructive to design your own, but it’s unlikely you can do better (statistically speaking) than what’s available in the literature.
So if it werent’ for prime numbers, the only numbers we’d have would be zero and one.
Actually, that’s not true anymore. Within the last year it’s been shown that PRIMES (the primality testing problem) is in P.
As I said just before to ultrafilter: PRIMES is in P.
Prime numbers are useful in software for hash tables. Hashing is the conversion of keys (for example, people’s names) to numerical storage locations in a sort of pseudo-random pattern. Some types of hash tables work best if the number of available storage locations is prime.
Thanks, I will obtain the Menezes book. I used Random Number Generation and Monte Carlo Methods by James Gentle and The Art of Computer Programming Volume 2 Seminumerical Algorithms by Donald Knuth. But the motherlode was a collection of papers by George Marsaglia. I used his Multiply with Carry generator. But I needed a MWC that could be implemented in a portable Korn shell script using only ksh’s built-in arithmetic. And none existed until I wrote one.
My script allows the user to control the character set of each position of the generated password. I asked it for passwords from the set of hex numbers, 100 characters long. I generated a million of these. The resulting file is one of the formats accepted by Marsaglia’s Diehard test suite. It passed. There are a lot of random number generators that can’t do that, including most so-called true random number generators.
This isn’t as off topic as you think. None of this is possible without prime numbers. Either of those books or Marsaglia’s papers quickly show how crucial prime numbers are.
Hmm, maybe this is an acceptable place to ask a related question I’ve always wondered about, to wit:
Why are prime numbers mathematically interesting?
I mean, the basic concept—not divisible by any number except one and itself—seems pretty trivial and commonplace. But primes are the subject of so many of the most important and/or counterintuitive and/or difficult results in number theory. How did such a simple idea produce so much mathematical complexity?
Is it just because of the “fundamentality” that other posters have pointed out? Numbers are basically made of primes, therefore a lot of interesting statements about numbers can be expressed in terms of primeness?
And would that not be true if there were only a finite number of primes?
[mathematical wonder mode]
[/mwm]
A lot of the results about primes will carry over in any unique factorization domain. There, addition, subtraction, and multiplication work basically the same way as you’re used to in the integers.
I’d agree that it’s their fundamentality. Every area has their fundamental pieces which it builds off of and mathematics is no different. Primes get the attention because they’re the DNA of Math.
Simple example of a problem which is not in NP: List all of the numbers from 1 to 2[sup]n[/sup]. And, of course, impossible problems like Turing’s Halting Problem aren’t in NP, either.
Many places where primes show up in math, it’s a direct result of the Prime Factorization Theorem. Most places, the relationship to their unfactorability is at least somewhat obvious. But then there’s things like the Greater Goldbach Conjecture. This conjecture states that every even number greater than 2 is the sum of two (not necessarily distinct) primes. It’s been tested via computers up to very high numbers (all numbers up to 2*10[sup]17[/sup], at least), and though it’s never actually been proven, any mathematician would lay down money that it’s true. If it’s true, then there must be something about prime numbers that makes it so, and since the definition of prime numbers is based on the factorability (or rather, lack thereof), there must be some relationship between their unfactorability and the Goldbach property. But no mathematician knows what that pattern is.
I’ll avoid the full generality and just talk about primes in the integers.
Given any number n, we can break all integers up into collections, each identified by its remainder on division by n. For instance, 3 breaks the integers into
{…, -6, -3, 0, 3, 6, …}
{…, -5, -2, 1, 4, 7, …}
{…, -4, -1, 2, 5, 8, …}
Which have remainders 0, 1, and 2 respectively. We can add and multiply numbers as usual and throw away everything but the remainder after dividing by n. For instance, if n is 12 then 10 + 5 = 3 – it’s like adding hours on a clock.
Anyhow, if n is 12 then 2*6 = 0. The familiar “can’t multiply to get zero” doesn’t hold, and we say that 2 and 6 are “zero divisors”. The interesting thing about prime numbers is that there are no zero divisors if and only if n is prime.
I think complexity theorists try to phrase problems as “yes/no” questions, don’t they?
Thanks Math, I get your explanation of modular arithmetic/quotient groups in the integers, but I’m intrigued by your statement that “the” interesting thing about primes is that you get no zero divisors modulo a prime number. That somehow doesn’t intuitively sound to me like a big fundamental issue! Could you explain more about why that’s central to the “fundamentality” of primes?
(And again, how does the infinitude of primes tie in with this?)
Yes, but it’s easy enough to convert any problem into a decision problem. For Chronos’s example, the corresponding decision problem is given a list l of integers, confirm that l is a list of the integers from 1 to 2[sup]n[/sup] with no repetitions.
But that’s a polynomial time problem. Remember, when you’re considering the scaling of a problem, you have to consider the size of the input, and in the verification version of the problem, the input is huge. Verification of the list would be approximately linear in the total length of the list. If we’re going to require boolean output, then I don’t know of any examples offhand of problems not in NP, and I’m not sure there are any. I just used that example because it was the one used by the professor in an algorithms class, so at least one complexity theorist considers that a valid type of problem.
No it isn’t. Not even if you have the array as input.
Your “conversion” to yes/no most definitely makes it a poly time problem.
On another matter …
There are many examples of exponential time or higher decidable problems. Many questions about decidable logics are at least a single exponential. Charlie Rackoff has a whole book full of those. Many questions about regular expressions can get quite difficult quickly. Determining if a regular expression using complement represents the empty set isn’t even elementary (a fixed number of stacked exponents). (A mental flash on the Larry Stockmeyer I knew when he proved that. He was so young back then. Now he’s gone.)
For regular folk, here’s some examples: Take Chess, Checkers, or Go on an nxn board with extra pieces (but still only 1 king in Chess) positioned however you like. Does the player to go next have a force win? All of these are Exponential Time Complete. (These are "perfect information"games. Throw in hidden positions and you get even higher complexity.)
Special Plea to SDMB posters: The definitions of P, NP and NP-Complete are very precise and not the same as what people routinely post in threads such as these. Please, pretty please, look the definitions up first before posting. If you are not especially knowledgable about the definitions (e.g., you didn’t referee all 3 of the game result papers mentioned above!), don’t post your version or re-interpretation. Fight Ignorance, don’t spread it. A link will suffice, e.g.,
How so? If the input is n, then there are an exponential number of integers in [1, 2[sup]n[/sup]].