înregistrare Logare
Puncte:0
mini minions avatar Crypto

Cum se calculează inversul funcției $x^3$ în $\mathbb{F}_{2^n}$

drapel mx
mini minions

Cum se calculează inversul funcției $x^3$ în $\mathbb{F}_{2^n}$?, Orice monom $x^d$ este o permutare în domeniu $\mathbb{F}_{2^n}$ dacă $gdc(d,2^{n}-1)=1$,De ce?

59
0 + 0
kelalaka avatar
drapel in
kelalaka
Bun venit la [cryptography.se]. $x^3$ nu este o funcție, ci mai degrabă o reprezentare polinomială a elementelor câmpului $\mathbb F_{2^2}$. Modalitatea implicită de a găsi inversul este utilizarea extins-gcd pe polinoame. Dacă aveți nevoie doar de rezultat, utilizați SageMath. Aceasta este întrebarea HW?
0
Răspunde
poncho avatar
drapel my
poncho
@kelalaka: de fapt, cred că prin $x^3$, el vorbește despre funcția $F(z) = z \cdot z \cdot z$, care este bine definită pe orice câmp, cum ar fi $\mathbb{ Z}_{2^{n}}$.
1
Răspunde
kelalaka avatar
drapel in
kelalaka
@poncho interpretarea ta este mai bună decât a mea.
0
Răspunde
Puncte:3
Daniel S avatar Crypto
drapel ru
Daniel S

Ordinea grupului multiplicativ al $\mathbb F_{2^n}$ este $2^n-1$. Dacă 3 este coprim cu $2^n-1$ atunci există $d\în [1,\ldots,2^n=1]$ astfel încât $3d\equiv 1\pmod{2^n-1}$. Putem găsi un astfel de $d$ folosind algoritmul euclidian extins.

Funcția activată $\mathbb F_{2^n}$ $y\mapsto y^d$ este atunci inversul hărții $x\mapsto x^3$ întrucât pentru $x\in\mathbb F_{2^n}^\times$ avem $(x^3)^d=x^{3d}=x^1$ (cazul $x=0$ este evident).

Aceasta înseamnă că $x\mapsto x^3$ este bijectiv și deci o permutare.

În cazul în care $3|2^n-1$, dacă $x^3=y$ în $\mathbb F_{2^n}$ apoi să facă așa $(\omega x)^3=y$ și $(\omega^2 x)^3=y$ Unde $\omega$ este o rădăcină cubă de 1 in $\mathbb F_{2^n}$. Rezultă că în acest caz harta nu este injectivă și deci nu este o permutare.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

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.