Magma, gruppi e curve ellittiche: uno strumento per scoprire nuovi risultati

Prof. Andrea Previtali andrea.previtali@uninsubria.it

http://scienze-como.uninsubria.it/previtali Milano, 06 Marzo 2006

Differenze tra valori assunti da permutazioni

Problema: Sia n un intero pari, mostrare che esiste una permutazione σ ∈ Sym (n) tale che {σ(i+1)−σ(i) : i = 1, …, n} considerato come un sottoinsieme dell’anello delle classi di resto ℤ/n ha cardinalità n − 1. Come procedere? Esperimento: Controlliamo alcuni valori piccoli per n. Già per n = 4 dobbiamo considerare 24 = 4! insiemi di cardinalità al piú 4. Cio significa calcolare 4 · 24 = 96 differenze. In generale dobbiamo effettuare n · n! differenze. Sfortunatamente questo numero cresce molto rapidamente (quanto?).

Magma

Magma è uno tra una serie di programmi atti ad effettuare calcoli matematici. Ne esistono altri come Maple e Mathematica. Sono probabilmente piú noti perché consentono di risolvere problemi in (quasi) tutti i campi della Matematica. Magma si specializza in problemi di Algebra e Geometria.

Le referenze di Magma

Magma è il risultato dell’evoluzione e dell’integrazione di vari linguaggi di manipolazione simbolica nati a partire dalla fine degli anni Settanta. Per citarne alcuni Cayley, CAS, Maxima, Axiom, Macaulay, Kant/Kash, Pari-Gp, Gap, Singular. Originariamente implementato per sistemi Unix/Linux, è stato esteso a sistemi Windows e MacIntosh. Il luogo di nascita è l’Università di Sydney.

Sul sito http://magma.maths.usyd.edu.au/ sono reperibili i files sor-

gente e vari manuali.

Ad esempio un manuale introduttivo (889 pagine), un manuale di referenza o Handbook (4047 pagine) e un manuale di esempi (245 pagine). Ecco una lista dei contenuti dell’Handbook: THE MAGMA LANGUAGE SETS, SEQUENCES, AND MAPPINGS SEMIGROUPS AND MONOIDS FINITE GROUPS INFINITE GROUPS BASIC RINGS AND LINEAR ALGEBRA EXTENSIONS OF RINGS MODULES AND ALGEBRAS DIFFERENTIAL RINGS REPRESENTATION THEORY LIE THEORY COMMUTATIVE ALGEBRA ALGEBRAIC GEOMETRY ARITHMETIC GEOMETRY FINITE INCIDENCE STRUCTURES CODING THEORY CRYPTOGRAPHY OPTIMIZATION

Gruppi Simmetrici

Magma consente di definire e lavorare coi gruppi simmetrici Sym (n) agenti su un numero qualsiasi di oggetti n.

Qualsiasi? Ovviamente n deve essere un intero. Teoricamente ogni intero è lecito. Ma come gli Ingegneri ci ricordano (o dovrebbero ricordarci) le risorse di calcolo sono limitate. Un laptop come quello che uso riesce a lavorare (con fatica) con n ≈ 10^{9}.

Mostro alcuni esempi con n = 10000.

Classi di resto

Magma consente di definire e lavorare con ℤ_{n} l’anello delle classi di resto modulo un intero n. (Gli interi n-adici non verranno menzionati, quindi non dovrebbe esserci confusione colla notazione.) Anche qui n ha limitazioni legate al computer. Mostro alcuni esempi per n = 10000.

Traduzione del problema

Apparentemente Magma ci consente di tradurre il problema iniziale in input. Data σ ∈ Sym (n) dobbiamo costruire {σ(i + 1) − σ(i) : i = 1, …, n}. Anche in questa semplice struttura si annidano dei problemi.

L’insieme naturale su cui agisce G = Sym (n) è Ω = {i = 1, …, n}.

Allora σ(n + 1) non è definito. D’altro canto se faccio variare i in ℤ_{n} e uso, come fa Magma, come rappresentanti gli interi {0, …, n − 1} allora σ(n) = σ(0) non è definito.

Diventa forte la tentazione di lasciar perdere Magma e usare carta e matita.

Esiste una soluzione tecnica che consiste di dotare ℤ_{n} della struttura di G-insieme.

Oppure si usa un piccolo trucco, ossia si sostituisce i con ((i−1) mod n)+ 1 al variare di i in {1, …, n}.

L’insieme a cui siamo interessati sembra diventare

{(i mod n + 1)^{σ} − (i − 1 mod n + 1)^{σ} : i ∈ [1..n]},

ove [1..n] è il simbolo usato da Magma per denotare la lista dei primi n interi.

Attenzione all’errore

Perché dico sembra? Prendete σ = (1, 4, 2, 3), allora

|{(i mod 4 + 1)^{σ} − (i − 1 mod 4 + 1)^{σ} : i ∈ [1..4]}| = 4. Ma ℤ_{4} ha 4 elementi ed essendo σ iniettiva 0 non compare mai come valore nel precedente insieme.

L’errore consiste nel non aver specificato il contesto corretto. Dobbiamo dire a Magma che l’insieme delle differenze va considerato come un sottoinsieme di ℤ_{n}, altrimenti viene visto come un sottoinsieme di ℤ. Magma consente di modificare il contesto specificandolo subito dopo la parentesi {. L’insieme corretto è Δ_{σ} = {ℤ_{n} | (i mod n + 1)^{σ} − (i − 1 mod n + 1)^{σ} : i ∈ [1..n]}.

Alcuni dati sperimentali

Ora si tratta di far variare σ ∈ Sym (n) finché la cardinalità di Δ_{σ} = n−1. Magma consente di stabilire l’esistenza di un tale elemento mediante il comando exists(τ){σ : σ ∈ Sym (n) | |Δ_{σ}| = n − 1}. Alla variabile τ viene assegnato come valore quello della prima permutazione che soddisfa la condizione richiesta. Per n ≤ 12 la risposta è affermativa, ma l’impressione è che i tempi di risposta crescano molto rapidamente. Questi sono trascurabili per n ≤ 6, ma diventano 0.120, 9.003 e 392.034 secondi per n = 8, 10 e 12.

E se n fosse dispari?

A volte vige il motto che generalizzando si possa semplificare il problema. Ha comunque senso chiedersi cosa accade quando n è dispari. Chiaramente n − 1 è il massimo valore che può assumere |Δ_{σ}| quando σ varia in Sym (n). Per n = 3, 5 non esiste alcun σ con |Δ_{σ}| = n − 1, ma esiste σ tale che |Δ_{σ}| = n − 2. Forse la congettura corretta è che ∀m ∈ ℕ, ∃σ ∈ Sym (2m + ε) tale che |Δ_{σ}| = 2m − 1, ove ε = 0, 1.

Generalizzo

Potremmo chiederci quale forma ha C_{n} = {|Δ_{σ}| : σ ∈ Sym (n)}.

Se non basta potremmo contare anche quante volte una certa cardinalità si ripete. La struttura corrispondente viene chiamata un multinsieme e la sintassi in Magma risulta essere M_{n} = {^{∗}|Δ_{σ}| : σ ∈ Sym (n)^{∗}}.

Qui sono riportati i tempi di esecuzione, C_{n} e M_{n} per n = 2, …, 10

n=2
Time: 0.000
{* 1^^2 *}
{ 1 }
n=3

Time: 0.000
{* 1^^6 *}
{ 1 }
n=4
Time: 0.000
{* 1^^8, 3^^16 *}
{ 1, 3 }
n=5
Time: 0.010
{* 1^^20, 3^^100 *}
{ 1, 3 }
n=6
Time: 0.030
{* 1^^12, 2^^60, 3^^288, 4^^288, 5^^72 *}
{ 1, 2, 3, 4, 5 }

n=7
Time: 0.210
{* 1^^42, 3^^1764, 4^^882, 5^^2352 *}
{ 1, 3, 4, 5 }
n=8
Time: 1.913
{* 1^^32, 2^^96, 3^^3584, 4^^10112, 5^^18816, 6^^6912, 7^^768 *}
{ 1, 2, 3, 4, 5, 6, 7 }
n=9
Time: 19.027
{* 1^^54, 2^^162, 3^^12744, 4^^39366, 5^^156978,
6^^105948, 7^^47628 *}
{ 1, 2, 3, 4, 5, 6, 7 }
n=10
Time: 211.724

{* 1^^40, 2^^760, 3^^18000, 4^^188400, 5^^826400,
6^^1420400, 7^^966000, 8^^194400, 9^^14400 *}
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Vedete qualche regolarità?

Non tutti gli errori vengono per nuocere

Stranamente la risposta (errata) ottenuta prima di cambiare contesto sembra ancora piú regolare

2
Time: 0.000
{* 2^^2 *}
{ 2 }
3
Time: 0.000
{* 2^^6 *}
{ 2 }
4
Time: 0.000

{* 2^^8, 3^^8, 4^^8 *}
{ 2, 3, 4 }
5
Time: 0.000
{* 2^^20, 3^^20, 4^^60, 5^^20 *}
{ 2, 3, 4, 5 }
6
Time: 0.020
{* 2^^12, 3^^84, 4^^336, 5^^168, 6^^120 *}
{ 2, 3, 4, 5, 6 }
7
Time: 0.200
{* 2^^42, 3^^112, 4^^1106, 5^^1932, 6^^1484, 7^^364 *}
{ 2, 3, 4, 5, 6, 7 }

Time: 1.803
{* 2^^32, 3^^224, 4^^3312, 5^^9648, 6^^16256,
7^^9216, 8^^1632 *}
{ 2, 3, 4, 5, 6, 7, 8 }
9
Time: 17.445
{* 2^^54, 3^^450, 4^^8298, 5^^39402, 6^^112752,
7^^129996, 8^^62568, 9^^9360 *}
{ 2, 3, 4, 5, 6, 7, 8, 9 }
10
Time: 197.855
{* 2^^40, 3^^700, 4^^18080, 5^^141760, 6^^603660,
7^^1203560, 8^^1139800, 9^^461360, 10^^59840 *}
{ 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Piani Proiettivi

Sia F un campo e sia ℙ^{2}(F) il piano proiettivo su F, ossia l’insieme delle classi di equivalenza in F^{3} ∖(0, 0, 0) rispetto alla relazione di equivalenza

(x, y, z) ∼ (ux, uy, uz),

ove u ∈ F^{∗}. Si indichi con (x : y : z) la classe di equivalenza contenente (x, y, z). (x : y : z) viene detto un punto proiettivo. Sia P (X, Y, Z) un polinomio omogeneo in F [X, Y, Z]. Si noti che P (x, y, z) = 0 sse P (ux, uy, uz) = 0, ∀u ∈ F^{∗}. Quindi ha senso dire che (x : y : z) annulla il polinomio P.

Curve Ellittiche

Sia P ∈ F [X, Y, Z] un polinomio omogeneo cubico. Diciamo che P definisce una curva ellittica E su F se

∃(x : y : z) ∈ ℙ^{2}(F) tale che P (x, y, z) = 0 (Esistenza punto razionale)

se nessun punto annulla le tre derivate parziali ∂_{i}P, i = 1, 2, 3 (Non singolare)

La seconda condizione è facilmente controllabile. Ad esempio usando basi di Groebner.

Punti Razionali

Per la prima non è noto alcun algoritmo in grado di fornire una risposta per ogni campo F. Ad esempio Selmer ha dimostrato che

E : 3X^{3} + 4Y^{3} + 5Z^{3} = 0

non ha punti su ℙ^{2}(ℚ), ma ne ha su ℙ^{2}(𝔽_{q}), per ogni q. Quindi non vale un Teorema Locale-Globale come quello di Hasse-Minkowski.

Genere

In realtà la definizione tecnica di curva ellittica è Una curva piana, non-singolare, di genere g = 1 Per una curva non singolare C ottenuta come luogo degli zeri di un polinomio omogeneo di grado d, il genere di C si ottiene facilmente come

g(C) = \frac{(d − 1)(d − 2)}{2} .

Quindi una curva piana cubica non-singolare ha sempre genere 1, quindi è ellittica sse possiede un punto razionale.

Ma esistono curve piane di grado d con punti razionali e di genere 1 (quindi sono singolari). Queste si possono trasformare con mappe birazionali in una curva ellittica, ossia mappe definite da funzioni razionali aventi inversa della stessa forma.

Ad esempio

C : X^{3}Y^{2} + X^{3}Z^{2} − Z^{5}

è una quintica di genere 1 con due punti singolari.

Modelli di Weierstraß

Sia C una curva ellittica su F allora C si trasforma nella curva

E : Y^{2}Z + a_{1}XY Z + a_{3}Y Z^{2} = X^{3} + a_{2}X^{2}Z + a_{4}XZ^{2} + a_{6}Z^{3}, a_{1}, a_{2}, a_{3}, a_{4}, a_{6} ∈ F. E viene detta un modello di Weierstraß esteso per C. Se char (F) ≠ 2, 3, possiamo ridurre ulteriormente la curva nella forma

W : Y^{2}Z = X^{3} + a_{4}XZ^{2} + a_{6}Z^{3}.

W viene detta un modello di Weierstraß per E.

Ad esempio sia C la curva piana definita dall’equazione di Fermat

C : X^{3} + Y^{3} + Z^{3}

su ℚ. Allora (0 : −1 : 1) ∈ C e C è non-singolare essendo le derivate parziali pari a 3X^{2}, 3Y^{2}, 3Z^{2}. Quindi C è ellittica.

Magma ne fornisce un modello di Weierstraß esteso

E : Y^{2}Z − 9Y Z^{2} = X^{3} − 27Z^{3}

e, siccome char (ℚ) = 0, posso ottenere anche un modello di Weierstraß

W : Y^{2}Z = X^{3} − 314928Z^{3}.

Modelli Minimali

Nel caso in cui E sia definita sugli interi, è possibile definire un modello minimale. Questo è l’analogo della riduzione in minimi termini di una frazione. Possiamo supporre che in coordinate non omogenee

E : y^{2} = f(x),

ove deg (f) = 3, f ∈ ℤ[x], monico. Tra tutti i modelli di E definiti su ℤ ne esiste uno per cui il discriminante di Disc(f) =Res(f, f′) è minimo. Tali discriminanti differiscono per dodicesime potenze intere. Tale modello viene detto modello minimale.

Gruppi Algebrici

Le curve ellittiche hanno sia la struttura di varietà algebriche che di gruppi abeliani. In un modello W di Weierstraß, lo zero è dato dal punto O = (0 : 1 : 0). Siccome W è non singolare, ogni retta per due punti P, Q di W passa per un terzo punto P ∗ Q di W. Si definisce P + Q mediante

P + Q + P ∗ Q = O.

Il miracolo è che + risulta essere un’operazione associativa su W. (W, +) risulta essere un gruppo abeliano.

Campi Finiti

Siamo interessati alle applicazioni crittografiche di tali gruppi e quindi considereremo in particolare il caso di campi finiti F = 𝔽_{q}, ove q = p^{s}, p primo. Per lavorare con un modello di Weierstraß, supponiamo che p ≠ 2, 3. Allora ogni curva ellittica su F è descritta da

E_{a,b} : Y^{2}Z = X^{3} + aXZ^{2} + bZ^{3},

con a, b ∈ F e 4a^{3} + 27b^{2} ≠ 0. Ovviamente G = E_{a,b} ha ordine al piú q^{2} + 1 = |𝔽_{q}^{2} ∪ O|, quindi risulta essere un gruppo abeliano finito.

Crittografia e Curve Ellittiche

Data una curva ellittica E su 𝔽_{q}, si può ideare un metodo di criptare messaggi come segue. Anna e Bruno scelgono pubblicamente E e un punto P ∈ E. Poi Anna sceglie un intero casuale a e invia aP a Bruno. Questi sceglie un intero casuale b e invia ad Anna bP. Entrambi sono in grado di calcolare a(bP) = b(aP) senza dover trasmettere a o b.

abP verrà usato come chiave per un sistema simmetrico.

Questa è la versione con curve ellittiche del protocollo di Diffie-Hellman.

Problema del Logaritmo Discreto

Nella scelta di P bisogna assicurarsi che |P | ≈ |E|, altrimenti Eva sarebbe in grado di determinare a a partire da aP e P semplicemente calcolando kP per k = 0, …, |P | − 1.

In linea di principio questo attacco è sempre possibile, ma richiede troppo tempo se q è abbastanza grande.

Il problema di determinare a a partire da aP e P viene detto il problema del logaritmo discreto. A tutt’oggi non sono noti metodi per le curve ellittiche essenzialmente migliori del metodo brute force indicato sopra. Ci si può ridurre a circa √|P | controlli usando il metodo baby step/giant step dovuto a Shanks.

Limite di Hasse

Cosa si può dire di |E| quando la curva è definita su 𝔽_{q}?

Un risultato dovuto a Hasse asserisce che

q + 1 − 2√q ≤ |E| ≤ q + 1 + 2√q.

Quindi nella scelta di E = E_{a,b} bisogna scegliere a, b ∈ 𝔽_{q} di modo che |E| abbia divisori primi grossi. Altrimenti un metodo dovuto a Pohlig e Hellman consente di ridurre il problema del logaritmo discreto a gruppi aventi ordine un divisore primo di |P |.

Simmetria

Incuriosito da questo problema ho analizzato la distribuzione di |E_{a,b}| al variare di a, b ∈ 𝔽_{q}, con 4a^{3} + 27b^{2} ≠ 0.

Qui sotto sono riportati i tempi di calcolo, q e le relative cardinalità con molteplicità, ove q è una potenza di un primo dispari.

Time: 0.000
3
{* 1, 4^^4, 7 *}
Time: 0.010
5
{* 2, 3^^2, 4^^3, 5^^2, 6^^4, 7^^2, 8^^3, 9^^2, 10 *}
Time: 0.010

{* 3, 4^^4, 5^^3, 6^^6, 7^^4, 8^^6, 9^^4, 10^^6,
11^^3, 12^^4, 13 *}
Time: 0.020
9
{* 4^^6, 7^^12, 10^^36, 13^^12, 16^^6 *}
Time: 0.020
11
{* 6^^5, 7^^5, 8^^10, 9^^10, 10^^10, 11^^5,
12^^20, 13^^5, 14^^10, 15^^10, 16^^10,
17^^5, 18^^5 *}
Time: 0.030
13
{* 7^^2, 8^^9, 9^^8, 10^^15, 11^^6, 12^^20,
13^^12, 14^^12, 15^^12, 16^^20, 17^^6,

18^^15, 19^^8, 20^^9, 21^^2 *}
Time: 0.050
17
{* 10^^4, 11^^8, 12^^24, 13^^8, 14^^16, 15^^24,
16^^28, 17^^8, 18^^32, 19^^8, 20^^28, 21^^24,
22^^16, 23^^8, 24^^24, 25^^8, 26^^4 *}
Time: 0.050
19
{* 12^^12, 13^^12, 14^^18, 15^^18, 16^^36,
17^^9, 18^^27, 19^^21, 20^^36, 21^^21,
22^^27, 23^^9, 24^^36, 25^^18, 26^^18,
27^^12, 28^^12 *}
Time: 0.080
23
{* 15^^11, 16^^22, 17^^11, 18^^44, 19^^11,

20^^44, 21^^33, 22^^22, 23^^22, 24^^66,
25^^22, 26^^22, 27^^33, 28^^44, 29^^11,
30^^44, 31^^11, 32^^22, 33^^11 *}
Time: 0.210
25
{* 16^^4, 17^^12, 18^^30, 19^^24, 20^^42, 21^^8,
22^^48, 23^^24, 24^^72, 25^^36, 27^^36, 28^^72,
29^^24, 30^^48, 31^^8, 32^^42, 33^^24, 34^^30,
35^^12, 36^^4 *}
Time: 0.250
27
{* 19^^117, 28^^468, 37^^117 *}
Time: 0.130
29
{* 20^^21, 21^^28, 22^^28, 23^^14, 24^^84,

25^^28, 26^^35, 27^^42, 28^^56, 29^^28,
30^^84, 31^^28, 32^^56, 33^^42, 34^^35,
35^^28, 36^^84, 37^^14, 38^^28, 39^^28,
40^^21 *}

Vedete qualche regolarità?