Prime numbers: dumb question

[allanb]

I'm interested in primes although I know almost nothing about them: I understand Euclid's proof that there is an infinite number of them, and that's the extent of my knowledge.

So here's the question. If the largest known prime is N, does that imply that all primes smaller than N are known, or can there be a prime smaller than N which hasn't yet been found?

[Firestone]

I don't think so.

Here (http://primes.utm.edu/primes/download.php) you can find a list af the largest known prime numbers. There is no reason I'm aware of to assume that we found all smaller primes.
(Although in theory it could be done of course.)

[Paul C. Anagnostopoulos]

Excellent question. I'd guess that there can be holes in the sequence, because primes are found using various algorithms that yield classes of primes. However, primes found using the sieve of Atkin (or whatever the current best sieve is) would not have gaps in the sequence.

~~ Paul

[DeviousB]

The 'largest primes' are usually Mersenne primes of the type "2n-1". Projects like GIMPS (http://www.mersenne.org/) search explicitly for these primes (for various complicated, but very good, reasons).

The current largest prime is 232,582,657-1 (9808358 digits long, discovered in September 2006) which beat the previous record of 230402457 (9152052 digits, found the previous December).

There are undoubtedly very many unknown primes between these two very large numbers.

[RecoveringYuppy]

One interesting fact about those Mersenee primes is that, in binary, they are a long string of nothing but ones.

232,582,657-1 (9808358 digits long, discovered in September 2006)

So that number has over 9 million apparently random digits when written in decimal, but in binary it is simply a string of 32,582,657 ones.

[Overman]

If you find the next largest prime number you win a lot of money...I can't remember who funds it...There are computers that just run that algorithm for over 10 years just to spit out that number.

[RecoveringYuppy]

The next prize is for a prime number with 10 million or more digits. I don't think it has to be a Mersenne prime, but it probably will be. The prize is by the Electronic Frontier Foundation. I think there are two more prizes beyond the 10 million digit landmark.

ETA: http://www.eff.org/awards/coop.php

[Big Al]

The hottest prime number topic at the moment is the Riemann Hypothesis. Last year, a team thought they'd cracked it, but that's in doubt now.

[Buckaroo]

The 'largest primes' are usually Mersenne primes of the type "2n-1". Projects like GIMPS (http://www.mersenne.org/) search explicitly for these primes (for various complicated, but very good, reasons).

The current largest prime is 232,582,657-1 (9808358 digits long, discovered in September 2006) which beat the previous record of 230402457 (9152052 digits, found the previous December).

There are undoubtedly very many unknown primes between these two very large numbers.

If it takes so long and is so difficult to find such large prime numbers, how does one confirm that they are indeed primes, and that some bug in your software hasn't produced an erroneous result? Seems like confirmation would take at least as long, if not longer. Or has the typical code for finding primes just been so well picked-through that this isn't a serious consideration?

[Dr Adequate]

So here's the question. If the largest known prime is N, does that imply that all primes smaller than N are known, or can there be a prime smaller than N which hasn't yet been found? There can be and there are: lots of them, in fact.

Because it takes so long to test a very large number for primality, people looking for very large primes pick out numbers which are particularly likely to be prime and test them for primality. It's known that these special numbers can't be all the primes there are (nor can they be all the primes there are above some sufficiently large number M). So yes, there are gaps in the list of known primes.

[DeviousB]

If it takes so long and is so difficult to find such large prime numbers, how does one confirm that they are indeed primes, and that some bug in your software hasn't produced an erroneous result? Seems like confirmation would take at least as long, if not longer. Or has the typical code for finding primes just been so well picked-through that this isn't a serious consideration?

They use the Lucas-Lehmer Test. (http://mathworld.wolfram.com/Lucas-LehmerTest.html)

[Dr Adequate]

To expand on my previous reply in a way that I think will answer Buckaroo's question as well, consider the following primality test (Lucas' test).

Let n > 1.

If for every prime factor q of n-1 there is an integer a such that:

an-1 = 1 (mod n)
a(n-1)/q ≠ 1 (mod n)

then n is prime.

So all you have to do is keep looking at integers less than n and test that it fits these conditions. Now, it has to fit these conditions for every prime factor q of n-1. So the smart thing to do, if you wish to use Lucas' test, is to choose n-1 to be a power of 2, because then it has only one prime factor (namely 2) which cuts down the time it takes to test that a candidate for a fits those conditions.

(Also, since there is only one value for q to test, there is less opportunity for a to fail the test relative to some q, so, intuitively, such numbers are more likely to be prime.)

---

Now Buckaroo will note that once we think we've found a candidate for a, thus proving n prime, all we have to do is two simple calculations to prove that this value of a does indeed meet the conditions.

The reason the program takes so long is that you have to find a suitable a. Checking that you've found it is simple.

For a bug in the software to give a "false positive", it would have to have something wrong in its routines for raising integers to integer powers modulo some integer, which is a really easy thing to do. If you had doubts about that, you could turn it over to someone with a completely different sort of supercomputer and ask them to check.

---

NB: The reason Mersenne numbers are popular for primality testing is that there are also tests which depend on the number of factors of n+1, where n is the number to be tested.

---

More information here. (http://primes.utm.edu/prove/prove3.html)

[Wavicle]

If it takes so long and is so difficult to find such large prime numbers, how does one confirm that they are indeed primes, and that some bug in your software hasn't produced an erroneous result? Seems like confirmation would take at least as long, if not longer. Or has the typical code for finding primes just been so well picked-through that this isn't a serious consideration?

To expand on what others have said, checking primality is an incredibly time consuming task. One reason Mersenne primes are preferred is that they are only extremely time consuming (extremely < incredible for sufficiently small values of extremely). In Mersenne primes you may notice that the exponent is also prime. The largest (currently) known Mersenne prime has an exponent of just over 32 million.

We know with certainty every prime number less than or equal to 2,000,000,009 (there are 98 million of them, and they're easy to find on the internet) so one would think that we could simply check all 98 million candidate Mersenne exponents and see which in fact produce Mersenne primes. The reality is that it takes years of computational resources to verify or reject primality. People searching for these things generally have vast amounts of very fast parallel computational power at their disposal and still take months to years to find a new Mersenne prime.

[Just thinking]

Is there any practical or beneficial use in finding such huge prime numbers? Obviously, it tests the computational speed and accuracy of some computers ... but beyond that?

[RecoveringYuppy]

Large Mersenne primes are very important to encryption.

[DavidS]

Large Mersenne primes are very important to encryption.

Large primes are very important to encryption. Bearing the Mersenne-nature is less important, and probably even undesirable for many such uses. So far we know of less than 32,582,657 Mersenne primes (per DeviousB). Cryptographers are fanatically paranoid and not afraid of a little brute force; they'd laugh at any algorithm that a measly thirty or forty million trials would defeat.

Large primes are important to many public-key ciphers because they're "easy" to defeat IF you can factor the number used for the public key. To use one of those ciphers "securely", you need to use a number that's "hard" for your attacker to factor. A number is harder to factor if all its factors are large, which is easiest to ensure if you pick a number that has only a few big factors, which is easiest to ensure if you pick the factors to be large prime numbers.

The bad news (or at least unsettling to my limited understanding) is that nobody's really proved that factoring large numbers is truly a "hard" problem (or at least hadn't when I read Schneier's "Applied Cryptography"). True, one can take comfort in the fact that brilliant mathematicians have been working on the problem for centuries and haven't come up with an algorithm that isn't "hard" (in the sense that the number of operations required grows rapidly with the size of the number), but nobody has (had?) proved that there couldn't be some magic-bullet algorithm that could factor any ten-thousand-digit number in a paltry few milion operations.

If anybody were to find such an algorithm, we'd have big problems. Ever see the movie "Sneakers?".

[RecoveringYuppy]

True, for many encryption applications the prime has to be large but not necessarily Mersenne. But don't most popular computer based encryption algorithms have to involve Mersenne primes to run in a practical amount of time? (To avoid translating the message in to some weird base rather than splitting the message along "word" boundaries)

[CapelDodger]

I lost much interest in number theory early on, but I'm dimly aware of types of prime, such as the Mersenne type. My interest is suddenly - and inexpicably - aroused in whether there's any proof that not all primes are of a type? Which is to say, that there are primes which have nothing in common with any other primes except their primeness?

If I'd discovered their existence I'd have called them primitive primes, but others might favour the term primal primes.

[DavidS]

True, for many encryption applications the prime has to be large but not necessarily Mersenne. But don't most popular computer based encryption algorithms have to involve Mersenne primes to run in a practical amount of time? (To avoid translating the message in to some weird base rather than splitting the message along "word" boundaries)

Not really. As I indicated above, an attacker who knew you were relying on the limited supply of known Mersenne primes would have a dramatically smaller search space to crack your key. That would make it one of the first things an attacker would try, and therefore a really, really bad idea for you.

There are primality tests that yield a "vanishingly small" probability of mistaking a non-prime number for a prime (Schneier's book lists a few, and if you're a US resident he used to send you a diskette with a few more for a couple dollars), so better than relying on Mersenne primes is a prime-generation method something like:

1. Generate a string of random bits as long as you want the prime number to be.

2. Set the high bit to guarantee the number is about as big as you want it to be, and the low bit to guarantee it's odd as primes bigger than two must be.

3. Try one or more primality tests (rigorous or probabilistic), as many as you need and are willing to compute for your required confidence level that your number is truly prime.

4. If your number fails, start over at step (1) to get a new number to try.

5. If your number passes the tests (3), consider it prime and carry on.

Most of the public-key algorithms don't actually require the keys to be primes or to have only two prime factors. That is, the encryption will still work if they're not, but the keys *might* be easier to factor to break the encryption. Factoring a 2kbit (or bigger) number is still pretty hard (with known algorithms), generally hard enough to make a brute-force attack unattractive. Using big primes to generate the keys just makes the factoring problem as hard as it can be, but it's almost always hard enough even if one of the numbers is more composite.

[andyandy]

dredging Simon Singh's code book up from my memory, i think it right to say that if quantum computers ever get built, then the whole primes as encryption tools will be blown apart....still, it's not likely anytime soon - and quantum encryption may be around by then anyway....so not to worry :)

[DavidS]

(To avoid translating the message in to some weird base rather than splitting the message along "word" boundaries)

The whole point of most public key ciphers is to translate the message to "some wierd base" and obscure "word" boundaries; you don't want to give the evil attacker any more clues than you must. Unless your key is as long as your message you're gonna have to split it somehow anyway. Actually, good cryptographic practice involves pre-encryption compression to both minimize encryption effort and (minimally) obscure (plaintext) "words".

Note the distinction between "ciphers" and "codes". A cipher translates an arbitrary plaintext data stream into a cyphertext data stream; any plaintext data can be enciphered. A code replaces plaintext symbols with corresponding ciphertext symbols; you can only encode plaintext symbols for which a ciphertext symbol has been defined -- that is, you can only encode words defined in your codebook. A cipher can be used as a code -- simply encipher the plaintext symbols to generate the "codebook" (ciphertext symbols) -- but a code might not be useful as a cipher.

I recommend Schneier's "Applied Cryptography" even if you're not of mathematical or computer-algorithm bent. The first half of the book isn't really about specific encryption algorithms anyway, it's more about protocols. It was enlightening (to me anyway) that even perfect unbreakable encryption won't save you if your protocols, including key generation and management, aren't sound. Getting them right can be a lot harder than you might naiively expect, and a bad protocol can actually cause worse problems than it solves.

[RecoveringYuppy]

Yes, I just did some reading and found only one encryption scheme (Fast Elliptic Encryption) depends on Mersenne primes.

[Cuddles]

dredging Simon Singh's code book up from my memory, i think it right to say that if quantum computers ever get built, then the whole primes as encryption tools will be blown apart....still, it's not likely anytime soon - and quantum encryption may be around by then anyway....so not to worry :)

This is often said, but isn't strictly true. The only thing that is important in cryptography is that it takes a much longer time to decode without a key than it does with. Quantum computers would allow people to break codes much faster, but at the same time they would also speed up all other parts of the encryption process, so in the end there would be no real change. What is important is the difference in speed between the processes, and this is only affected by the maths behind it, not the computer it's running on.

[RecoveringYuppy]

But it also depends on who can afford the fast computers.

[Jekyll]

This is often said, but isn't strictly true. The only thing that is important in cryptography is that it takes a much longer time to decode without a key than it does with. Quantum computers would allow people to break codes much faster, but at the same time they would also speed up all other parts of the encryption process, so in the end there would be no real change. What is important is the difference in speed between the processes, and this is only affected by the maths behind it, not the computer it's running on.

But quantum computers allow the solution of NP problems in polynomial time due to their non-deterministic nature. You would have to move to problems which are more than than NP hard solve in order to prevent easy decryption.

[rockoon]

We know with certainty every prime number less than or equal to 2,000,000,009 (there are 98 million of them, and they're easy to find on the internet)

I know with certainty every prime less than 17,179,869,184 .. and the only thing that keeps me from doing more is memory constraints (I only have 17179869184 bits of memory on board for the seive)

[Ben Tilly]

This is often said, but isn't strictly true. The only thing that is important in cryptography is that it takes a much longer time to decode without a key than it does with. Quantum computers would allow people to break codes much faster, but at the same time they would also speed up all other parts of the encryption process, so in the end there would be no real change. What is important is the difference in speed between the processes, and this is only affected by the maths behind it, not the computer it's running on.

Um, no. At least not by my understanding of quantum computers.

The trick with quantum computers is that, thanks to the joy of superpositions, they can carry on many operations in parallel. They do not allow any particular operation to go faster, they just allow multiple branches to execute at once.

Therefore quantum computers won't speed up encryption significantly. But they have the promise of being able to massively speed up factoring. Which means that they would render existing public key algorithms useless.

However quantum computers have two major drawbacks. The first is that a quantum computer cannot ever do an irreversible operation or else it loses the special properties that make it perform its magic. This makes them very hard to "program". The second constraint is that a working quantum computer with many parallel branches working requires tremendous precision in setting up and measuring the computation. The last I checked into this, the jury was out on whether we'd ever be able to scale them up to handle numbers of significant size. (Though we've gone farther than early doubters expected - several years ago a group at IBM factored 15 successfully using a quantum computer.)

However there is one fact I should mention involving quantum mechanics and encryption. And that is the idea of quantum cryptography. This is unrelated to usual mathematical notions of encryption and decryption. Instead it is a signal sent which, because of the special properties of quantum mechanics, we can tell has not been tapped. There is no ability to store information, it is only useful for direct transmission of data.

This bears no relationship to quantum computers or quantum computing. And it will become practical much faster - indeed it already is over short distances. (And there are already quantum cryptography devices that are commercially available.)

Cheers,
Ben

[Ben Tilly]

I know with certainty every prime less than 17,179,869,184 .. and the only thing that keeps me from doing more is memory constraints (I only have 17179869184 bits of memory on board for the seive)

You just have to be clever to improve that constraint. For instance you can just remember that 2 is prime and do a sieve on the odd numbers only. That will approximately double how much you can do. Also if you're willing to be a bit slower, you can keep the data for your sieve on disk. It will be slower, but it won't be as slow as you think. Particularly not if you reduce the number of passes over the sieve by sieving multiple primes on each pass. How many should you sieve? I'd personally aiming for sieving just as many in parallel as I can while still maxing out my hard drive data transfer speed. (Hopefully you can do that and keep most of the data on what you are doing in local cache to that part goes very fast.)

Cheers,
Ben

[Cuddles]

I've never really looked past the pop-science for quantum computers, so it's entirely possible I'm wrong. The part I don't understand is how is there a difference between performing multiple calculations simultaneously and simply performing them faster. For example, if I have 10 calculations to perform, a quantum computer will do them all at the same time and get the answer 10 times faster than a normal computer. However, if I get a normal computer that is 10 times faster it will also get the answer 10 times faster. As long as you have an encryption process that can benefit from the increased power of a quantum computer, the ratio of "encryption with key":"encryption without key" should stay the same. Obviously I must be missing something here, but what is it?

As for quantum cryptography, isn't that up to 50km now? Or maybe further since that was a few months ago.

[Jekyll]

I've never really looked past the pop-science for quantum computers, so it's entirely possible I'm wrong. The part I don't understand is how is there a difference between performing multiple calculations simultaneously and simply performing them faster. For example, if I have 10 calculations to perform, a quantum computer will do them all at the same time and get the answer 10 times faster than a normal computer. However, if I get a normal computer that is 10 times faster it will also get the answer 10 times faster. As long as you have an encryption process that can benefit from the increased power of a quantum computer, the ratio of "encryption with key":"encryption without key" should stay the same. Obviously I must be missing something here, but what is it?

You're missing the exponential growth.
If we allow a quantum bit (qbit) to hold two states simultaneously, then an operation that tries out all possible states on a single bit will be twice as fast on a quantum computer as on a normal computer (assuming everything else is equal).
A quantum computer will be 4 times as fast if the operation tries all states on 2 bits, 8 times as fast on an operation that tries all states on 3 bit, 16 times as fast for an operation that.....

Basically, for a very large class of problems including those relied upon by cryptographers, the harder the problem, the more significant the speed boost given to you by quantum computers.

[Cuddles]

But why does this mean the problem itself is changed from NP to P? The speed increase is exponential wrt the number of bits used, but doesn't that increase apply to both types of problem without actually changing their nature?

[Jekyll]

But why does this mean the problem itself is changed from NP to P? The speed increase is exponential wrt the number of bits used, but doesn't that increase apply to both types of problem without actually changing their nature?
Well no, because you don't have to calculate all possible keys when decoding, as you already know what the key is.
You can only get this exponential speed up if you can phrase the problem you're looking to solve as a search of some kind of space. So guessing someone else's key gets the speed up while just using the correct key doesn't.

At the moment, using the correct key is of polynomial difficulty so if you're worried that someone can crack your current security you can add an extra bit to your key size for a small cost to your processing time.

This extra bit would double the time it takes someone to search through possible keys as there are now twice as many possible keys, but not with quantum computing as you get that extra factor of two speed up from the extra Qbit you need to use.

So at the moment the amount of work people have to to crack a key is proportional to 2^(amount of work you do) with quantum computing it's proportional to the amount of work you do.

So you lose the ability to generate an unbreakable message in 10 minutes computing time as rather than taking 2^ hundred thosands of clock cycles to solve it just takes a few hundred thousands of clock cycles and can be done in a lunch break.

[sphenisc]

I lost much interest in number theory early on, but I'm dimly aware of types of prime, such as the Mersenne type. My interest is suddenly - and inexpicably - aroused in whether there's any proof that not all primes are of a type? Which is to say, that there are primes which have nothing in common with any other primes except their primeness?

If I'd discovered their existence I'd have called them primitive primes, but others might favour the term primal primes.

I think that there are degrees of having "nothing in common" with other primes, and that, on this scale, the prime primal prime will be 2.

[Art Vandelay]

I lost much interest in number theory early on, but I'm dimly aware of types of prime, such as the Mersenne type. My interest is suddenly - and inexpicably - aroused in whether there's any proof that not all primes are of a type? Which is to say, that there are primes which have nothing in common with any other primes except their primeness?First you would have to define what you mean by that. It's easy to find trivial examples. For instance, 7 is the only prime divisible by seven.

I've never really looked past the pop-science for quantum computers, so it's entirely possible I'm wrong. The part I don't understand is how is there a difference between performing multiple calculations simultaneously and simply performing them faster. For example, if I have 10 calculations to perform, a quantum computer will do them all at the same time and get the answer 10 times faster than a normal computer.The difference is between parallel and serial. If you need the result from the first calculation before you can start the second calculation, then you can't do them at the same time; you have to do them in series. Serial power can be traded for parallel power one-for-one; that it, a computer that can perform serial tasks twice as quickly can also perform parallel tasks twice quickly. When you go from parallel to serial, however, the trade is a logarithmic one; squaring the parallel speed only doubles the serial power. A quantum computer with 10 qbits would be able to perform a parallel process about 1000 times as quickly as a regular computer, but a serial process only about 10 times as quickly as a regular computer.

[Ben Tilly]

The difference is between parallel and serial. If you need the result from the first calculation before you can start the second calculation, then you can't do them at the same time; you have to do them in series. Serial power can be traded for parallel power one-for-one; that it, a computer that can perform serial tasks twice as quickly can also perform parallel tasks twice quickly. When you go from parallel to serial, however, the trade is a logarithmic one; squaring the parallel speed only doubles the serial power. A quantum computer with 10 qbits would be able to perform a parallel process about 1000 times as quickly as a regular computer, but a serial process only about 10 times as quickly as a regular computer.

Where do you get the figure that a quantum computer could do a serial process about 10 times as quickly as a regular computer? Figures like that should be highly dependent on the implementation of the physical computers, and we don't have enough experience in building quantum computers to say how fast we can get them to run. Let alone compare them with classical computers. (And, of course, the speed of classical computers keeps on changing.)

Presumably you get it from your assertion that going from parallel to serial gives a logarithmic tradeoff. You claim that squaring the parallel speed only doubles the serial power. I have no idea where this claim comes from, and it looks wrong. For instance suppose that I have a system with 4 CPUs and I try to run a serial process on it. It will use 1 CPU. Now let's "square the parallel power" which I presume means give it 16 CPUs. That same job will still use 1 CPU and will therefore run at exactly the same speed.

The moral is that a completely serial process does not benefit at all from opportunities to parallelize. Or as Brooks famously said, "It takes 9 months to make a baby, no matter how many women are put to the task."

Furthermore I should point out that parallelizing computations on a quantum computer is not as straightforward as one might hope. For instance I don't believe that you can simply choose, say, 10 different computations to do in parallel and do them. That's because you're always limited to putting in one set of data, performing your operations, then reading one set of data out. The magic lies in the fact that the computer goes into a superposition for the intermediate set of operations, so you may have a tremendous amount of parallelism at that step. But everything that comes up must be on the set of possible computational paths from the starting dataset to the finishing dataset.

So for certain computations, quantum computers will fly! And for others? Well there is a reason that people envision having quantum computers hooked up to classical ones.

Cheers,
Ben

[Art Vandelay]

Where do you get the figure that a quantum computer could do a serial process about 10 times as quickly as a regular computer? Figures like that should be highly dependent on the implementation of the physical computers, and we don't have enough experience in building quantum computers to say how fast we can get them to run.I should have been more clear on that. 10 is the upper bound; it would be unlikely that we could come close to that. For many processes, it would probably take millions of processors just to get a a few doublings in speed. The task at hand would be more of a factor than the implementation.

[rockoon]

Modern single-core processors ARE parallel computers. Its just 'behind the scenes' with multiple execution units, out of order processing, and so forth. The good old days of drawing simplified divisions between the two is gone.

Scaling the single-core processor up in this manner has diminishing returns due to 'dependency chains' in program flow. Operation X requires the result of operation Y, which requires the result of operation Z, and so forth.

Quantum computers, multi-processors, and multi-core designs? None of them will help the execution time of dependency chains and the algorithms that require them.

Factoring large numbers does not require long dependecy chains.. so quantum computers will rule on that front.

[Thabiguy]

But quantum computers allow the solution of NP problems in polynomial time due to their non-deterministic nature. You would have to move to problems which are more than than NP hard solve in order to prevent easy decryption.

This is not true and it is actually a common misconsception about quantum computers. It is not known that quantum computers can solve NP problems in polynomial time. In fact, it is suspected that they can not!

The class of problems that quantum computers can solve (in polynomial time) is called BQP, and it is generally suspected to be different from NP. Some NP problems (importantly, integer factorization and discrete logarithm problem) are known to be in BQP, but not all of them. In particular, no NP-complete problem is known to be solvable by a quantum computer in polynomial time.

It's good that people are interested in quantum computers, but I suggest that they do some research before jumping to incorrect conclusions.

[Ben Tilly]

Where do you get the figure that a quantum computer could do a serial process about 10 times as quickly as a regular computer? Figures like that should be highly dependent on the implementation of the physical computers, and we don't have enough experience in building quantum computers to say how fast we can get them to run.
I should have been more clear on that. 10 is the upper bound; it would be unlikely that we could come close to that. For many processes, it would probably take millions of processors just to get a a few doublings in speed. The task at hand would be more of a factor than the implementation.
Sorry, but you aren't making sense.

If I have a completely serial process, that is one where each step depends on the previous steps having happened, then how can adding extra processors improve my speed? (Unless the new processors are faster than existing ones.) I don't care whether you add 2 or 2 million processors, I'm going to execute A then B then C at the same rate.

[rockoon]

If I have a completely serial process, that is one where each step depends on the previous steps having happened, then how can adding extra processors improve my speed? (Unless the new processors are faster than existing ones.) I don't care whether you add 2 or 2 million processors, I'm going to execute A then B then C at the same rate.

hum

I imagine if step A has 10 possible outcomes, then 10 processors could work on step B while 1 processor is working on step A

Or if you only have say 2 processors, then while one processor is working on step A, the other could take a guess as to which output step A will emit, being right no worse than 10% of the time with a random guess.... would add a theoretical 10% or better performance boost if communication between processors was free or at least could be ammortized to approach free.

(I would argue that if you could make a better-than-random guess to feed into step B, then the entire process as a whole is probably not optimal and could do with some rearangement or a different strategy entirely)


1024 processors could evaluate 10 steps of an algorithm which leverages a binary decimation strategy such as a binary search .. so 1024 processors would offer a theoretical 10x improvement for such algorithms. But honestly you would make more effective use of all those processors by doing 1024 different binary searches in parallel (a 1024x improvement) so this is sort of a mental masturbation.

[Beerina]

The bad news (or at least unsettling to my limited understanding) is that nobody's really proved that factoring large numbers is truly a "hard" problem (or at least hadn't when I read Schneier's "Applied Cryptography").

And still haven't. It would be huge news. Indeed, studies have even been done on the catastrophic effects such a discovery would have as, for example, supposedly people could easily break into many secure things like airport flight controller systems, banks, etc. before they could be altered in favor of a different scheme. Humanity relies on this a ton for security.

[Jekyll]

This is not true and it is actually a common misconsception about quantum computers. It is not known that quantum computers can solve NP problems in polynomial time. In fact, it is suspected that they can not!

The class of problems that quantum computers can solve (in polynomial time) is called BQP, and it is generally suspected to be different from NP. Some NP problems (importantly, integer factorization and discrete logarithm problem) are known to be in BQP, but not all of them. In particular, no NP-complete problem is known to be solvable by a quantum computer in polynomial time.

It's good that people are interested in quantum computers, but I suggest that they do some research before jumping to incorrect conclusions.

Now that's interesting. Can you point me towards some work explaining where the difference between the classes comes from? It sounds very cool.

[Cuddles]

Thanks guys, that clears things up a bit.

On a slightly different subject, does anyone know what class the encryption in mobiles devices is? I can't remember what it is now, but I think it was based on conic sections or something like that. Obviously it's NP, but will it be breakable by quantum computers?

[Ben Tilly]

Thanks guys, that clears things up a bit.

On a slightly different subject, does anyone know what class the encryption in mobiles devices is? I can't remember what it is now, but I think it was based on conic sections or something like that. Obviously it's NP, but will it be breakable by quantum computers?

At a guess you are thinking of elliptic curve cryptography. Which isn't just for use in mobile devices however it may be more popular there than elsewhere. See http://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm for an overview on why elliptic curve cryptography is good. Skip to the bottom to the comment on patents to see why it isn't more popular.

I think that the patent problem is the clincher. Open source software authors are in no position to negotiate patent licenses, and that eliminates the use of the technique in open source. But open source software like Apache is critical for many commercial applications, and that shuts that encryption method out of use there. Therefore we are unlikely to see elliptic curve cryptography in use in protocols like https. By contrast the creators of mobile devices are in a position to negotiate patent licenses, and are desperate for performance improvements, so the various advantages of the technique will push them to use it.

In any case that encryption is based on the discrete logarithm problem which quantum computers can break in polynomial time. The algorithm was found by Peter Shor. (Yes, the same person who found the fast factoring algorithm. And the two even were published in the same paper, see http://www.arxiv.org/abs/quant-ph/9508027.)

Note that currently elliptic curve cryptography is harder to break than things like RSA, so people use smaller keys. Both kinds of cryptography can be broken in polynomial time on a quantum computer. This suggests to me that quantum computers will enable breaking practical elliptic curve cryptography before they are useful for the factorization problem.

Cheers,
Ben

[Ben Tilly]

hum

I imagine if step A has 10 possible outcomes, then 10 processors could work on step B while 1 processor is working on step A

Or if you only have say 2 processors, then while one processor is working on step A, the other could take a guess as to which output step A will emit, being right no worse than 10% of the time with a random guess.... would add a theoretical 10% or better performance boost if communication between processors was free or at least could be ammortized to approach free.

Unfortunately communication between processors is orders of magnitude slower than communication between a processor and local cache, which means that for one CPU to communicate to another CPU its exact state is inevitably worse than having the CPU just do the work itself.

(I would argue that if you could make a better-than-random guess to feed into step B, then the entire process as a whole is probably not optimal and could do with some rearangement or a different strategy entirely)

Actually real CPUs do this already.

The problem is that CPUs actually have a queue of instructions to execute (called a pipeline). It takes a certain number of cycles for an instruction to actually get through the CPU, and the CPU wants to have the pipeline full. Therefore CPUs play a number of tricks to keep the CPU full. (Putting instructions in out of order, etc.) One of those tricks is that if an "if" instruction is coming through, then the CPU will add instructions for one branch of that if statement to the pipeline. Then if the "if" executes the way the CPU hoped, the CPU saved time, and if not, the CPU lost nothing because those steps would have been empty.

In short this extracts some parallelism out of serial code and results in a modest speedup.

However there is a pretty severe limit to how much code can be sped up this way. Plus companies that care about efficiency (like Google) don't like this because it takes extra electric power for results that are often thrown away. Which is why Intel introduced "hyperthreading". There instead of trying to extract parallelism out of serial code, you have two pieces of serial code being pushed through the same CPU at the same time. Now it is far easier to keep the pipeline full - just interleave the instructions from two different jobs.

1024 processors could evaluate 10 steps of an algorithm which leverages a binary decimation strategy such as a binary search .. so 1024 processors would offer a theoretical 10x improvement for such algorithms. But honestly you would make more effective use of all those processors by doing 1024 different binary searches in parallel (a 1024x improvement) so this is sort of a mental masturbation.

My guess is that in general the cost of synchronizing those processors afterwards to find who got the right answer outweighs the performance gain from the parallel work. And you're absolutely right that having the CPUs do different things is far more efficient. (And that's the way the industry is headed. Though I'm waiting for operating systems to catch up to the fact that NUMA is the way to go rather than SMP...)

Cheers,
Ben

[Cuddles]

At a guess you are thinking of elliptic curve cryptography. Which isn't just for use in mobile devices however it may be more popular there than elsewhere. See http://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm for an overview on why elliptic curve cryptography is good. Skip to the bottom to the comment on patents to see why it isn't more popular.

That's the ones. It's mainly used in mobile devices because of the processing and bandwidth advantages. I didn't know about any patent issues though, I'd assumed that other applications just don't need to save any processing power so they were happy sticking with the more established prime business.

Interestingly (and more for people who don't know what we're talking about), elliptic curves have another problem similar to primes. If the Riemann hypothesis is solved, primes will be shown to be predictable and encryption based on them will no longer be safe. There is a different hypothesis in the maths behind elliptic curves that will have exactly the same effect on their encryption methods. Both of these hypotheses have had solutions presented, although so far there have been flaws in all of them. It is not all that unlikely that both methods of encryption will be rendered useless mathematically, no matter what kind of computers we are using.

[Tez]

If the Riemann hypothesis is solved, primes will be shown to be predictable and encryption based on them will no longer be safe.

So if I just happen to believe the Riemann hypothesis is true I can read all these messages?

Perhaps whatever method is used to prove the Riemann conjecture will also yield better factorization algorithms, but its not a given. And certainly there are no efficient factorisation algorithms which start with "Assume the Riemann conjecture is true. Here's how you factorise efficiently..." If so we'd have an efficient algorithm for all practical pusposes!

[boooeee]

And still haven't. It would be huge news. Indeed, studies have even been done on the catastrophic effects such a discovery would have as, for example, supposedly people could easily break into many secure things like airport flight controller systems, banks, etc. before they could be altered in favor of a different scheme. Humanity relies on this a ton for security.
Which makes me wonder that if somebody actually did discover an efficient factoring method, would it be publicized? There would be a LOT to gain by keeping a discovery like that secret. And you'd piss off a lot of very powerful people by going public with it.

I bet if the NSA got word of it, they would try their hardest to keep it under wraps. I think I've got a screenplay idea......

[Tez]

I bet if the NSA got word of it, they would try their hardest to keep it under wraps. I think I've got a screenplay idea......

The NSA funds a lot of quantum computing research. Of course they would do this to maintain the facade anyway...

There are actually public key cryptographic schemes for which it is believed that a quantum computer will not suffice (essentially the "shortest vector in a lattice" schemes.) Here is another recent interesting idea: http://arxiv.org/abs/quant-ph/0701115

Its also been examined whether a hidden variable model underlying quantum mechanics would give more powerful computation - the answer is "somewhat, but not dramatically so". (e.g. It would solve the shortest vector in a lattice thingy but not NP complete problems).

Finally, we could resort to quantum cryptography. There have, in fact, been proposals of protocols that are secure even given theories stronger than quantum mechanics! The paper http://arxiv.org/abs/quant-ph/0405101 gives a method for security in any theory that doesnt allow faster than light signalling for instance.

[Ben Tilly]

Interestingly (and more for people who don't know what we're talking about), elliptic curves have another problem similar to primes. If the Riemann hypothesis is solved, primes will be shown to be predictable and encryption based on them will no longer be safe. There is a different hypothesis in the maths behind elliptic curves that will have exactly the same effect on their encryption methods. Both of these hypotheses have had solutions presented, although so far there have been flaws in all of them. It is not all that unlikely that both methods of encryption will be rendered useless mathematically, no matter what kind of computers we are using.

Sorry, but this really sounds like you mixed something up. I'd want to see references before I believed that the Riemann hypothesis implies a fast factoring algorithm. That claim is one that would astonish me.

The Riemann hypothesis does not imply that individual primes are predictable, only that their overall frequency is. Specifically the hypothesis is equivalent to saying that a certain version of the prime number theorem is accurate to within C*sqrt(n)*log(n) for a known constant C. However it is known that this bound is accurate to some absurdly large number (certainly larger than numbers we actually use for encryption.) Furthermore the first ten trillion non-trivial zeros of the Riemann zeta function are known to be 0 (see http://numbers.computation.free.fr/Constants/Miscellaneous/zetazeroscompute.html) which is enough for any practical purpose that I'm aware of.

Therefore you see that the Riemann hypothesis says nothing useful about factoring individual numbers. And should, by some miracle, someone manage to find a connection, then the hypothesis is "close enough to true" that I'd expect someone to be able to create a factoring algorithm that would be effective for all numbers currently used in encryption.

Cheers,
Ben

[Ben Tilly]

Which makes me wonder that if somebody actually did discover an efficient factoring method, would it be publicized? There would be a LOT to gain by keeping a discovery like that secret. And you'd piss off a lot of very powerful people by going public with it.

I bet if the NSA got word of it, they would try their hardest to keep it under wraps. I think I've got a screenplay idea......

While it is always possible that the NSA has such a method, outside estimates by cryptographers indicate that the NSA has significantly less in the way of resources to devote to this type of research than the general mathematical community. It would therefore be surprising if they were significantly ahead of the general community.

Similarly there is no way that the NSA can fund enough research into computer technology to significantly outperform commodity CPUs.

This is why cryptographers feel that it is safe to estimate the NSA's capabilities by assuming that they are limited to publically known techniques implemented on a system built out of commodity hardware with a very large (but fundamentally limited) budget.

Cheers,
Ben

[Ashles]

One interesting fact about those Mersenee primes is that, in binary, they are a long string of nothing but ones.

Surely that isn't correct?

1 = 1
2 = 10
3 = 11
5 = 101
7 = 111
13 = 1101
17 = 10001

etc.

Am I missing something? Is it Mersenne primes over a certain value?

[RecoveringYuppy]

2, 5, 13 and 17 aren't Mersenne primes because they aren't all ones in binary. Mersenne primes are those primes that are all ones in binary.

[Ashles]

2, 5, 13 and 17 aren't Mersenne primes because they aren't all ones in binary. Mersenne primes are those primes that are all ones in binary.
Every link I look at seems to disagree with you.

From Mersenne.org (http://www.mersenne.org/faq.htm#what)
A Mersenne prime is a prime number of the form 2P-1.

I am genuinely confused here. Are you serious? If so where are you getting that information from because I'm not seeing it, including on Wiki, Mersenne.org, primes.utm.edu etc...

[RecoveringYuppy]

Here's the link to Wikipedia's article on Mersenne primes:

http://en.wikipedia.org/wiki/Mersenne_prime

Search for the sentence near the top of the article containing the word "repunit".

[Ashles]

Here's the link to Wikipedia's article on Mersenne primes:

http://en.wikipedia.org/wiki/Mersenne_prime

Search for the sentence near the top of the article containing the word "repunit".
But it doesn't say that Mersenne primes are defined as only those which are repunits.
That page clearly includes 2, 3, 5, 13, 17 as Mersenne primes.

[RecoveringYuppy]

I don't see where you're getting that. Since 3, 6, 14, and 18 aren't powers of two the numbers 2, 5, 13, and 17 can't be Mersenne numbers of any kind.

BTW 3 is a Mersenne prime since it's prime and 4 is also a power of 2.

[RecoveringYuppy]

I may see your confusion. Note that the Mersenne primes are listed in column 3 of that table, not column 2. Column 2 is the exponent associated with the prime.

[Ashles]

I may see your confusion. Note that the Mersenne primes are listed in column 3 of that table, not column 2. Column 2 is the exponent associated with the prime.
Riiight, I just noticed that.

Apologies - I now see, and I have reread the other pages and see where I was missing a step.

Gotcha.

[boooeee]

Surely that isn't correct?

1 = 1
2 = 10
3 = 11
5 = 101
7 = 111
13 = 1101
17 = 10001

etc.

Am I missing something? Is it Mersenne primes over a certain value?

Never mind. Ashles figured it out without my help.

[RecoveringYuppy]

No problem. I did a real double take when I saw that table also.

[Tez]

To go back to the OP, a simple calculation I dont have time to do accurately is this. Say the largest known prime is 2^X-1. Then a typical number less than this is approx D decimal digits or B binary digits which requires K kilobytes to store.

The number of prime numbers between 2 and 2^X is (2^X)/X, (by the prime number theorem) so the memory required is approx (2^X)/X*K

I've no idea how large it is, but I'm guessing larger than the NSA can store...

[rockoon]

To go back to the OP, a simple calculation I dont have time to do accurately is this. Say the largest known prime is 2^X-1. Then a typical number less than this is approx D decimal digits or B binary digits which requires K kilobytes to store.

The number of prime numbers between 2 and 2^X is (2^X)/X, (by the prime number theorem) so the memory required is approx (2^X)/X*K

I've no idea how large it is, but I'm guessing larger than the NSA can store...

They wouldnt have to store the values themselves, only the delta between values:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

+1 +2 +2 +4 +2 +4 +2 +4 +6 ...

..hence they could iterate through them all fairly quickly, and also store them all fairly efficiently. If the average delta between primes is 'x', then ln(x) / ln(2) would be the average number of bits needed to store each delta. So we are talking about much less than 32-bit per prime.

Additionally, that is only storing them uncompressed. Clearly some values will appear a lot more often and could therefore be encoded in a lot fewer bits to attain additional significant space savings. Some compression algorithms are fairly efficient to impliment, such as predictor methods. Efficient enough to be used in realtime digital telecom.

[Thabiguy]

Now that's interesting. Can you point me towards some work explaining where the difference between the classes comes from? It sounds very cool.

Ooops! Sorry, Jekyll, I overlooked your reply, so this comes quite late.

The difference between BQP and NP is "by default"; it simply comes from the fact that they are class of problems solved by different machines. (Like P and NP.) If we find some way to relate problems or machines - for example, if we find a way to simulate one machine with the other - we can make conclusions about relationship of the classes (like we can prove that P is a subset of NP). Or we may find that there's no way to relate the problems (like we can prove that PSPACE is not a subset of NL). Or we may suspect that there's no way to relate them but cannot prove that (like we suspect that NP is not a subset of P). With BQP and NP, we suspect that neither is a subset of the other but we have no proof. We don't know any way to polynomially simulate a non-deterministic Turing machine on a quantum computer or vice versa. We know that BQP is a superset of P and a subset of PSPACE, though.

As for a work explaining this, I think you would not appreciate scanned notes from my college classes. ;) There doesn't seem to be a single best source for this information; you may start with Wikipedia or just type something like "bqp quantum" into Google and you will find lots and lots of articles and references.

[phildonnia]

But why does this mean the problem itself is changed from NP to P? The speed increase is exponential wrt the number of bits used, but doesn't that increase apply to both types of problem without actually changing their nature?

The very definition of "NP" is: polynomial-time on a non-deterministic machine. The nature of the problem doesn't change from NP to P, but the amount of time it takes to solve it gets a lot better.

Consider factoring primes. All you have to do is test n for divisibility by each number less than n. Assuming you have a hillion-jillion processors working in parallel, you can verify primeness in as long as it takes to do a single division.