Número pseudoprimo fort

Un número pseudoprimo fort és un número compuesto que satisfà el test de primalidad de Miller-Rabin. Tots els número primo passen esta prova, pero també passa una chicoteta fracció dels composts, lo que els convertix en números pseudoprimos.

A diferència dels pseudoprimos de Fermat, per als quals existixen números que són pseudoprimos para totes les bases de número coprimo (els números de Carmichael), no hi ha composts que siguen pseudoprimos forts per a totes les bases.

Motivació i primers eixemples

Suponga's que es vol investigar si n = 31697 és un provable primer (PRP). S'elegix llavors per eixemple la base a = 3, inspirada en el menuda teorema de Fermat, i es calcula:

$3^{31696}\equiv 1(\mathrm{mod}31697)$

Açò demostra que 31697 és un PRP de Fermat (en base 3), per lo que es pot sospitar que és un número primo. Ara, es reduïx a la mitat repetidament l'exponent:

$3^{15848}\equiv 1(\mathrm{mod}31697)$

$3^{7924}\equiv 1(\mathrm{mod}31697)$

$3^{3962}\equiv 28419(\mathrm{mod}31697)$

El primer parell de voltes no tira res interessant (el resultat seguix sent 1 mòdul 31697), pero en l'exponent 3962 s'observa un resultat que no és ni 1 ni menys 1 (és dir, 31696) mòdul 31697. Açò prova que 31697 és de fet compost (és igual a 29×1093). Prenent el mòdul a primer, el residu 1 no pot tindre atres raïls quadrades que 1 i menys 1. Açò demostra que 31697 no és un pseudoprimo fort en base 3.

Per a un atre eixemple, elegixca's n = 47197 i calcule's de la mateixa manera:

$3^{47196}\equiv 1(\mathrm{mod}47197)$

$3^{23598}\equiv 1(\mathrm{mod}47197)$

$3^{11799}\equiv 1(\mathrm{mod}47197)$

En este cas, el resultat seguix sent 1 (mod 47197) fins a aplegar a un exponent impar. En esta situació, es diu que 47197 és un cosí provable fort de base 3. Degut a que resulta que este PRP és de fet compost (es pot vore elegint atres bases que no siguen 3), es té que 47197 és un pseudoprimo fort respecte a la base 3.

Finalment, considere's n = 74593, d'a on s'obté:

$3^{74592}\equiv 1(\mathrm{mod}74593)$

$3^{37296}\equiv 1(\mathrm{mod}74593)$

$3^{18648}\equiv 74592(\mathrm{mod}74593)$

Ací s'aplega a menys 1 mòdul 74593, situació que és perfectament possible en un primer. Quan açò ocorre, es deté el càlcul (encara que l'exponent encara no és impar) i es diu que 74593 és un cosí provable fort (i, com a resultat, un pseudoprimo fort) en base 3.

Definició formal

Un número compuesto impar n = d · 2^s + 1, a on d és impar, es diu pseudoprimo forta (de Fermat) respecte a la base exponencial a si:

$a^d\equiv 1(\mathrm{mod}n)$

o

$a^{d\cdot 2^r}\equiv -1(\mathrm{mod}n)\text{para algún valor }0\le r<s.$

(Si un número n satisfà una de les condicions anteriors i encara no sabem si és primer, és més precís referir-se a ell com un provable primer fort en base a. Pero si sabem que n no és primer, llavors podem usar el terme pseudoprimo fort.)

La definició es complix trivialmente si a ≡ ±1 (mod n), per lo que estes bases trivials a sovint s'exclouen.

Guy va donar erròneament una definició en solament la primera condició, que no tots els número primo complixen.