[QUOTE=3.14159;222425]Passes SPRP test (No base specified)[/QUOTE]

"No base specified" = base 2, in this case, since the script has
[code]isSPRP(n,b=2)[/code]
making the value of b 2 unless it's explicitly made something else.

[QUOTE=3.14159;222425]Those all fail the TD test.[/QUOTE]

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.

[QUOTE=3.14159;222425]Wait.. To weed out pseudoprimes
I should change b to (random(n)).[/QUOTE]

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.

[QUOTE]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.[/QUOTE]

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.

[QUOTE=3.14159;222430]What are the chances that the number might be pseudoprime to a random base, especially when dealing with the larger integers?[/QUOTE]

For the Fermat test near n, at most [TEX]1-2/\sqrt n[/TEX]: 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.

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

Carmichael numbers. :tu:

[QUOTE]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.[/QUOTE]

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

[QUOTE=3.14159;222432]Those are worst-case odds. How about average odds?[/QUOTE]

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%.

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

55% :orly owl:

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

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

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

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

[QUOTE=3.14159;222449]Well, then, if the at max probability of failure is not 1/4[sup]n[/sup] for n randomly chosen bases, what is it?[/QUOTE]

For the problem I stated, it's quite complicated. An upper bound (based on DLP Theorem 2) would be
[TEX]k^{2n}\cdot4^{2n-n\sqrt k}[/TEX].

[QUOTE=CRGreathouse;222435]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%.[/QUOTE]

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