The biggest gaps between primes do indeed grow faster than the input size. I don’t know how close results like Cramer’s conjecture are to being proved, but that would suggest one can keep things polynomial.
Isn’t that known to be false? (I’m not sure)
For clarity: N can be tested for primality in P(log(N)) time. The next prime can be found in, at most, N*P(log(N)) time which is polynomial in N, but exponential in the number of bits of N.
This article may touch on your question. Apparently, for any constant c there are infinitely many prime gaps larger than c log n log log n log log log log n (log log log n)[sup]-2[/sup]
Paul Erdős offered a $10,000 prize to prove this, but had been dead 18 years when Ford–Green–Konyagin–Tao and, independently, James Maynard completed the proof. Wikipedia seems to be silent about the disposition of the $10,000.
Then it should be quite simple for you to provide a cite that shows a proof that a 64 bit computer can find new primes in polynomial time.
While you dislike the term Miller–Rabin due to your personal connections, Rabin did create the probabilistic version and if you want to be pedantic Miller was not the first to make the discovery.
Miller–Rabin primality test is potentially useful for encryption breaking because the GRH it uses ensures the existence of enough primes with certain properties. But it does not reduce the need to produce a pool of primes to test to break encryption which is what the OP was talking about.
Note as Miller-Rabin is unsuitable for encrypting data for two reasons.
[ol]
[li]The Miller only solution depends on a assumption that isn’t proven (GRH) but is deterministic.[/li][li]The probabilistic form Miller-Rabin finds strong pseudoprimes, which despite being named “strong” still open one to malicious attacks by someone passing you pseudoprimes.[/li][/ol]
Even if you use a linear prime finder like the following that requires O(√n/(log log n)[sup]2[/sup]) bits of space to run in linear time:
For a 1024 bit key, with simplified math you need. 2.5529116337158649e+152 bits or:
232185960495904955199734095212196794412133896546396616061488058408655268230310091139861586347561318906937577846710638035372117875923517177856.00 TB of ram.
The slower form saves some space, only needing:
594910947897768854095409740280336378396803810680285153367426951187486471974084023441406694248414911128545629749623437444160843795655531954176.00 TB of ram.
The thing you are ignoring is that 2^1024 is:
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216
When Miller-Rabin pseudoprimes has barely been proven past 64 bits.
One cannot ignore the space complexity and just focus on the time complexity.
Here is the python for you to see.
import mpmath
num = 2**1024
mpmath.sqrt(num/mpmath.log(mpmath.log(num))**2)
Even with bit packing etc… finding the primes gets expensive and while you can do better than brute force the time complexity does become exponential within practical computing limits.
Feel free to provide me with a cite that covers this, but as almost all of these prime factorization methods haven’t been proven even close to the typical lowest key sizes I haven’t found anything.
But in simple language, with crypto keys being large you can’t make assumptions based on the efficiency of algorithms that fit within memory. As SDMB doesn’t support math formatting I can’t offer the math to do so. But if this isn’t problematic, with the interest in crypto, you should be able to find me a paper that matches your claim.
Sorry had a bug in the above, it should be:
The cited linear time sieve that only needs O(√n/(log log n)[sup]2[/sup]) bits of space would require:
656721068651864933251365238901797777789346124834761924763964434238208264657067085515014255510306966202398431308722072940977738506407172374528 TB of ram.
For a 1024 bit key.
Perhaps you are mixing some things up? That linear prime finder finds all the primes from 1 to n; of course some space is needed if n is huge. But the problem we are considering is to start with some n and find one single prime greater than n.
Note: you specifically said finding the next higher prime above n “requires exponential runtime”. I know of nothing that proves this and is likely false. It’s really hard to find a cite for something that hasn’t apparently been proven. My searches all indicate it isn’t that hard.
If you know of a proof, give a citation to a paper. Keep in mind that for some reasons your posts are rambling and hard to follow. So please, give a link to where someone has a readable proof of what you are talking about.
Regarding Miller’s proof. He was a grad student at Berkely when Rabin came by for a visit. Miller gave a preliminary seminar presentation on his methods. Before he knew it Rabin came out with a paper giving Miller’s ideas.
Rabin did this. E.g. the proof that 2 way DFAs accept only regular languages. The journal Rabin published in went to so far as to list an earlier date on the bottom of the paper than the actual one for that issue. All the other papers had the correct date. This allowed Rabin to claim priority of the proof when others had gotten their paper published before his.
It’s like the prof says in Real Genius. “Never forget to check your references.”
You are going to have to search for papers on gaps between consecutive prime numbers, but most of this range hasn’t been worked on.
The Dope just doesn’t work for showing this type of math, as an example this is just unreadable.
G(x) ≥ f(x) log(x)log(log(x)log(log(log(x)))/(log(log(log(x))))[sup]2[/sup]
Cramér’s conjecture helps you out if you control the way that you generate random numbers for encrypting but for breaking ecryption the work load increases to the point of almost being brute force.
Here is a proof on Paul Erdős conjecture about Cramér’s conditional proof semi-related to the above task.
http://annals.math.princeton.edu/2016/183-3/p04
Here is a link to a site showing that even for trivial to generate sequences like Fermat numbers that this is non-trivial.
What probability to find a divisor for Fermat numbers?
The prime number theorem states the number of primes not exceeding x is asymptotic to x/log(x).
Then realize that those are the keys you have to test per number, thus O(n[sup]k[/sup]) if you don’t have enough memory for the linear methods mentioned above.
We can disagree about how sub-exponential is defined and if that is sub-exponential but it still ends up being brute force for crypto key sizes and algorithms that are safe to use. Using smooth numbers has to be avoided for security reasons as an example:
So you should be flipping this around, if you can trivialize this you will be famous. But there is a reason that smaller keys have been abandoned a long time ago, especially ones that would fit within practical memory for some of these linear time methods.
That is a nice result and the methods used to prove it are worthy of study by anyone interested in the subject, but it is not an exponential gap (and the conjecture is that there is no exponential gap, just (log x)[sup]2[/sup], i.e., quadratic)
For your “paranoid crypto”, some of the algorithms described here can prove a number is prime in a reasonable amount of time, if that is what you mean.
You have to keep trying numbers until you find one that is prime.
You are missing the difficulty in breaking encryption, not randomly finding a convenient set of random numbers. When you are encrypting something you only care that you and your intended recipient agree and that neither of you picks a pseudorandom numbers.
When you are breaking encryption you can’t just randomly skip prime encryption values that some of these faster methods that are useful for encrypting data.
Yes. (so?)
I never claimed to describe a method of fast or polynomial integer factorization that is useful for breaking encryption.
[raises hand to ask a possibly stupid question]
Suppose I choose two large numbers I believe to be prime and inform my agent in the Kremlin of their product. He starts sending me messages and I decode them.
But, unbeknownst to me, one of the two ‘primes’ I chose was just a pseudoprime: it was itself the product of two largish primes. Since it’s almost a prime does the encryption/decryption almost work? Assuming small message blocks are coded independently, should I expect 99% of them to be garbled? Only 1% garbled? Something in between?
Encryption works fine. It doesn’t even need the numbers to be primes. What you have is a vulnerable encryption. In principle it would be easier to crack your encryption. In practice using the product of two large primes rather than a huge prime is actually done.
I am still completely baffled by Rat Avatar’s jumping all over the place. Answering questions by discussing something else, etc.
But again I just want to get down the the “requires exponential time” claim.
After all, good old RSA in their original paper give a way to find large primes: Randomly generate a 100* digit odd number and test it. Keep going. Won’t take long to find one. (Page 9)
A. Why would sequential searching take horribly much longer?
B. And that still doesn’t address the claim there’s a proof that it does?
- Ah, the good old days when 200 digit RSA keys were fine.
The entire point it is used in encryption is that there is an easy way to generate something that is hard to reverse.
Proving that some symmetries or algebraic structures connected to prime numbers would change this story. While it is often said that proving the Riemann Hypothesis would cause this really proving it was false would point to the distribution of primes having more structure than we expect.
The reason I have been insistent that these solutions we have with small numbers doesn’t apply in this thread is due to the last paragraph in the OP.
These linear factoring methods fall down when you have more possible numbers than the number elementary particles of matter exist in the visible universe (roughly 10[sup]86[/sup]).
This is why you use two 1024-bit factors which are > 2[sup]1023.5[/sup] as recommended in FIPS 186-4.
The computational cost is the primary reason for this. While there is always a prime between “n and 2n” as mentioned before, finding the same primes one someone else used is the expensive part.
Perhaps the reason you are confused about my replies is because you aren’t focusing on the question the OP had. As you just stated low bit sized modulus are useless so why offer methods that only work at low bit sizes?
Let’s not call it linear, it’s exponential as a function of the magnitude of the number.
I’m confused too, since I can in fact generate big bit sized RSA moduli on an obsolete desktop computer using those methods and even rigorously check the factors for primality. Note I cannot factor your RSA modulus on the same computer using trial division, but who said we could?