Puncte:3

Distingerea punctelor în curbe eliptice peste câmpuri de extensie binare folosind Trace

drapel lu

Lăsa $E$ fie o curbă eliptică $^2 + xy â¡ ^3+^2+$ (o curbă Weierstrass) (în acest caz, cu caracteristica 2) peste un câmp de extensie binar $(2^{m})$ cu construirea polinomului $()$ fi un polinom ireductibil, primitiv $GF(2)$, si lasa $P(x_p,y_p)$ fi un punct pe curbă.

Am văzut diverse implementări și discuții (cum ar fi acest răspuns în partea de jos) menționați aceste puncte $P$ poate fi distins cu funcția de urmărire a câmpului și că „se poate arăta că pentru punctele din subgrupul curbei de ordin prim, urma lui $x_p$ coordonata trebuie să fie egală cu urma lui $a$ din ecuația curbei eliptice", adică

$Tr(x_p) = \begin{cases} \mbox{a,} & \mbox{if } P \in E \ \mbox{1,} & \mbox{otherwise} \end{cases}$

Totuși, nu găsesc nicio bibliografie relevantă care să explice clar de ce acest lucru este valabil din perspectivă matematică. Poate cineva să ofere teoria relevantă din spatele acestui lucru? De asemenea, care sunt restricțiile și condițiile de bază necesare pentru ca Trace să poată reflecta dacă un punct se află sau nu pe curbă?

Multumesc pentru timpul acordat,

poncho avatar
drapel my
De fapt, ecuațiile Weierstrass pentru curbele caracteristice chiar sunt diferite
G. Stergiopoulos avatar
drapel lu
Am modificat ecuația pentru a se potrivi pentru curbele caracteristice 2, mulțumesc.
kelalaka avatar
drapel in
[O analiză a formulelor eficiente pentru eliptică Adăugarea punctelor de curbă peste câmpuri de extensie binare](https://sci-hub.st/https://doi.org/10.1109/CISS.2011.5766253)
Puncte:3
drapel us

Iată ce mi-am putut da seama pe baza notelor curbei eliptice de aici: https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html, dat un punct $P=(x_1,y_1)$ și o curbă definită de $$Y^2+a_1XY = X^3+a_2X^2+a_4X+a_6$$ apoi cel $x$-coordonata de $2P$ este dat de

$$x_2 = \lambda^2 + a_1\lambda - a_2 - 2x_1$$

In cazul tau, $a_1=1$. De asemenea $2x_1=0$ deoarece câmpul are caracteristica 2 și putem comuta toate semnele minus la semnele plus din același motiv. Astfel, formula devine:

$$x_2=\lambda^2 + \lambda + a$$

Urma de $x_2$ va fi $\text{tr}(\lambda^2) + \text{tr}(\lambda)+\text{tr}(a)$. De cand $\text{tr}(\lambda^2) = \text{tr}(\lambda)$, acest lucru înseamnă $\text{tr}(x)=\text{tr}(a)$. Astfel, pentru orice punct $P$ pe curbă, dacă $P=2Q$ pentru unii $Q$, apoi urma de $P$lui $x$-coordonata este egală cu urma lui $a$.

Dacă avem un subgrup ciclic cu ordine impară $n$, atunci $2$ are ceva invers $2^{-1}$ modulo $n$. Astfel, pornind din orice punct $P$ în acest subgrup, știm că $2(2^{-1}P)=P$, deci există un punct $Q=2^{-1}P$ astfel încât $P=2Q$, și astfel ei $x$-coordonata are aceeasi urma ca $a$.

În general, fiecare element al subgrupului $2E(GF(2^m)) = \{x+x : x\in E(GF(2^m))\}$ toate vor avea aceeași urmă.

Dar alte puncte? Nu știu. Ar putea fi că punctele $P$ care nu sunt egale $2Q$ pentru orice $Q$ mai poate avea urmă egală cu $\text{tr}(a)$, sau poate puteți demonstra că nu pot.

knaccc avatar
drapel es
Cum se calculează tr (coordonata x)?
G. Stergiopoulos avatar
drapel lu
Bună găsire @SamJaques. Voi arunca o privire extinsă în weekend și voi reveni la tine despre asta.
G. Stergiopoulos avatar
drapel lu
@knaccc $Tr(x)$ peste un câmp de extensie binar poate fi calculat ca sumă a conjugatelor reprezentării polinomiale a elementului (caz în care, $x$).În ceea ce privește curbele eliptice, trace are de-a face cu Frobenius și poate fi calculată într-un mod similar (deși nu identic). Verificați asta: https://www.math.uci.edu/~asilverb/bibliography/compress.pdf
kelalaka avatar
drapel in
[O analiză a formulelor eficiente pentru eliptică Adăugarea punctelor de curbă peste câmpuri de extensie binare](https://sci-hub.st/https://doi.org/10.1109/CISS.2011.5766253)
kelalaka avatar
drapel in
dacă un element generează un grup de ordine impar, atunci toate elementele sunt duble față de altele. De fapt. avem nevoie de mai mult decat ciudat, ordine primara. Secțiunea H, a lucrării de mai sus, are o scriere mai bună și menționează chiar și cazul în mod explicit!
Sam Jaques avatar
drapel us
Ordinea impară este suficientă pentru ca fiecare punct să fie dublu față de celălalt. Nu am putut găsi nimic în secțiunea H care să acopere cazul punctelor de ordine completă într-un subgrup de ordine egală.
G. Stergiopoulos avatar
drapel lu
Acest lucru acoperă în mod adecvat toate situațiile posibile pentru comenzile impare și, după cum a afirmat @SameJaques, curbele de ordine par în ipotezele menționate mai sus. Mulțumiri! [continuare]
G. Stergiopoulos avatar
drapel lu
[continuare] Am încercat să transfer acest lucru în curbe peste câmpuri prime, dar, deoarece $tr$ nu este binar și nu are caracteristica = 2, nu sunt sigur dacă acest lucru se generalizează într-un fel peste câmpurile prime.Ceva gânduri?

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.