înregistrare Logare
Puncte:1
avatar Crypto

Care sunt formele normale algebrice pentru fiecare bit al lui $z$, unde $z = (x \oplus y) \oplus ((x \wedge y) \ll 1)$ (o operație neliniară în NORX)?

drapel de
lyrically wicked

Lăsa $x, y, z$ denota trei $n$-bit cuvinte astfel încât $$z = (x \oplus y) \oplus ((x \land y) \ll 1).$$

Lucrarea NORX conține descrierea generalizată a formelor normale algebrice pentru fiecare bit de $x$ dat $y$ și $z$: $$\begin{matrice}{l} x_0 = (z_0 \oplus y_0),\ x_1 = (z_1 \oplus y_1) \oplus (x_0 \land y_0),\ \vdots\ x_i = (z_i \oplus y_i) \oplus (x_{i-1} \land y_{i-1}),\ \vdots\ x_{n-1} = (z_{n-1} \oplus y_{n-1}) \oplus (x_{n-2} \land y_{n-2}), \end{matrice}$$

Unde $w_i$ denotă o $i$-al doilea fragment din cuvânt $w \in \{x, y, z\}$.

Care este descrierea generalizată corespunzătoare a formelor normale algebrice pentru fiecare bit de $z$ dat $x$ și $y$?

98
1 + 0
Puncte:2
Fractalice avatar Crypto
drapel in
Fractalice

Din $$x_i = z_i \oplus y_i \oplus (x_{i-1} \land y_{i-1})$$ primim $$z_i = x_i \oplus y_i \oplus (x_{i-1} \land y_{i-1}).$$

0 + 9
drapel de
lyrically wicked
Atunci mă întreb de ce lucrarea susține că această funcție „nu este în mod evident inversabilă la prima vedere”. Este adevărat că este o [funcție T] triunghiulară (https://en.m.wikipedia.org/wiki/T-function) (precum și adunarea și scăderea)?
0
Răspunde
Fractalice avatar
drapel in
Fractalice
Este triunghiulară, dar nu există o expresie bazată pe cuvinte pentru inversare, cum ar fi adunarea/scăderea. Probabil că acesta este motivul.
0
Răspunde
drapel de
lyrically wicked
Se pare că inversul funcției H în NORX este triunghiulară, dar funcția H în sine nu este triunghiulară deoarece forma normală algebrică pentru $z_i$ _nu_ depinde de fiecare bit mai puțin semnificativ. Este adevarat?
0
Răspunde
drapel pe
Samuel Neves
Este corect; neavând o inversă cu un număr similar de operații de cuvinte ca direcția înainte este motivul pentru care am numit-o „nu este evident”. Ambele direcții înainte și înapoi sunt funcții T; o funcție T nu trebuie să implice fiecare bit anterior pentru a fi triunghiulară, trebuie doar să implice _exclusiv_ biți anteriori.
1
Răspunde
drapel de
lyrically wicked
@SamuelNeves: „o funcție T nu trebuie să implice fiecare bit anterior pentru a fi triunghiulară” â depinde de ceea ce înseamnă cuvântul „implica”. Potrivit [acest articol Wikipedia](https://en.m.wikipedia.org/wiki/T-function), „dacă fiecare bit mai puțin semnificativ este inclus în actualizarea fiecărui bit din stat, un astfel de T- funcția se numește triunghiulară.” Observați formularea: „fiecare bit mai puțin semnificativ”. [1/2]
0
Răspunde
drapel de
lyrically wicked
@SamuelNeves: direcția înapoi a funcției H se potrivește cu definiția „triunghiulară”, dar direcția înainte nu este, deoarece ANF pentru un $i$-al-lea bit al cuvântului $x$ (adică direcția înapoi) conține $x_{i -1}$, dar ANF pentru un $i$-al-lea bit al cuvântului $z$ (adică direcția înainte) nu conține $z_{i-1}$. Este corectă înțelegerea mea despre „triangularitate”? [2/2]
0
Răspunde
drapel pe
Samuel Neves
Mi se pare puțin prostesc să vorbesc despre funcții T triunghiulare, deoarece T înseamnă deja triunghiular. Nu prea știu de unde a luat această definiție articolul de pe wikipedia, din moment ce nu-mi amintesc să fi văzut-o în literatură.
0
Răspunde
drapel de
lyrically wicked
@SamuelNeves: Secțiunea 4 din lucrarea „O nouă clasă de mapări inversabile” [A. Klimov, A. Shamir] oferă o descriere la ceea ce se referă numele „funcție T” și explică diferența dintre triangulația implicită și triangulația explicită... Deci poate că o „funcție T triunghiulară” implică un „T- funcție care are o formă triunghiulară explicită"?
0
Răspunde
drapel pe
Samuel Neves
OK, din câte îmi pot da seama, Wikipedia are o definiție mult mai restrânsă a unei funcții T, ceea ce o obligă să fie inversabilă (nu este neapărat cazul). Ceea ce numește o funcție T este ceea ce s-ar numi de obicei o funcție T inversabilă sau bijectivă, iar ceea ce numește o funcție T triunghiulară este ceea ce s-ar numi o funcție T cu un singur ciclu. Deci, operațiunea NORX este o funcție T bijectivă, dar cu siguranță nu o funcție T cu un singur ciclu (când se remediază unul dintre argumente).
0
Răspunde
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.