Wheel factorization: Efficient?

[CRGreathouse]

Originally Posted by 3.14159

Classic case of people making unrealistic predictions. Moore's law is a flawed fiction.

What's unrealistic? It said, in 2003, that you should use a 2048-bit key if you want data to remain secure until 2030. 1024 bits seems insufficient for that timescale: another NFS-type discovery in the factoring community would surely be enough to overturn it, and with 27 years that didn't seem implausible.

The guideline is *not* predicting when a keylength will be crackable, but rather a 'safe harbor' of when it should not be crackable.

[3.14159]

What's unrealistic? It said, in 2003, that you should use a 2048-bit key if you want data to remain secure until 2030. 1024 bits seems insufficient for that timescale: another NFS-type discovery in the factoring community would surely be enough to overturn it, and with 27 years that didn't seem implausible.

Persons making predictions. Just look at the RSA-2048. Another classic example of people making unrealistic predictions, and having unrealistic goals.

Random GFN prime: 6640¹⁰²⁴ + 1 (3914 digits) .. Proth + GFN prime: 286 * 186¹²⁸+1 (293 digits)

[retina]

Originally Posted by CRGreathouse

I guess it all depends on how long the data needs to stay secure and who you need to protect against. 768-bit keys could still be used, in a pinch, for data that goes stale fast. But if you need the data to be secure for years and think that the NSA wants it... 1024 is clearly inadequate.

But it doesn't depend upon how long you want to keep data secure. The OP said that a 1024 key "might be factored soon enough". So estimating the amount of effort required to do that is entirely appropriate. It doesn't require any additional qualification based upon what the key is protecting.

[kar_bon]

Originally Posted by 3.14159

Random GFN prime: 6640¹⁰²⁴ + 1 (3914 digits)

You know this page?

[3.14159]

You know this page?

You discouraged my search for GFNs. I'll search for Proth + GFNs instead.. Unless those are taken as well?

[kar_bon]

Originally Posted by 3.14159

You discouraged my search for GFNs.

No, I saved you a lot of senseless cycles!

[3.14159]

No, I saved you a lot of senseless cycles!

No, you discouraged my search completely, for any practical range and any practical exponent. I'll search Proth-GFNs instead. If there's a link for that, any search for GFN-related primes, I give up on entirely. All ranges from 2 to 65536 have been completed. Up to about three million.

Example of a Proth-GFN prime: 7296 * 1296⁵¹²+1

[CRGreathouse]

Originally Posted by retina

But it doesn't depend upon how long you want to keep data secure. The OP said that a 1024 key "might be factored soon enough". So estimating the amount of effort required to do that is entirely appropriate. It doesn't require any additional qualification based upon what the key is protecting.

I was pointing out the difference between factoring in the outside world and factoring in secret agencies like the NSA. They discovered differential cryptanalysis decades before its discovery in the outside world (<= 1970s vs. 1990s?); it's not implausible that they have a better factoring algorithm. Even if not, they surely have more hardware and better implementations than that used for academic factorizations.

[3.14159]

Searching for Proth-GFNs, exponent: 8192, base: 1296. Range of k: 2 to 70000. (This is about 25500 digits, by the way. I need a closer 2nd place.)

Based on that.. There are 5293 candidates.

Out of 69999 candidates: About 1 in 11 should be prime.

Wait, wait, wait: It's actually 1 in 58718. Only one number should be prime in this entire search. Well, the search shall continue on, in that case.

[CRGreathouse]

Using the approximation P(n is prime) = 1/(log (n) + 1) I get 1.19 expected primes. But adding in the effect of the small prime divisors of the numbers I get 3.97 expected primes instead:

l=8192*log(1296)+1;sum(k=2,70000,1/(l+log(k)))

stuff(n)={my(f=factor(6*n)[,1]);prod(i=1,#f,f[i]/(f[i]-1))};
l=8192*log(1296)+1;sum(k=2,70000,stuff(k)/(l+log(k)))

[3.14159]

Using the approximation P(n is prime) = 1/(log (n) + 1) I get 1.19 expected primes. But adding in the effect of the small prime divisors of the numbers I get 3.97 expected primes instead:

How did you get nearly 4, if the odds are 1 in 58720 ? As of this post, I've tested up to 2223 * 1296⁸¹⁹²+1