Quote from: il_minatore on January 17, 2019, 09:55:18 AM

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.