Wheel factorization: Efficient?

[CRGreathouse]

Originally Posted by 3.14159

Passes SPRP test (No base specified)

"No base specified" = base 2, in this case, since the script has

isSPRP(n,b=2)

making the value of b 2 unless it's explicitly made something else.

Originally Posted by 3.14159

Those all fail the TD test.

You changed the code on my if you're trial-dividing to a million; it was only doing it to 500 before.

But I'm surprised you can't see the relevance of the sequence -- it should be easy to use it to find all exceptions up to 100 billion.

[CRGreathouse]

Originally Posted by 3.14159

Wait.. To weed out pseudoprimes
I should change b to (random(n)).

That doesn't weed out pseudoprimes, it just tests to a random base. Of course if you do that the pseudoprimes you get will be unpredictable -- you can't just check a list of 2-pseudoprimes, for example.

[3.14159]

That doesn't weed out pseudoprimes, it just tests to a random base. Of course if you do that the pseudoprimes you get will be unpredictable -- you can't just check a list of 2-pseudoprimes, for example.

What are the chances that the number might be pseudoprime to a random base, especially when dealing with the larger integers? And, pseudoprimes share the property of becoming less common in larger integers with the (genuine) primes.

[CRGreathouse]

Originally Posted by 3.14159

What are the chances that the number might be pseudoprime to a random base, especially when dealing with the larger integers?

For the Fermat test near n, at most : some numbers are pseudoprime to almost all bases.

For the Miller-Rabin test near n, at most 1/4. 88831 is a strong pseudoprime to 22049 out of the 88829 valid choices of base.

[3.14159]

For the Fermat test near n, at most : some numbers are pseudoprime to almost all bases.

Carmichael numbers.

For the Miller-Rabin test near n, at most 1/4. 88831 is a strong pseudoprime to 22049 out of the 88829 valid choices of base.

Those are worst-case odds. How about average odds?

[CRGreathouse]

Originally Posted by 3.14159

Those are worst-case odds. How about average odds?

Suppose you pick odd k-bit numbers uniformly at random and do a strong pseudoprime test, discarding it and restarting the procedure if it's proven composite. Let p_k represent the probability that the procedure stops on a composite rather than a prime.

According to Damgård, Landrock, & Pomerance (1993), p_100 is at most 0.68%, p_150 is at most 0.034%, p_200 is at most 0.0017%, and p_250 is at most 0.000084%.

I can't get useful estimates below 100 bits, though; Theorem 2 gives only that p_75 < 55%.

[3.14159]

I can't get useful estimates below 100 bits, though; Theorem 2 gives only that p_75 < 55%.

55%

[CRGreathouse]

I imagine you're thinking that it's obviously at most 25%. Damgård, Landrock, & Pomerance address this misconception on p. 178.

[3.14159]

I imagine you're thinking that it's obviously at most 25%. Damgård, Landrock, & Pomerance address this misconception on p. 178.

Well, then, if the at max probability of failure is not 1/4ⁿ for n randomly chosen bases, what is it?

1/2ⁿ? 1/1.5ⁿ? 1/1.25ⁿ? (The last one is initially ridiculous, its first term = 80% chance of failure.)

[CRGreathouse]

Originally Posted by 3.14159

Well, then, if the at max probability of failure is not 1/4ⁿ for n randomly chosen bases, what is it?

For the problem I stated, it's quite complicated. An upper bound (based on DLP Theorem 2) would be
.

[R.D. Silverman]

Originally Posted by CRGreathouse

Suppose you pick odd k-bit numbers uniformly at random and do a strong pseudoprime test, discarding it and restarting the procedure if it's proven composite. Let p_k represent the probability that the procedure stops on a composite rather than a prime.

According to Damgård, Landrock, & Pomerance (1993), p_100 is at most 0.68%, p_150 is at most 0.034%, p_200 is at most 0.0017%, and p_250 is at most 0.000084%.

I can't get useful estimates below 100 bits, though; Theorem 2 gives only that p_75 < 55%.

http://dilbert.com/strips/comic/2001-10-25/