dissabte, 19 de setembre de 2009

De Grups a Corbes el·líptiques [I] - Grups i Cossos

Benvinguts i benvingudes a un previsiblement llarg post sobre matemàtiques.

Espero que no se us indigesti massa.

Primer de tot, l'objectiu: Construir i entendre un "criptosistema" basat el corbes el·líptiques (ejem emparellaments bilineals, ejem) que, a més, sigui relativament eficient.


O sigui, que necessitem de matemàtiques per tal de construir-ho?

Primer de tot, necessitem saber què és un Grup.

I. Grup

Bé, aquesta és la part fàcil, un grup és un conjunt d'elements i una operació. Ja està, finito.

Direm G al conjunt d'elements del grup, i + a la operació. Així cal que es compleixin les següents especificacions:

  1. a + (b + c) = (a + b) + c per a tot a, b, c pertanyents a G
  2. Existeix un element, e, tal que a + e = e + a = a per a tot a pertanyent a G. Aquest e és l'element neutre del grup.
  3. Tot a pertanyent a G té un element invers, -a, tal que a + (-a) = (-a) + a = e

Bé, aqui un exemple ràpid: Els nombres enters, reals, imaginaris, etc... formen un grup sota la operació suma i el seu element neutre és el 0.

Podríem també afegir una característica adicional per tal de definir els grups Abelians:

  1. a + b = b + a per a tot a, b pertanyent a G. Aquesta característica es coneix amb el nom de conmutativitat.

Ara anem a definir un dels grups "especials". Un grup de nombres finits: Zn (Us heu d'imaginar la Z com aquella Z dels nombres enters tan guai, i la n com a un subindex).

Per fer això només ens cal definir el conjunt com tots els residus mòdul n. Què vol dir? Que per saber la correspondència d'un nombre a Z a Zn, només ens cal dividir-lo per n i agafar el residu.

Exemple, Z3:

0 => [0]
1 => [1]
2 => [2]
3 => [0]
4 => [1]
5 => [2]
25 => [1]
...

així tenim un grup amb només 3 elements: [0], [1] i [2]
[0] + [0] = [0]
[0] + [1] = [1]
[0] + [2] = [2]
[1] + [0] = [1]
[1] + [1] = [2]
[1] + [2] = 3 = [0]
[2] + [0] = [2]
[2] + [1] = 3 = [0]
[2] + [2] = 3 = [1]


II. Cossos:

Un cos (F,+,·) [F = conjunt d'elements, + i · = operacions) es defineix de la següent manera:
  1. (F,+) és un grup abelià.
  2. Sigui F* el conjunt F tret de l'element neutre respecte +. (F*,·) també és un grup abelià. Pensem en F* com els elements diferents de zero de F.
  3. a · (b + c) = a·b + a·c (propietat distribuitiva)
Qualsevol Zn amb n primer forma un cos. Si n no és primer, aleshores hi ha elements sense invers respecte la multiplicació i, per tant, no és un cos (Excepció al següent paràgraf).

Podem crear un cos finit de Zp^m (p^m hauria de ser un subíndex...) amb l'ajuda de polinomis.

Primer, agafem tots els polinomis amb coeficients a Zp (O sigui, amb coeficients menors a p). Després agafem un polinomi de grau m irreductible (que no es pugui expresar com a multiplicació de altres polinomis de Zp de grau igual o major que 1) i fem el módul com abans hem fet per Zn.

Si agafem, per exemple, el cos Z9 [Z3^2], tindrem els següents elements:
[0],[1],[2],[x],[x+1],[x+2],[2x],[2x+1],[2x+2]
9 en total. Per fer la operació de multiplicació necessitem un polinomi irreductible per fer el módul. x^2 + 1 servirà.

Ah si, notació: Zn[x] / f(x) per indicar el cos de polinomis amb coeficients a Zn i módul f(x). (Zn[x] vol dir l'anell de polinomis a Zn)

L'exemple de dalt seria Z3[x] / (x^2+1)

Detalls curioso-importants:
  1. Els cossos tenen una característica. És el nombre de vegades que et cal sumar un element a ell mateix per tal que dongui 0. A Zp^m la característica és p.
  2. Els cossos finits s'els hi pot fer un endorfisme (paraulota) una mica curiós que bé a ser f(a) => a^p. Si ho fas p vegades, torna a donar a. Bàsicament es pot fer servir de la següent manera: Si tu vols elevar un element a p (característica del cos), només et cal elevar cada x a p.
Z3[x] / (x^2+1)
(x+2)^3 = x^3 + 2·(x^0)^3 = x^3 + 2 = 2x + 2
(x+2)·(x+2)·(x+2) = (x^2 + x + 1)·(x+2) = (2+x+1)·(x+2) = x·(x+2) = x^2 + 2x = 2x + 2

2 comentaris:

  1. vale molt bé.... (això era l'ultim tema de fmd)
    espero la segona part i les elípticurves,,,,

    ResponElimina
  2. i m'estic tornant més borde que el rhisto mejide... així que, ves-te acostumant
    que m'agrada el sarcasme àcid injustificat.

    ResponElimina