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

Frase per la prosperitat

Los únicos enemigos de las lenguas son aquellos que las prohiben o las imponen.
- Mariano Rajoy, 19/9/2009
Míting a Catalunya


Un dia ens adonem que la incapacitat d'aquesta penya no és la de veure més enllà dels seus nassos, sinó ben al contrari, veure que fan ells mateixos.

dimarts, 15 de setembre de 2009

Despropósit democràtic

Avui, mirant l'APM, he recordat en quin país visc.

Primer de tot he d'aclarir que estic força orgullós de l'Estat Espanyol en general, especialment com a bon lloc on viure, després d'haver rondat per quasi tota Europa.

Ara bé, aquí, en aquest Estat, hi ha una profunda confusió en els termes de què és la democrácia.

Aquest no és un post de democràcia si, democràcia no. Ni un post amb grans afirmacions politico-socials. Aquest és simplement un post per assanyalar un fet:

Mitja espanya creu que preguntar la opinió als ciutadans és antidemocràtic.

És així, simple pla i clar. I tothom n'hauria de fer una lectura correcta d'aquest fet, i senyalo sobretot i especialment al PSC. He d'admetre que tenia certa esperança sobre el PSC, ja que últimament s'està comportant d'una manera que em sorprén positivament, malgrat això continua tenint certs deures que, encara que puguin ser-lis incómodes, els hi pesen.

I em refereixo a l'esforç que fan uns i altres al dir que és una consulta inútil i sense conseqüències. Bé, aixó el temps ho dirà. Seguiran altres municipis el referent d'Arenys? Hi haurá algun dia en el qual celebrem que el 13/9/9 es va obrir una petita esquerda que va arribar a cert lloc?

Sé que encara és d'hora, però que sigui només per fastidiar: Que aquells que temin veure España trencada, els hi entri el "cangueli" cada vegada més profund i, sobretot, amb més raó.

dissabte, 12 de setembre de 2009

Sad, but true



Dear Peter Wiggin: This letter is to inform you that you have received enough upvotes on your reddit comments to become president of the world. Please be at the UN tomorrow at 8:00 sharp.

dimarts, 1 de setembre de 2009

Demostenes' nades d'olla XXXVIII

Tots sóm John Travolta [Excepte per lo de cienciologia...]