Magma, algebra commutativa e curve ellittiche:

uno strumento per scoprire nuovi risultati

Prof. Andrea Previtali Università dell’Insubria-Como andrea.previtali@uninsubria.it

http://scienze-como.uninsubria.it/previtali

Università di Milano-Bicocca, 24 Marzo 2006

Ideali e Varietà

Sia k un campo e sia R = k[x_{1}, …, x_{n}] l’anello dei polinomi in n variabili a coefficienti in k.

Un sottoinsieme non vuoto I di R dicesi un ideale se

I è un sottogruppo di (R, +) (in simboli I + I ≤ I);

∀r ∈ R, i ∈ I si ha ri ∈ I (in simboli RI ≤ I).

Ad esempio, fissati f_{1}, …, f_{s} ∈ R, I = {∑_{j} h_{j}f_{j} : h_{j} ∈ R} è un ideale. Viene detto l’ideale generato da f_{1}, …, f_{s} e sarà denotato con ⟨f_{1}, …, f_{s}⟩.

Viceversa un ideale della forma ⟨f_{1}, …, f_{s}⟩ viene detto finitamente generato. Teorema della base di Hilbert: Sia I un ideale di R = k[x_{1}, …, x_{n}], allora I è finitamente generato, ossia della forma ⟨f_{1}, …, f_{s}⟩. D’ora in poi assumeremo di specificare un ideale I mediante un insieme di generatori f_{1}, …, f_{s}. Problema (Membership): Dato f ∈ R stabilire se f ∈ I = ⟨f_{1}, …, f_{s}⟩. Dato un ideale I di R si indica con 𝒱(I) l’insieme {x ∈ k^{n} : f(x) = 0, ∀f ∈ I}. Tale insieme viene detto la varietà definita da I. Problema (Variety): Dato I determinare 𝒱(I).

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

Anelli di polinomi in più variabili

Magma consente di definire e lavorare con anelli di polinomi in n variabili

R = k[x_{1}, …, x_{n}]

per qualsiasi campo k ed intero n.

Qualsiasi? Teoricamente ogni intero n è 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^{5}.

Magma lavora con molti campi, i razionali ℚ, i reali ℝ, i complessi ℂ (con data precisione), i campi finiti 𝔽_{q}, i campi p-adici ℚ_{p} e relative estensioni (ciclotomiche, campi algebrici numerici, estensioni p-adiche non-ramificate e totalmente ramificate, ...)

Ideali

Magma consente di definire ideali in R specificando un insieme di generatori f_{1}, …, f_{s}. Il campo k deve essere esatto, ad esempio ℚ, ℚ[i] o 𝔽_{q}. Reali, complessi o p-adici possono risultare indigesti per un computer.

Ad esempio consideriamo l’ideale in ℚ[x, y] generato da f_{1} = x^{2} +y^{2} −7 e f_{2} = x^{2} − y^{2} − 1. Geometricamente I rappresenta l’intersezione di un’ellisse con un’iperbole.

Ovviamente I è generato da f_{1} + f_{2} = 2(x^{2} − 4) e f_{1} − f_{2} = 2(y^{2} − 3). Per cui 𝒱(I) = ∅ sui razionali.

Se I ha dimensione 0 Magma è in grado di fornire il numero di punti di V su una chiusura algebrica di ℚ e di determinarli simbolicamente.

Algoritmo di divisione

Nel caso in cui n = 1 esiste un metodo molto semplice per stabilire se un dato f appartiene a I = ⟨f_{1}, …, f_{s}⟩. Tale metodo si basa sull’algoritmo di divisione lunga che consente di calcolare rapidamente il massimo comune divisore g dei generatori f_{i}. Allora f ∈ I sse g divide f. Questo era già noto a Euclide circa 2300 anni fà.

Molti hanno tentato di estendere l’algoritmo di divisione al caso in più variabili. Solo nel 1965 Bruno Buchberger ha imboccato la strada buona introducendo la nozione di insiemi di generatori particolari di un ideale. Questi sono chiamati basi di Groebner dal nome del relatore di tesi di Buchberger.

Ordinamenti Monomiali

Sia R = k[x_{1}, …, x_{n}]. Un monomio in R ha la forma x^{α} = ∏_{j} x_{j}^{a_{j}}, ove α = (a_{1}, …, a_{n}) ∈ ℕ^{n}. Un ordinamento monomiale su R = k[x_{1}, …, x_{n}] è una relazione d’ordine ⪰ sui monomi (o su ℕ^{n}):

totale;

α ⪰ β implica α + γ ⪰ β + γ;

ogni sottoinsieme non vuoto di ℕ^{n} ammette un minimo (buon ordinamento).

Ad esempio

α ≻_{lex} β sse il primo elemento non nullo di α − β ∈ ℤ^{n} è positivo definisce l’ordinamento lessicografico. Si dimostra essere un ordinamento monomiale. Sia f = ∑_{α∈ℕ^{n}} a_{α}x^{α} un polinomio non nullo e ⪰ un ordinamento monomiale, allora:

il multigrado di f è multideg (f) = max (α ∈ ℕ^{n} : a_{α} ≠ 0); il coefficiente direttivo di f è LC(f) = a_{multideg (f)}; il monomio direttivo è LM(f) = x^{multideg (f)}; il termine direttivo di f è LT (f) = LC(f)LM(f).

Come nel caso in una variabile vale il seguente Algoritmo di divisione Dati f, f_{1}, …, f_{s} ∈ R esistono a_{i} e r tali che

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r,

ove multideg (f) ⪰ multideg (a_{i}f_{i}) e r = 0 oppure r è somma di monomi nessuno dei quali divisibile per LT (f_{i}).

Unicità e forma normale

Purtroppo per n > 1 l’algoritmo di divisione non risulta del tutto soddisfacente. Anzitutto r non è unico, ma dipende dall’ordine dei polinomi f_{1}, …, f_{s}. In particolare r = 0 in qualche ordine non assicura che r sia zero per ogni ordine.

Magma è in grado di calcolare r come funzione di f e della sequenza ordinata [f_{1}, …, f_{s}]. r viene detto la forma normale di f rispetto alla sequenza.

Ad esempio se f = xy^{2} − x, f_{1} = xy + 1, f_{2} = y^{2} − 1, allora NormalForm(f, (f_{1}, f_{2})) = −x−y, mentre NormalForm(f, (f_{2}, f_{1})) = 0.

Quindi l’algoritmo non può essere usato per risolvere il membership problem: f ∈ ⟨f_{1}, …, f_{s}⟩?

Basi di Groebner

Si fissi un ordinamento ⪰ in R, sia I ≠ 0 un ideale. Si definisce con LT (I) l’insieme dei termini direttivi di tutti gli elementi di I. Sia ⟨LT (I)⟩ l’ideale generato da LT (I).

Un insieme finito g_{1}, …, g_{t} di I viene detto una base di Groebner se ⟨LT (I)⟩ = ⟨LT (g_{i}) : i = 1, …, t⟩.

Teorema di Hilbert-Buchberger Ogni ideale I ≠ 0 di k[x_{1}, …, x_{n}] ammette una base di Groebner g_{1}, …, g_{t}. Inoltre I = ⟨g_{1}, …, g_{t}⟩.

Resto e basi di Groebner

Se si usa una base di Groebner per l’ideale viene ripristinata l’unicità del resto indipendentemente dall’ordine. In realtà questa condizione equivale ad essere una base di Groebner. In più r = 0 sse f ∈ I. Come costruire una base di Grobner? Dati f, g ∈ R sia α = multideg (f), β = multideg (g) e γ definito via γ_{i} = max (α_{i}, β_{i}). Si definisce l’S-polinomio tra f e g,

S(f, g) = \frac{x^{γ}}{LT (f)} f − \frac{x^{γ}}{LT (g)} g.

Criterio di Buchberger

La definizione di S-polinomio è motivata dal tentativo di costruire elementi di ⟨f, g⟩ con multigrado più piccolo di quelli di f, g. Vale il seguente Criterio di Buchberger: Sia G = {g_{1}, …, g_{t}} una base per l’ideale I. Allora G è una base di Groebner sse la forma normale di S(g_{i}, g_{j}) vale 0. Questo criterio è costruttivo ed è implementato in Magma in una versione molto efficiente dovuta a Faugère.

Syzygy

Sia F = (f_{1}, …, f_{s}) una sequenza ordinata di polinomi. Un syzygy (termine greco che significa giogo) sui termini direttivi di F è una s-pla S = (h_{1}, …, h_{s}) di polinomi tale che

_{j}^{∑} h_{j}LT (f_{j}) = 0.

Sia S(F) l’insieme di tutte le syzygy sui termini direttivi di F. Ovviamente S(F) è un R-sottomodulo di R^{s}.

Come conseguenza del Teorema della base di Hilbert esiste una base

finita di S(F). Sia e_{i} = (0, …, 0, 1^{i}, 0, …, 0) ∈ R^{s}, allora

S_{ij} = \frac{x^{γ}}{LT (f_{i})} e_{i} − \frac{x^{γ}}{LT (f_{j})} e_{j}

appartiene a S(F), ove γ è definito come sup (multideg (f_{i}), multideg (f_{j})). Il legame tra syzygy e basi di Grobner è dato da: Syzygy e S-polinomi: L’insieme delle syzygy S ∈ S(F) ammette come base (polinomiale) S_{ij}.

Il Teorema di Schreyer

Sia G = (g_{1}, …, g_{t}) una base di Groebner per qualche ideale I e sia S(G) l’insieme di syzygy su G. Allora per il criterio di Buchberger

\frac{x^{γ_{ij}}}{LT (g_{i})} g_{i} − \frac{x^{γ_{ij}}}{LT (g_{j})} g_{j} = _{u}^{∑} a_{iju}g_{u},

ove (γ_{ij})_{k} = max (multideg (g_{i})_{k}, multideg (g_{j})_{k}). Quindi τ_{ij} = \frac{x^{γij}}{LT (g_{i})} e_{i} − \frac{x^{γij}}{LT (g_{j})} e_{j} − ∑_{u} a_{iju}e_{u} ∈ S(G). Teorema di Schreyer: I τ_{ij} sono una base di Groebner per S(G).

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à?