Talk:Strong pseudoprime

Redundant?

"A strong pseudoprime to base a is always an Euler pseudoprime to base a (Pomerance, Selfridge, Wagstaff 1980), but not all Euler pseudoprimes are strong pseudoprimes. Some Fermat pseudoprimes and Carmichael numbers are also strong pseudoprimes."

"A strong pseudoprime to base a is always an Euler pseudoprime to base a" includes that every strong pseudoprime is a fermat pseudoprime. So "Some Fermat pseudoprimes and Carmichael numbers are also strong pseudoprimes" is redundant and should be: "Some Carmichael numbers are also strong pseudoprimes". --Arbol01 23:40, 9 January 2007 (UTC)[reply]

Clarify relation to Miller-Rabin Test

My understanding is that the Strong Pseudo Prime Test is the same as the Miller-Rabin test, and that Strong Pseudo Prime Test was invented by Selfridge. I also understand that Miller-Rabin invented their test independently but later than Selfridge. The Miller-Rabin test got more publicity because they proved that it errs with probability at most 1/4th per iteration. Scott contini (talk) 02:08, 19 August 2010 (UTC)[reply]

I agree that there should be a more prominent mention or merging of Miller–Rabin primality test. Crandall and Pomerance page 136 indicate the test was first suggested by Artjuhov in 1966, followed by Selfridge who independently rediscovered and and publicized it in the early 1970s including coining the name "strong pseudoprime". Miller published his test in 1975, Rabin in 1976 ("Probabilistic Algorithms") with the more commonly cited publication being the 1980 (first received 1977) "Probabilistic Algorithm for Testing Primality" which had the error bounds. See PSW80 page 1004 for some info as well (e.g. "Gary Miller was the first to consider examining

a^{d\cdot 2^{r}}

as in (ii)...").

Dietzfelbinger 1998, pages 80-81 also points out Artjuhov then discusses Miller, Rabin, Bach, and Monier. No mention at all of Selfridge. Brent 2010 mentions everyone including Dubois, as does Bernstein 2010 with the preface "Messy history". Morain calls it the "Dubois-Selfridge-Miller-Rabin algorithm".

Knuth usually gives a good history, and is mentioned in Rabin's 1980 paper as having commented on the algorithm in 1978. TAoCP volume 2 3rd edition page 396 states that his Algorithm P (pretty much what we think of now as the Miller-Rabin test) is "a simplified version of a procedure due to M. O. Rabin, based in part on ideas of Gary L. Miller" and cites Rabin's 1976 paper.

I think Bernstein said it well with "messy history". I'd guess that Miller and Rabin get the name because (1) Miller's deterministic work showing something substantially different than just XYZ pseudoprime tests, and (2) Rabin's well-formed paper with error bounds vs. the previous "it's a really good test" without qualifiers. DAJ NT (talk) 22:18, 4 June 2015 (UTC)[reply]

Are strong pseudoprimes always Euler-Jacobi pseudoprimes?

I found that 91 is a strong pseudoprime to base 12, but it is not an Euler-Jacobi pseudoprime to base 12, I doubt that the article is not true. — Preceding unsigned comment added by 101.12.251.120 (talk) 09:36, 16 February 2015 (UTC)[reply]

Yes, they are. For a=12, n=91:

\scriptstyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

hence it is a Euler-Jacobi pseudoprime. See the Pomerance-Selfridge-Wagstaff paper, page 1009. It's also noted in Grantham 2001, Riesel, and elsewhere. Note that most sources say Euler pseudoprime for what this Wikipedia is distinguishing as a Euler-Jacobi pseudoprime. DAJ NT (talk) 21:05, 4 June 2015 (UTC)[reply]

Least witness to bases 2..n

Some ways to create this list. Perl:

use ntheory ":all"; my @ps; for my $b (2..100) { for my $n (1..1e7) { if (!is_prime($n) && ($b % $n) && is_strong_pseudoprime($n,$b)) { push @ps,$n; last } } } print join(", ",@ps), "\n";

Pari/GP:

is(n, b=3)={ bittest(n, 0)||return; ispseudoprime(n)&return; my(d=(n-1)>>valuation(n-1, 2)); Mod(b, n)^d==1 || until(n-1<=d*=2, Mod(b, n)^d+1 || return(1))};
for(base=2,100,forcomposite(n=2,10^7,if(is(n,base),print1(n", ");break)))

I don't understand why we particularly care about this list, but there we are. DAJ NT (talk) 20:37, 4 June 2015 (UTC)[reply]

Looks like 24.240.67.157 reverted back to the giant table. Can we remove this or compress it? I don't see that the table adds any value to the subject. The author has added similar tables to other pages such as Fermat pseudoprime, Euler pseudoprime, and Euler-Jacobi pseudoprime. These tables seem like examples of the WP:Datahoard subject. DAJ NT (talk) 08:35, 29 August 2015 (UTC)[reply]

Removed the huge tables, copied from OEIS, by 101.15.81.148. There is no reason for this data to be on the page. DAJ NT (talk) 18:02, 29 June 2016 (UTC)[reply]

Something wrong

1 there are no composites that are strong pseudoprimes to all bases.

2 But if we know that n is not prime, then one may use the term strong pseudoprime.

3 There are infinitely many strong pseudoprimes to any base

Something wrong with those sentences

From 2 follows, that strong pseudoprime must be composite

But in that case 1 contradict 3.

Jumpow (talk) 11:59, 13 April 2017 (UTC)[reply]

I was wrong...

There are infinitely many strong pseudoprimes to any (given) base

there are no (instance of) composites that are strong pseudoprimes to all bases.

But thouse sentence are confusing. I think they must be rewritten more clearly. Jumpow (talk) 12:04, 13 April 2017 (UTC)[reply]