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

Pseudoprimi ellittici

Teoria dei numeri 

L’introduzione di un test di primalità basato sulle proprietà di punti con coordinate razionali su una curva ellittica, cioè una curva di equazione y2 = x3 + ax + b, con a e b interi e D = –16(4a3 + 27b2) ≠ 0, portò D.M. Gordon nel 1987 a definire “pseudoprimi ellittici” i numeri composti che non vengono identificati come tali dal test.

 

La definizione degli pseudoprimi ellittici è piuttosto tecnica e necessita di alcune premesse.

Una retta interseca una curva ellittica in uno o 3 punti (due dei quali eventualmente coincidenti, in caso di tangenza) e se le coordinate di due delle intersezioni sono razionali, anche quelle della terza lo sono. Questo permette di definire un’operazione di addizione tra i punti con cordinate razionali su una curva ellittica, dove A = B + C significa che A è la terza intersezione con la curva di una retta passante per B e C (invertendo il segno della coordinata y). Un punto si può anche “sommare” a se stesso e il risultato è l’altra intersezione con la curva della retta tangente nel punto.

L’operazione di addizione dà all’insieme dei punti con coordinate razionali sulla curva una struttura di gruppo; si definisce quindi “ordine” di un punto P come il minimo valore di n tale che nP = 0, ossia il minimo numero di volte per le quali si deve sommare il punto a se stesso per raggiungere l’origine.

Data una curva ellittica e un punto P su di essa avente ordine infinito nel gruppo additivo dei punti con coordinate razionali sulla curva, se n è un primo tale che (–D | n) = –1 (dove Simbolo di Jacobi (–D | n) è il simbolo di Jacobi), allora (n + 1)PO mod n.

Un numero composto n, primo rispetto a D e che soddisfi le stesse relazioni si chiama “pseudoprimo ellittico”. Tali pseudoprimi dipendono sia dalla curva, sia dal punto iniziale scelto su essa.

 

D.M. Gordon dimostrò nel 1989 che:

  • esistono infiniti pseudoprimi ellittici rispetto alla curva y2 = x3 + 3 e al punto (1, 2), ma non è stato dimostrato un teorema analogo per qualsiasi curva e qualsiasi punto;

  • supponendo vera l’ipotesi di Riemann generalizzata, il numero di pseudoprimi ellittici minori di n cresce almeno come n * log(log(n)) / log(n)^2, quindi non molto più lentamente dei primi, ma ha densità nulla;

  • almeno per certe curve e punti iniziali, il numero di pseudoprimi ellittici minori di n è almeno sqrt(log(n)) / log(log(n)).

 

R. Balasubramanian e M. Ram Murty dimostrarono nel 1988 che il numero di pseudoprimi ellittici minori di n, per n abbastanza grande non supera n / e^(k * sqrt(log(n) * log(log(n)))), con K costante.

 

Nel 1989 Iam Miyamoto e M. Ram Murty dimostrarono che il numero di pseudoprimi ellittici minori di n è inferiore a n * sqrt(log(log(n)) / log(n)^3), indipendentemente dalla curva e dal punto iniziale.

 

Nel 1991 Gordon e Carl Pomerance dimostrarono che per qualsiasi curva e punto iniziale il numero degli pseudoprimi ellittici minori di n è inferiore a n / (e^(log(n) * log(log(log(n))) / log(log(n)))^(1 / 3), per n abbastanza grande.

 

Uno pseudoprimo ellittico che resta tale per qualsiasi scelta del punto P sulla curva si dice “numero di Carmichael ellittico” rispetto alla curva, un po’ come si chiamano “numeri di Carmichael” gli pseudoprimi di Fermat rispetto a qualsiasi base.

A differenza dei numeri di Carmichael, i numeri di Carmichael ellittici possono essere multipli di quadrati.

I minimi numeri di Carmichael ellittici rispetto alla curva y2 = x3 + 3 sono: 15, 77, 203, 245, 725, 875.

 

Si chiamano “numeri di Carmichael ellittici universali” i numeri di Carmichael ellittici rispetto a qualsiasi curva ellittica; è probabile che non esistano, ma non è stato dimostrato.

Contattami

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