Wheel factorization: Efficient?

[CRGreathouse]

Originally Posted by 3.14159

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

Because the odds aren't 1 in 58720, they vary from as good as 1 in 19173 for k = 5 to as poor as 1 in 50035 for k = 69984. (Actually, these are slightly high because of other primes I didn't include... if you work only mod 6, the expected number is 3.57.)

[xilman]

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.

Actually, it depends very much on how long you want to keep data secure. It also depends on the value of the data to you and to your opponents.

For instance, if I want to keep something secure from you until tomorrow a 512-bit key is easily adequate. If I want to keep it secure for twenty years from the likes of me, a 1024-bit key is probably inadequate.

"Soon enough" is very context-dependent.

Paul

[3.14159]

Because the odds aren't 1 in 58720, they vary from as good as 1 in 19173 for k = 5 to as poor as 1 in 50035 for k = 69984.

I made my estimate based on 1/log(x): So I simply did: 1/log(70000 * 1296⁸¹⁹² + 1), which was about 1 in 58720.

Also: Making a (nextSPRP(n)) function, to compare it to the (nextprime(n)) function.

[CRGreathouse]

Originally Posted by 3.14159

I made my estimate based on 1/log(x): So I simply did: 1/log(70000 * 1296⁸¹⁹² + 1), which was about 1 in 58720.

I used a more sophisticated estimate. I originally said around 4, but the truth is probably closer to 3.5; I'll need to check more carefully to get good results.

[3.14159]

Added a help option to the isSPRP test:
"A pseudoprimality test which employs trial division to 1000003, then performs a Miller-Rabin primality test using a random base between 1 and n, if b=x is omitted. If b=x is present, it will perform a Miller-Rabin test using base x."

[CRGreathouse]

Originally Posted by 3.14159

Added a help option to the isSPRP test:
"A pseudoprimality test which employs trial division to 1000003, then performs a Miller-Rabin primality test using a random base between 1 and n, if b=x is omitted. If b=x is present, it will perform a Miller-Rabin test using base x."

That refers to this code?

isSPRP(n,b=2) = {
forprime(p=2, nextprime(10^6),
if(n%p==0,return(p))
);
my(s=valuation(n-1,2),d=n>>s);
n = Mod(b, n)^d;
if (n == 1, return(n));
while(s--,
if (n == -1, return(n));
n = n^2;
);
n == -1
};

You should, at the least, explain what the return values mean in the help entry. Also, "then performs a Miller-Rabin primality test using a random base between 1 and n, if b=x is omitted" is false for the above code.

[3.14159]

You should, at the least, explain what the return values mean in the help entry. Also, "then performs a Miller-Rabin primality test using a random base between 1 and n, if b=x is omitted" is false for the above code.

As I posted earlier on, I changed it to (random(n)), which means it now uses random bases.

[axn]

Originally Posted by 3.14159

I made my estimate based on 1/log(x): So I simply did: 1/log(70000 * 1296⁸¹⁹² + 1), which was about 1 in 58720

Since you're only considering odd integers, you can immediately double that estimation. So 1 in 29000. Then consider the fact that no factor of 1296 can be a factor of the number. This rules out 3 as a factor. So you can multiply the probability estimate by another 1.5. So 1 in 20000. That should be "good enough for government purposes".

[3.14159]

Since you're only considering odd integers, you can immediately double that estimation. So 1 in 29000. Then consider the fact that no factor of 1296 can be a factor of the number. This rules out 3 as a factor. So you can multiply the probability estimate by another 1.5. So 1 in 20000. That should be "good enough for government purposes".

Well, that bumps the amount of primes I'll find to at most three or four. 1/58720 * 2 = 1/29360
1/29360 * 1.5 = 1/19573. Surprisingly, just as CRG guessed earlier on.

[CRGreathouse]

Originally Posted by 3.14159

As I posted earlier on, I changed it to (random(n)), which means it now uses random bases.

Ah. In that case "If b=x is present, it will perform a Miller-Rabin test using base x." is incorrect.

(Very minor point: you shouldn't really allow bases 0 or 1.)

[CRGreathouse]

Originally Posted by 3.14159

Well, that bumps the amount of primes I'll find to at most three or four. 1/58720 * 2 = 1/29360
1/29360 * 1.5 = 1/19573. Surprisingly, just as CRG guessed earlier on.

If you look at the code I posted, I take into account 2, 3, and up to four other primes. So it should be no surprise....

I also took into account smaller factors, like adding the constant 1 to the log and using the actual k values rather than just 7000; these only increase the denominator by ~9 in the extreme case, though, so not a big deal.