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

Pseudoprimi di Frobenius

Teoria dei numeri 

Dato un polinomio P(x) a coefficienti interi e col coefficiente del termine di grado massimo uguale a 1, si dicono “pseudoprimi di Frobenius rispetto a P(x)” i numeri dispari composti che passano un test definito da Jon Grantham (2000), che dipende da P(x).

 

Nel caso di polinomi quadratici della forma P(x) = x2bxc, un intero n primo rispetto a 2c(b2 + 4c) è primo o pseudoprimo di Frobenius rispetto a P(x) se Simbolo di Jacobi (b^2 – 4 * c | n) uguale a 1 e xnx mod MCD(n, P(x)) oppure se Simbolo di Jacobi (b^2 – 4 * c | n) uguale a –1 e xnbx mod MCD(n, P(x)), dove Simbolo di Jacobi (m | n) è il simbolo di Jacobi (Jon Grantham, 2000).

Gli pseudoprimi di Frobenius rispetto al polinomio x2Px + Q sono i numeri composti che sono contemporaneamente pseudoprimi di Lucas (I) rispetto a P e Q e pseudoprimi di Dickson di seconda specie (v. pseudoprimi di Lucas (I)) rispetto a P e Q.

Gli pseudoprimi di Frobenius rispetto a P = 1 e Q = –1 si dicono “pseudoprimi di Fibonacci – Frobenius”; i primi sono 4181 = 37 • 113 e 5777 = 53 • 109.

Non si conosce alcun pseudoprimo di Fibonacci – Frobenius che sia il quadrato di un primo; se esistono, sono maggiori di 1013.

 

Andrzej Rotkiewicz dimostrò che:

  • esistono infinite progressioni aritmetiche di tre pseudoprimi di Fibonacci – Frobenius (1972); in particolare, se p e 2p – 1 sono primi, Primo termine della progressione aritmetica di tre pseudoprimi di Fibonacci – FrobeniusSecondo termine della progressione aritmetica di tre pseudoprimi di Fibonacci – Frobenius e Terzo termine della progressione aritmetica di tre pseudoprimi di Fibonacci – Frobenius costituiscono una progressioni aritmetiche di tre pseudoprimi di Fibonacci – Frobenius (2002);

  • esistono infiniti pseudoprimi di Fibonacci che non sono pseudoprimi di Fibonacci – Frobenius (1972); in particolare se p è primo, p ≡ 1 mod 6 e p ≡ ±1 mod 5, F2p è pseudoprimo di Fibonacci e pseudoprimo di Fibonacci – Frobenius (2002); per esempio, per p = 19, F2p = 39088169 = 37 · 113 · 9349 è pseudoprimo di Fibonacci e pseudoprimo di Fibonacci – Frobenius;

  • esistono infiniti pseudoprimi di Fibonacci che non sono pseudoprimi di Fibonacci – Frobenius (1972); in particolare se p è un primo maggiore di 5 e p ≡ 1 mod 6, F2p è pseudoprimo di Fibonacci, ma non è pseudoprimo di Fibonacci – Frobenius (2002); per esempio, per p = 17, F2p = 5702887= 1597 · 3571 è pseudoprimo di Fibonacci, ma non è pseudoprimo di Fibonacci – Frobenius;

  • per P e Q uguali a ±1 esistono infiniti pseudoprimi di Frobenius, ciascuno prodotto di due primi distinti (1973);

  • in ogni sequenza della forma an + b, con a e b primi tra loro, vi sono infiniti pseudoprimi di Frobenius con P e Q uguali a ±1 (1973).

 

Nel caso di polinomi cubici della forma P(x) = (xa)(x2 – 2axc) un intero n primo rispetto a 8c(a2 + c) è primo o pseudoprimo di Frobenius rispetto a P(x) se Simbolo di Jacobi (–4 * (a^2 + c)^2 | n) uguale a 1 e xnx mod MCD(n, P(x)) oppure se Simbolo di Jacobi (–4 * (a^2 + c)^2 | n) uguale a –1 e xnbx mod MCD(n, P(x)), dove Simbolo di Jacobi (m | n) è il simbolo di Jacobi (Catherine A. Buell e Eric W. Kimball, 2014).

 

Grantham dimostrò nel 2001 che gli pseudoprimi di Frobenius rispetto al polinomio x3rx2 + sx – 1 sono anche pseudoprimi di Perrin, ma non necessariamente viceversa.

 

Gli pseudoprimi di Frobenius rispetto al polinomio (xa)(x2bxc) sono anche pseudoprimi di Frobenius rispetto al polinomio x2bxc, ma non necessariamente viceversa (Catherine A. Buell e Eric W. Kimball, 2014).

 

Basandosi sugli pseudoprimi di Frobenius sono stati sviluppati vari metodi per stabilire se un numero è primo, con una probabilità di errore molto bassa:

  • nel 1998 Jon Grantham sviluppò un esame con probabilità di errore non superiore a 1 / 7710;

  • nel 2001 Müller sviluppò un esame con probabilità di errore non superiore a 1 / 131040;

  • nel 2003 Damgård e Frandsen svilupparono un esame con probabilità di errore non superiore a 1 / 1296;

  • nel 2005 Martin Seysen sviluppò un esame con probabilità di errore non superiore a 1 / 4096 e uno con probabilità di errore non superiore a 8 / 168221.

Vedi anche

Pseudoprimi.

Contattami

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