Pages:
Author

Topic: curve ellittiche e algoritmo ECDSA - page 2. (Read 25659 times)

legendary
Activity: 1932
Merit: 2077
January 20, 2019, 03:53:10 AM
#65
Preferisco inserire in questo post dedicato tutte le seguenti considerazioni, che si possono considerare un ulteriore approfondimento di questa sezione che ho comunque riveduto e ampliato a sua volta.

In questo post aggiungo qualche dettaglio anche pratico di calcolo sugli elementi di Fp, il campo delle coordinate che può essere visto (come tutti i campi finiti) sia come gruppo additivo che come gruppo moltiplicativo (tolto lo zero).


Poichè nel nostro caso Fp = Zp (campo delle classi dei resti della divisione degli interi per p), si ha che:

a) Fp è un gruppo ciclico di ordine p rispetto all'operazione di addizione
b) Fp - {0} è un gruppo ciclico di ordine p -1 rispetto all'operazione di moltiplicazione (si può dimostrare)

quindi per

a) si ha che a+a+a+a+a+a... = a*p = 0 mod p per ogni a di Fp
b) si ha che a*a*a*a*a ........... = a^(p-1) = 1 mod p per ogni a di Fp - {0}

La seconda relazione è quella che ci interessa.

Già Fermat aveva dimostrato un risultato pressochè equivalente:

per ogni numero primo p è sempre vera la relazione a^p - a = multiplo di k, ovvero a^p = a mod p  (piccolo teorema di Fermat)
 


1) Visto che il campo finito Fp è un gruppo ciclico (rispetto all'operazione di moltiplicazione) di ordine p - 1, si può utilizzare la relazione precedente per calcolare l'inverso di un elemento a diverso da 1:

a^(p-1) = 1   mod p   (a^(ordine) = 1)

quindi

a^(p-1) * a^(-1) = 1 * a^(-1) =  a^(-1) mod p

Quindi a^(p-2) = a^(-1) mod p

Ad esempio per calcolare l'inverso di 4 in F_ 7 basta fare 4^(7-2)  = 2  mod 7  e infatti  4*2 = 1 mod 7 (effettivamente 2 è l'inverso di 4 in F_7).

Sia nella mia prima versione della libreria micro_ecdsa che nella libreria secp256k1 si utilizza questo metodo (ovviamente nella libreria secp256k1 c'è un'ottimizzazione per la quale si è riusciti a minimizzare il numero di moltiplicazioni necessarie per ottenere a^(p-2) ricorrendo agli elevamenti al quadrato, un po' come nel caso della moltiplicazione (addizione ripetuta) per uno scalare si utilizzano i raddoppi dei punti per fare meno addizioni possibili.


2)  E' possibile anche ricavare la radice quadrata di b = a^2.

Infatti se p = 3 mod 4 (come succede effettivamente nella secp256k1), allora p + 1 è un multiplo di 4, e quindi:

a^p = a   mod p
 
a^(p+1) = a^2    mod p

a^((p+1)/4) = a^1/2 = sqrt(a)  mod p

Code:
>>> p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

>>> p % 4
3


>>> a = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

>>> a1 = pow(a, (p+1)/4, p) #sqrt(b)
>>> print(hex(a1))
0xcb6dfbd6cdf31164bbeb3052460c1fa3f827f01d6e7fb5f69580cfb96560c16a

>>> (a1 * a1)-a  % p    #verifica
0

>>> a2 = p-a  #a2 = -a1  trovo l'altra radice
>>> print(hex(a2))
0x34920429320cee9b4414cfadb9f3e05c07d80fe291804a096a7f30459a9f3ac5

>>> (a2 * a2)-a  % p  #verifica
0

Questa è l'implementazione di questa funzione nella libreria secp256k1. In quella libreria quando ci si riferisce a un'operazione definita su un elemento del campo delle coordinate si usa la sillaba 'fe' = field element , quando invece ci si riferisce a un'operazione sui punti della curva si usa la sillaba 'ge' = group element come succede ad esempio qui nell'implementazione della funzione che somma due punti della curva.
legendary
Activity: 1932
Merit: 2077
January 18, 2019, 12:26:04 PM
#64
Avevo letto da qualche parte che la stessa cosa vale per altri tipi di anelli che non sono campi finiti, ad es. definendo:

Z'n = 0 U {a: 0 < a < n, MCD (a, n) = 1}

cioè anche con n che non è primo, se a ed n sono primi fra loro.


Z'p non so neanche se sia corretta come notazione, andavo un po' a memoria.


Trovata, intendevi questo (fonte: https://it.wikipedia.org/wiki/Gruppo_ciclico):

Quote
Gruppo delle unità

Le unità dell'anello Z/nZ  sono i numeri primi con n, ovvero i generatori del gruppo. Formano un gruppo con la moltiplicazione, di φ ( n )  elementi (vedi sopra), indicato generalmente come Zn^* .

Ad esempio, i gruppi Z6^*  = { 1 , 5 }  e Z8^*  = { 1 , 3 , 5 , 7 }  sono isomorfi rispettivamente a Z / 2 Z  e Z / 2 Z × Z / 2 Z.

In generale, Zn^*  è ciclico se e solo se n  è 2, 4 , p^k o 2 p^k  dove p  è un primo dispari e k ≥ 1.

In particolare, il gruppo Zp^* è ciclico con p − 1  elementi per ogni primo p. Più in generale, ogni sottogruppo finito del gruppo moltiplicativo di un campo è ciclico.

Io invece mi sono soffermato nella teoria di questo thread solo sui gruppi di cui si parla nell'ultima riga perchè il campo Fp della secp256k1 è esattamente di quella forma.
legendary
Activity: 1932
Merit: 2077
January 17, 2019, 03:04:47 PM
#63
Ho un'altra domanda... Immagino non sia un caso che il rislutato di "x^3+7 mod 11" siano tutti valori diversi, da cosa dipende?
se ho capito bene la tua domanda è:

perchè la funzione f definita da F_11 a F_11 in questo modo:

    F_11  -->   F_11

f:     x     -->   x^3 + 7

è iniettiva?

Risposta: questa funzione è iniettiva a seconda del valore di p in Fp (lo è nel caso di F_11, non lo è nel caso di Fp della secp256k1)



Una funzione f di A in B si dice iniettiva se

x1 != x2  --> f(x1) != f(x2)  per ogni coppia di valori x1, x2 in A

o equivalentemente se:

f(x1) = f(x2) --> x1 = x2  

Osservazione:

Supponiamo che f(x1) = f(x2), e cioè che  (x1)^3 + 7 = (x2)^3 + 7 mod 11, allora (x1)^3 = (x2)^3 mod 11 (per il primo principio di equivalenza delle equazioni).

Quindi ( x1 / x2 ) ^3 = 1 mod 11

Ora consideriamo l'equazione x^3 = 1 mod 11 (dove x = x1/x2). Quante soluzioni può avere?

Sicuramente ha come possibilità x = 1, ovvero x1 = x2. Quindi se l'equazione x^3 = 1 mod 11 ha come unica soluzione x = 1 allora la funzione f(x) = x^3 + 7 è iniettiva, altrimenti no.

Se infatti esistessero altre radici cubiche dell'unità, che chiameremo beta, ci sarebbero altre possibilità:

tipo beta^3 = 1 mod 11 (con beta diverso da 1) e quindi (x1/x2) = beta -->  x1 = beta * x2 mod 11 ed entrambi i valori x1 e x2 alla terza sarebbero uguali!

Ora si può dimostrare che se il numero primo 'p' di Fp è congruente a 1 mod 3 (ovvero se p = 1 mod 3) allora ci sono ben 3 diversi elementi x che vengono mappati nella stessa y (questa proprietà del campo delle coordinate induce una proprietà particolare nel gruppo dei punti che si costruiscono a partire da queste coordinate, si parla di endomorfismi, un legame particolare tra i punti della curva).

Questo è proprio il caso della p della secp256k1, quindi nel campo delle coordinate della curva utilizzata da Bitcoin esistono 3 numeri: 1, beta1, beta2 che elevati alla terza fanno 1 mod p, questo fa sì che per ogni possibile risultato y = x^3 + 7 mod p vi siano ben 3 valori di x possibili, detta in altri termini

se x --> y
allora anche

beta1*x --> y
beta2*x --> y

quindi i punti della curva secp256k1 si suddividono in gruppi da tre punti che condividono la stessa ordinata:

Code:
(x,y), (beta1*x, y), (beta2*x, y)

dove

beta1 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee #  (beta1^3 = 1 mod p)
beta2 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40 #  (beta2 = beta1^2, beta2^3 = 1 mod p)

sfruttare questa proprietà della curva accelera enormemente i calcoli (se l'obiettivo è generare il più velocemente possibile i punti della curva).

Nota bene:

11 non è congruente a 1 mod 3 (11 = 2 mod 3), quindi non può avere sottogruppi di ordine 3, e di sicuro non può avere allora un numero a diverso da 1 tale che a^3 = 1 mod 11.  In sostanza un campo di p elementi è un gruppo ciclico rispetto all'operazione di moltiplicazione di ordine p-1 (ha solo p-1 elementi perchè bisogna togliere lo zero), nel nostro caso 10.

Questo vuol dire che i possibili sottogruppi di {1,2,3,4,5,6,7,8,9,10} (guarda qui per il concetto di ordine e di sottogruppo)  possono avere per il teorema di Lagrange solo ordine un divisore di 10, ovvero o 1 o 2 o 5.  In un sottogruppo di ordine 2, deve esistere un elemento a != 1 tale che a^2 = 1 mod 11, in un sottogruppo di ordine 5 (se c'è) ci devono essere degli elementi b != 0 tali che b^5 = 1 mod 11.
Non potendoci essere un sottogruppo di ordine 3 (perchè 3 non divide 10), non ci può essere quindi un elemento beta diverso da 1 tale che beta^3 = 1 mod 11.

Se provi invece con F_7 (o con F_19 o con altri valori di p primo congruenti a 1 mod 3), poichè 7 = 1 mod 3 (ovvero 7-1 è un multiplo di 3) in F_7 può esserci un sottogruppo di ordine 3 e quindi un paio di elementi diversi da 1 di ordine 3 (ci può essere cioè un sottoinsieme di F_7 formato da 3 elementi = {1, beta1, beta2} che elevati alla terza fanno 1).

Infatti (tutti i calcoli sono fatti modulo 7 in F_7):

x     x^3    x^3 + 7    y=sqrt(x^3 + 7)

0      0            0                        0
1     1            1                     1 o 6
2     1            1                     1 o 6
4     1            1                     1 o 6
3      6            6                 non esiste
5      6            6                 non esiste  
6      6            6                 non esiste

quindi l'insieme E(F_7), ovvero la curva (il gruppo) formata da tutti i punti le cui coordinate nel campo F_7 soddisfano l'equazione y^2 = x^3 + 7 mod 7 é

E(F_7) = { (0,0), (1,1), (2,1), (4,1), (1,6), (2,6), (4,6) } U {punto all'infinito}

notare la doppia "simmetria"di questa curva:

1) rispetto all'asse x  (le y vanno a "coppie", 1 e 6 sono come 1 e -1, sono valori simmetrici rispetto all'asse x, questo deriva dal termine y^2)

2) rispetto ai singoli valori di y (le x associate alla stessa y sono terne di x legate tra loro dalle radici cubiche dell'unità, questo deriva dal termine x^3 dell'equazione e dal particolare valore di p)

Ho aggiunto in fondo a questo post il calcolo del numero distinto dei valori assunti dalle coordinate x e dalle coordinate y dei punti della curva, calcolo che si basa proprio su questa doppia simmetria.
sr. member
Activity: 292
Merit: 250
January 17, 2019, 04:55:18 AM
#62
Addizione tra 2 punti in E(F_11): esempio


Vediamo di costruire come esempio il gruppo E(F_11), cioè il gruppo di elementi della curva di equazione y^2=x^3+7 a coordinate in F_11.

Proviamo tutti i casi possibili:

x   x^3+7   x^3+7 mod 11    Sqrt(x^3+7) mod 11   
0   7                   7      
1   8                   8      
2   15                   4                     2 o 9        2 o -2   --> (2,2), (2,-2)
3   34                   1                    1 o 10      1 o -1  -->  (3,1), (3, -1)
4   71                   5                    4 o 7        4 o -4  -->  (4,4),(4,-4)        
5   132                   0                        0               0      -->  (5,0)
6   223                   3                    5 o 6        5 o -5   -->  (6,5),(6,-5)
7   350                   9                    3 o 8        3 o -3   --> (7,3),(7,-3)
8   519                   2      
9   736                  10      
10   1007                  6      




Mi perdo nel passaggio dalla terza alla quarta colonna, il mod11 viene fatto sul sqrt? Non capisco come vengono estrapolati i valori.

mod 11 viene applicato al risultato della radice quadrata (in generale viene applicato al risultato di qualsiasi operazione quando questo risultato supera 11).

Prendiamo per esempio la riga del 2:

x = 2 --> x^3 = 8 --> x^3 + 7 = 8 + 7 = 15 = 4 mod 11 --> sqrt(4) = 2 o 9 (perchè 2*2 = 4 ma anche 9*9=81 = 4 mod 11) lascia perdere i valori negativi (semplicemente 9 = -2 mod 11, li ho inseriti solo per far vedere che le radici quadrate sono sempre opposte, anche in questi insiemi strani; anche con i numeri normali se ti dico x^2 = 4, chi è x? Tu rispondi: 2 o -2)

Ho un'altra domanda... Immagino non sia un caso che il rislutato di "x^3+7 mod 11" siano tutti valori diversi, da cosa dipende?
sr. member
Activity: 292
Merit: 250
January 17, 2019, 02:39:34 AM
#61



 sqrt(4) = 2 o 9 (perchè 2*2 = 4 ma anche 9*9=81 = 4 mod 11)

ecco il motivo, scusate ma ho solo qualche reminiscenza universitaria...
legendary
Activity: 1932
Merit: 2077
January 16, 2019, 04:48:58 PM
#60
Addizione tra 2 punti in E(F_11): esempio


Vediamo di costruire come esempio il gruppo E(F_11), cioè il gruppo di elementi della curva di equazione y^2=x^3+7 a coordinate in F_11.

Proviamo tutti i casi possibili:

x   x^3+7   x^3+7 mod 11    Sqrt(x^3+7) mod 11   
0   7                   7      
1   8                   8      
2   15                   4                     2 o 9        2 o -2   --> (2,2), (2,-2)
3   34                   1                    1 o 10      1 o -1  -->  (3,1), (3, -1)
4   71                   5                    4 o 7        4 o -4  -->  (4,4),(4,-4)        
5   132                   0                        0               0      -->  (5,0)
6   223                   3                    5 o 6        5 o -5   -->  (6,5),(6,-5)
7   350                   9                    3 o 8        3 o -3   --> (7,3),(7,-3)
8   519                   2      
9   736                  10      
10   1007                  6      




Mi perdo nel passaggio dalla terza alla quarta colonna, il mod11 viene fatto sul sqrt? Non capisco come vengono estrapolati i valori.

mod 11 viene applicato al risultato della radice quadrata (in generale viene applicato al risultato di qualsiasi operazione quando questo risultato supera 11).

Prendiamo per esempio la riga del 2:

x = 2 --> x^3 = 8 --> x^3 + 7 = 8 + 7 = 15 = 4 mod 11 --> sqrt(4) = 2 o 9 (perchè 2*2 = 4 ma anche 9*9=81 = 4 mod 11) lascia perdere i valori negativi (semplicemente 9 = -2 mod 11, li ho inseriti solo per far vedere che le radici quadrate sono sempre opposte, anche in questi insiemi strani; anche con i numeri normali se ti dico x^2 = 4, chi è x? Tu rispondi: 2 o -2)
legendary
Activity: 1932
Merit: 2077
January 16, 2019, 04:27:58 PM
#59
...
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie
Vedi: https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
e anche https://en.bitcoin.it/wiki/Address

Grazie, ma manca proprio il calcolo della chiave pubblica (passaggio da 0 a 1)

L'ho spiegato qui con un codice python applicato a una chiave reale:

https://bitcointalksearch.org/topic/m.48983013

nella libreria micro_ecdsa la funzione che effettua il passaggio dalla chiave privata alla chiave pubblica è la funzione mul che moltiplica il generatore G per una chiave privata d (uno scalare) e restituisce la chiave pubblica corrispondente d*G. Quindi per trovare la chiave pubblica relativa a 'd' basta chiamare la funzione mul(d,Gx, Gy), dove Gx e Gy sono le coordinate del punto G scelto dalla SEC. Ti consiglio di scaricarti lo script pyhton e provare a generare delle chiavi pubbliche a partire dalle chiavi private. Lascia stare gli indirizzi, quelli vengono dopo.

La funzione 'mul' invece di fare banalmente d*G = G+G+G+.... un numero d di volte (essendo d dell'ordine di 2^256 ci impiegherebbe un'eternità) crea tutte le potenze di 2 tipo 2*G, 4*G, 8*G, 16*G, 32*G, ... , 2^255*G e poi somma tra loro quelle che servono. Ho anche fatto un esempio concreto con una chiave piccola tipo 25 = 11001 in base 2. In quel caso basta generare 1G, 2G, 4G, 8G, 16G e poi sommare rispettivamente: 16G + 8G +1G (che corrispondono ai 3 'uno' della sequenza 11001) per ottenere 25G (che è la chiave pubblica relativa alla chiave privata 25).  Nella libreria ci sono anche la formula per l'addizione di due punti e la formula per il raddoppio di un punto che sono i mattoncini base per la funzione mul.

EDIT: altri link utili:

https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3

legendary
Activity: 2506
Merit: 1120
January 16, 2019, 06:42:41 AM
#58
...
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie
Vedi: https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
e anche https://en.bitcoin.it/wiki/Address

Grazie, ma manca proprio il calcolo della chiave pubblica (passaggio da 0 a 1)
A memoria, certo di sbagliarmi, prego correggermi.
prv=privete key
pub=public key
G= generatore

pub=G+G+G ...+G=prv*G (o G*prv se commutativo, non ricordo).
sr. member
Activity: 292
Merit: 250
January 16, 2019, 03:54:24 AM
#57
...
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie
Vedi: https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
e anche https://en.bitcoin.it/wiki/Address

Grazie, ma manca proprio il calcolo della chiave pubblica (passaggio da 0 a 1)
sr. member
Activity: 292
Merit: 250
January 16, 2019, 03:52:53 AM
#56
Per molti sarà banale, per uno come me che non è del mestiere ho trovato questo materiale molto utile. Vedere il codice a volte aiuta a capire la teoria  Grin :

https://rosettacode.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

https://rosettacode.org/wiki/RSA_code

https://rosettacode.org/wiki/Bitcoin/public_point_to_address

legendary
Activity: 2506
Merit: 1120
January 16, 2019, 03:51:58 AM
#55
...
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie
Vedi: https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
e anche https://en.bitcoin.it/wiki/Address
sr. member
Activity: 292
Merit: 250
January 16, 2019, 03:21:42 AM
#54
Addizione tra 2 punti in E(F_11): esempio


Vediamo di costruire come esempio il gruppo E(F_11), cioè il gruppo di elementi della curva di equazione y^2=x^3+7 a coordinate in F_11.

Proviamo tutti i casi possibili:

x   x^3+7   x^3+7 mod 11    Sqrt(x^3+7) mod 11   
0   7                   7      
1   8                   8      
2   15                   4                     2 o 9        2 o -2   --> (2,2), (2,-2)
3   34                   1                    1 o 10      1 o -1  -->  (3,1), (3, -1)
4   71                   5                    4 o 7        4 o -4  -->  (4,4),(4,-4)        
5   132                   0                        0               0      -->  (5,0)
6   223                   3                    5 o 6        5 o -5   -->  (6,5),(6,-5)
7   350                   9                    3 o 8        3 o -3   --> (7,3),(7,-3)
8   519                   2      
9   736                  10      
10   1007                  6      



Mi perdo nel passaggio dalla terza alla quarta colonna, il mod11 viene fatto sul sqrt? Non capisco come vengono estrapolati i valori.
Altra domanda...Qualcuno è così gentile da scrivere i vari passaggi da privkey a pubkey con una privkey reale? grazie
legendary
Activity: 1932
Merit: 2077
January 11, 2019, 01:39:50 PM
#53
Sono un po OT, ma volevo sapere: partendo da un indirizzo, posso sapere se è stato generato a partire da una pubkey compressa o meno? Grazie

No, non si può sapere. Nel momento in cui passi la stringa '04' + 'X' + 'Y' alla funzione ripemd160(sha256()) il risultato è solo una stringa di 160 bit, lo stesso otterresti se mettessi in input '02' + 'X'.

Di più, la stringa di 160 bit (l'address è sostanzialmente un numero di 160 bit presentato all'essere umano in base 58) potrebbe essere l'impronta di qualsiasi cosa. Ad esempio, se consideri la frase 'Ciao come stai' e la dai in pasto così:  ripemd160(sha256('Ciao come stai')) ottieni un numero di 160 bit, se ora passi la sua codifica in base 58 a qualcuno perchè lui ti paghi su quell'indirizzo, la transazione avverrà con destinazione quell'indirizzo, poichè non è possibile dall'indirizzo stesso ricavare nulla su come sia stato effettivamente generato (se non che la sua codifica in base 58 è stata ottenuta aggiungendo il byte 00 all'inizio della stringa di 160 bit).
Quindi in tal caso nessuno potrebbe smuovere più quei fondi.
sr. member
Activity: 292
Merit: 250
January 11, 2019, 05:22:41 AM
#52
Sono un po OT, ma volevo sapere: partendo da un indirizzo, posso sapere se è stato generato a partire da una pubkey compressa o meno? Grazie
legendary
Activity: 3808
Merit: 2044
January 01, 2019, 06:13:01 PM
#51
mi sono ricordato che ai miei tempi c'era un corso di Algebra tra quelli opzionali, ma non lo sceglieva quasi nessuno, me compreso...
Avevamo tutti un corso di Geometria al primo anno, con solo una parte di algebra lineare sulle matrici. Devo dire che a volte mi pesa avere di queste lacune.

Non è mai troppo tardi per mettersi a studiare, l'importante è che ti interessi veramente, ormai di materiale in rete ce n'è in abbondanza.

già, di materiale senz'altro, ma di tempo no purtroppo Sad
legendary
Activity: 1932
Merit: 2077
January 01, 2019, 05:26:56 PM
#50
mi sono ricordato che ai miei tempi c'era un corso di Algebra tra quelli opzionali, ma non lo sceglieva quasi nessuno, me compreso...
Avevamo tutti un corso di Geometria al primo anno, con solo una parte di algebra lineare sulle matrici. Devo dire che a volte mi pesa avere di queste lacune.

Non è mai troppo tardi per mettersi a studiare, l'importante è che ti interessi veramente, ormai di materiale in rete ce n'è in abbondanza.
legendary
Activity: 3808
Merit: 2044
January 01, 2019, 05:11:09 PM
#49

ok ti ringrazio, mi mancava quel tassello dell'identità di Bezout!
Z'p non so neanche se sia corretta come notazione, andavo un po' a memoria.

Per curiosità, che corso è quello del testo? Tu insegni questo all'università?

Direi un classico corso di Algebra. Certo era solo un riferimento, visto che mi hai chiesto dei campi finiti ho fatto una rapida ricerca con google.  Smiley

Io insegno matematica al liceo, non all'università.

mi sono ricordato che ai miei tempi c'era un corso di Algebra tra quelli opzionali, ma non lo sceglieva quasi nessuno, me compreso...
Avevamo tutti un corso di Geometria al primo anno, con solo una parte di algebra lineare sulle matrici. Devo dire che a volte mi pesa avere di queste lacune.
legendary
Activity: 1932
Merit: 2077
January 01, 2019, 05:04:51 PM
#48

ok ti ringrazio, mi mancava quel tassello dell'identità di Bezout!
Z'p non so neanche se sia corretta come notazione, andavo un po' a memoria.

Per curiosità, che corso è quello del testo? Tu insegni questo all'università?

Direi un classico corso di Algebra. Certo era solo un riferimento, visto che mi hai chiesto dei campi finiti ho fatto una rapida ricerca con google.  Smiley

Io insegno matematica al liceo, non all'università.
legendary
Activity: 3808
Merit: 2044
January 01, 2019, 04:50:30 PM
#47
ok ma qui è invertito l'ordine: è appunto la parte in grassetto che non capisco come si dimostra. Come dimostri che per ogni a < p, esiste b < p t.c. a x b = 1?

Infatti ho solo dimostrato che Zn non è un campo quando n non è primo.

Dimostrare che un insieme è un campo è ovviamente più laborioso (dimostrazione completa , da pag. 35 a pag. 46!), devi infatti dimostrare che le operazioni di somma e moltiplicazioni sono ben definite, godono delle proprietà associative e commutative e che tutti gli elementi hanno l'opposto e il reciproco.

Come hai ben osservato, la parte più interessante è l'ultima, ovvero dimostrare che ogni elemento (a parte lo 0) di Zp ha sempre un inverso.


Premessa:

Identità di Bezout: dati a e b numeri interi relativi diversi da 0 e detto d = MCD(a,b), allora esistono x,y interi tali che

a*x + b*y = d

x e y non sono unici, per trovarne un paio basta applicare l'algoritmo di Euclide per la determinazione del MCD (ce ne sono in realtà  infinite coppie).

Supponiamo vera l'identità di Bezout (vedi pag. 45 del link), vediamo che x e y non sono unici.

Notiamo infatti che a*b + b*(-a) = 0, quindi k * [a*b + b*(-a)] = 0 per ogni k intero

da ciò segue che per ogni k intero, a*(b*k) + b(-a*k) = 0 quindi x = b*k e y = -a*k  possono assumere infiniti valori.



Teorema: se p é primo allora ogni elemento diverso da 0 di Zp ha un inverso in Zp

Sia a un numero diverso da 0 di Zp, con p primo.

Poichè p è primo, MCD(a,p)=1

Per l'identità di Bezout esistono x e y interi tali che:

a*x + p*y = 1

ovvero a*x = 1 -y*p  ovvero a*x  = 1 mod p (a*x = 1 mod p significa che esiste q tale che a*x= q*p + 1)

quindi x è l'inverso di a mod p
CVD

Ti consiglio caldamente la lettura delle pagine dalla 42 alla 46, spiegano bene la questione a partire dal concetto di divisore, di MCD, identità di Bezout e teorema su Zp.


Avevo letto da qualche parte che la stessa cosa vale per altri tipi di anelli che non sono campi finiti, ad es. definendo:

Z'n = 0 U {a: 0 < a < n, MCD (a, n) = 1}

cioè anche con n che non è primo, se a ed n sono primi fra loro.

Penso che dalla dimostrazione che ti ho dato ora questo punto sia diventato chiaro.

Ultima osservazione, bisognerebbe stare attenti a come sono definiti gli elementi degli insiemi in algebra, io ho utilizzato una notazione 'leggera' per cui Zp = { 0, 1, 2, ...., n-1} mentre in realtà bisognerebbe scrivere Zp = { [ 0], [1], [2], ...., [n-1]} perchè gli elementi di Zp sono le classi di congruenza modulo n, penso che anche l'insieme Z'n di cui parli tu sia la stessa cosa, altrimenti non è chiaro neanche come è definita l'addizione e la moltiplicazione tra elementi.

Detta in altri termini, Zp = { 0, 1, 2, ...., n-1} NON è un campo con le usuali operazioni di addizioni e moltiplicazione!
Invece Zp = { [ 0], [1], [2], ...., [n-1]} lo è, una volta definite le operazioni + e * sui suoi particolari elementi.

Ad esempio Z'6 = {[ 0], [1], [5]} ( Z'6 ha 3 elementi, è isomorfo quindi a Z3 = {[ 0], [1], [2]} )

dove
[ 0]  * [ 0] = [ 0]
[ 0]  * [1] = [ 0]
[ 0]  * [5] = [ 0]
[ 1]  * [ 0] = [ 0]
[ 1]  * [1] = [ 1]
[ 1]  * [5] = [ 5]
[ 5]  * [ 0] = [ 0]
[ 5]  * [1] = [ 5]
[ 5]  * [5] = [ 1]

ok ti ringrazio, mi mancava quel tassello dell'identità di Bezout!
Z'p non so neanche se sia corretta come notazione, andavo un po' a memoria.

Per curiosità, che corso è quello del testo? Tu insegni questo all'università?
EDIT: vedo nel link Geometria e Algebra, ma non so se l'hai segnalato solo come riferimento
legendary
Activity: 1932
Merit: 2077
January 01, 2019, 03:08:55 PM
#46
ok ma qui è invertito l'ordine: è appunto la parte in grassetto che non capisco come si dimostra. Come dimostri che per ogni a < p, esiste b < p t.c. a x b = 1?

Infatti ho solo dimostrato che Zn non è un campo quando n non è primo.

Dimostrare che un insieme è un campo è ovviamente più laborioso (dimostrazione completa , da pag. 35 a pag. 46!), devi infatti dimostrare che le operazioni di somma e moltiplicazioni sono ben definite, godono delle proprietà associative e commutative e che tutti gli elementi hanno l'opposto e il reciproco (in sostanza che sono definite implicitamente anche le operazioni di sottrazione e divisione per un numero diverso da zero).

Come hai ben osservato, la parte più interessante è l'ultima, ovvero dimostrare che ogni elemento (a parte lo 0) di Zp ha sempre un inverso.


Premessa:

Identità di Bezout: dati a e b numeri interi relativi diversi da 0 e detto d = MCD(a,b), allora esistono x,y interi tali che

a*x + b*y = d

x e y non sono unici, per trovarne un paio basta applicare l'algoritmo di Euclide per la determinazione del MCD (ce ne sono in realtà  infinite coppie).

Supponiamo vera l'identità di Bezout (vedi pag. 45 del link), vediamo che x e y non sono unici.

Notiamo infatti che a*b + b*(-a) = 0, quindi k * [a*b + b*(-a)] = 0 per ogni k intero

da ciò segue che per ogni k intero, a*(b*k) + b(-a*k) = 0 quindi

0 + a*x + b*y = d ->  a*(b*k) + b(-a*k) + a*x + b*y = d

da cui si ricava che x' = b*k + x    e   y' = -a*k + y possono assumere infiniti valori.



Teorema: se p é primo allora ogni elemento diverso da 0 di Zp ha un inverso in Zp

Sia a un numero diverso da 0 di Zp, con p primo.

Poichè p è primo, MCD(a,p)=1

Per l'identità di Bezout esistono x e y interi tali che:

a*x + p*y = 1

ovvero a*x = 1 -y*p  ovvero a*x  = 1 mod p (a*x = 1 mod p significa che esiste q intero tale che a*x= q*p + 1)

quindi x è l'inverso di a mod p
CVD

Ti consiglio caldamente la lettura delle pagine dalla 42 alla 46, spiegano bene la questione a partire dal concetto di divisore, di MCD, identità di Bezout e teorema su Zp.


Avevo letto da qualche parte che la stessa cosa vale per altri tipi di anelli che non sono campi finiti, ad es. definendo:

Z'n = 0 U {a: 0 < a < n, MCD (a, n) = 1}

cioè anche con n che non è primo, se a ed n sono primi fra loro.

Penso che dalla dimostrazione che ti ho dato ora questo punto sia diventato chiaro.

Ultima osservazione, bisognerebbe stare attenti a come sono definiti gli elementi degli insiemi in algebra, io ho utilizzato una notazione 'leggera' per cui Zp = { 0, 1, 2, ...., n-1} mentre in realtà bisognerebbe scrivere Zp = { [ 0], [1], [2], ...., [n-1]} perchè gli elementi di Zp sono le classi di congruenza modulo n, penso che anche l'insieme Z'n di cui parli tu sia la stessa cosa, altrimenti non è chiaro neanche come è definita l'addizione e la moltiplicazione tra elementi.

Detta in altri termini, Zp = { 0, 1, 2, ...., n-1} NON è un campo con le usuali operazioni di addizioni e moltiplicazione!
Invece Zp = { [ 0], [1], [2], ...., [n-1]} lo è, una volta definite le operazioni + e * sui suoi particolari elementi.

Ad esempio Z'6 = {[ 0], [1], [5]} ( Z'6 ha 3 elementi, è isomorfo quindi a Z3 = {[ 0], [1], [2]} ) (per fare i calcoli basta sostituire [5] con [2])

dove

[ 0]  * [ 0] = [ 0]                [ 0]  +  [ 0] = [ 0]
[ 0]  * [ 1] = [ 0]                [ 0]  +  [ 1] = [ 1]
[ 0]  * [ 5] = [ 0]                [ 0]  +  [ 5] = [ 5]
[ 1]  * [ 0] = [ 0]                [ 1]  +  [ 0] = [ 1]
[ 1]  * [ 1] = [ 1]                [ 1]  +  [ 1] = [ 5]
[ 1]  * [ 5] = [ 5]                [ 1]  +  [ 5] = [ 0]
[ 5]  * [ 0] = [ 0]                [ 5]  +  [ 0] = [ 5]
[ 5]  * [ 1] = [ 5]                [ 5]  +  [ 1] = [ 0]
[ 5]  * [ 5] = [ 1]                [ 5]  +  [ 5] = [ 1]
Pages:
Jump to: