Don't take life too seriously: it's just a temporary situation

Pseudoprimi simmetrici

Teoria dei numeri 

Dato un polinomio P(x) a coefficienti interi con coefficiente del termine di grado massimo uguale a 1, se p è primoP(x(k)^p) ≡ 0 mod p per ogni radice xk del polinomio. Un intero composto n si dice “pseudoprimo simmetrico” rispetto al polinomio P, se ha la stessa proprietà, ossia se P(x(k)^n) ≡ 0 mod n per ogni radice xk del polinomio.

Per esempio, nel caso del polinomio P(x) = x – 2, l’unica radice è 2 e il minimo pseudoprimo simmetrico è 341 = 11 • 13, perché P(2341) = 2341 – 2 ≡ 0 mod 341.

 

I numeri di Carmichael sono pseudoprimi simmetrici rispetto a qualsiasi polinomio con tutte le radici intere.

 

Chiamiamo SP, m(k) la somma delle k-esime potenze delle radici del polinomio, prese m alla volta in tutti i modi possibili. Per esempio, se le 4 radici di un polinomio di quarto grado sono x1, x2, x3 e x4:

  • S(P, 1)(k) = x(1)^k + x(2)^k + x(3)^k + x(4)^k,

  • S(P, 2)(k) = x(1)^k * x(2)^k + x(1)^k * x(3)^k + x(1)^k * x(4)^k + x(2)^k * x(3)^k + x(2)^k * x(4)^k + x(3)^k * x(4)^k,

  • S(P, 3)(k) = x(1)^k * x(2)^k * x(3)^k + x(1)^k * x(2)^k * x(4)^k + x(1)^k * x(3)^k * x(4)^k + x(2)^k * x(3)^k * x(4)^k,

  • S(P, 4)(k) = x(1)^k * x(2)^k * x(3)^k * x(4)^k.

Queste somme sono simmetriche rispetto alle radici del polinomio e il termine “pseudoprimo simmetrico” deriva dal fatto che un intero composto n è pseudoprimo simmetrico rispetto a un polinomio P se e solo se SP, m(n) ≡ SP, 1(1) mod n per 1 < md, dove d è il grado del polinomio.

 

Se n è primo o pseudoprimo simmetrico rispetto a P, SP, m(kn) ≡ SP, m(k) mod n per 1 < md e ogni intero positivo k; inoltre se n è primo rispetto al termine costante del polinomio, la relazione vale anche per k intero negativo.

Un intero composto n è invece pseudoprimo ordinario rispetto a un polinomio P se e solo se SP, 1(n) ≡ SP, 1(1) mod n, quindi uno pseudoprimo simmetrico deve soddisfare molte più condizioni di uno ordinario e gli pseudoprimi simmetrici sono più rari di quelli ordinari.

Un intero composto n primo rispetto a d! è pseudoprimo simmetrico rispetto a P se e solo se SP, 1(kn) ≡ SP, 1(k) mod n per 0 < kd, dove d è il grado di P. Per uno pseudoprimo ordinario la congruenza vale solo per k = 1.

 

Se il termine costante del polinomio è 1 o –1:

  • un intero composto n primo rispetto a (d – 1)! è pseudoprimo simmetrico rispetto a P se e solo se SP, 1(kn) ≡ SP, 1(k) mod n per 0 < k < d;

  • un intero composto n primo rispetto a Fattoriale del massimo intero non superiore a d / 2 è pseudoprimo simmetrico rispetto a P se e solo se SP, 1(kn) ≡ SP, 1(k) mod n per Limiti inferiore e superiore per k.

 

Gli pseudoprimi simmetrici rispetto a un polinomio di primo grado xc sono gli pseudoprimi di Fermat rispetto a c.

 

Gli pseudoprimi simmetrici rispetto a un polinomio di secondo grado (xa)(xb), con a e b interi, sono gli pseudoprimi di Fermat rispetto sia ad a che a b (e quindi in particolare i numeri di Carmichael) e gli interi n composti tali che an + bna + b mod n e che anbnab mod n.

Per esempio, escludendo i numeri pseudoprimi di Fermat sia rispetto a 2 che a 3, vi sono 35 pseudoprimi ordinari rispetto al polinomio (x – 2)(x – 3) minori di 106 (v. pseudoprimi ordinari), ma tra questi solo 15 è pseudoprimo simmetrico.

Escludendo i numeri pseudoprimi di Fermat rispetto a 2, 3 e 5, vi sono 18 pseudoprimi ordinari rispetto al polinomio (x – 2)(x – 3)(x – 5) minori di 106 (v. pseudoprimi ordinari), ma tra questi solo 50721 e 811921 sono pseudoprimi simmetrici.

Quindi anche con polinomi prodotto di semplici polinomi di primo grado gli pseudoprimi simmetrici sono ben pochi in più degli pseudoprimi rispetto alle radici dei polinomi. Utilizzando polinomi opportunamente scelti, in particolare senza radici intere, si possono rendere gli pseudoprimi simmetrici molto rari e si può costruire un test di primalità molto efficiente.

Per esempio, gli unici pseudoprimi simmetrici rispetto al polinomio x2 – 4x – 9 inferiori a 106 sono 10, 1105, 2465, 15457 e 38503; per confronto, un test basato sugli pseudoprimi di Fermat, anche utilizzando numerose basi diverse, si lascerebbe sfuggire come minimo i 43 numeri di Carmichael inferiori a 106.

 

Il minimo pseudoprimo simmetrico rispetto al polinomio di Perrin x3x – 1 è 27664033 = 3037 • 9109.

 

Il minimo pseudoprimo simmetrico rispetto al polinomio x5x3 – 2x2 + 1 è 2258745004684033 = 27439297 • 82317889.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.