înregistrare Logare
Puncte:6
Dominic van der Zypen avatar Crypto

Registru de schimbare a feedback-ului bazat pe majoritate

drapel br
Dominic van der Zypen

Registre de deplasare cu feedback liniar (LFSR) lucrează luând un șir de biți cu lungime fixă $b\în\{0,1\}^n$, precum și „taps” fixe (poziții de biți) și aplicarea XOR la ​​robinete, dând un bit de ieșire, care este atașat la $b$ după ce l-a mutat.

Acum XOR este o funcție liniară.O funcție naturală neliniară care poate fi utilizată pe setul fix de robinete este un fel de „vot majoritar”, care funcționează după cum urmează: dacă majoritatea robineților este $0$, apoi ieșim $1$, si invers. (Pentru aceasta, cel mai bine este să aveți un număr impar de atingeri.)

Poate fi găsită o implementare simplă a unui registru de schimbare a feedback-ului bazat pe majoritate Aici.

Desigur, aplicând această procedură de „vot majoritar” din nou și din nou, aceasta devine în cele din urmă periodică.

Întrebare. Având o lungime fixă ​​de biți $n$, care este limita inferioară a lungimii maxime a unei perioade care poate fi atinsă alegând un șir de început adecvat $b\în \{0,1\}^n$ și un set potrivit de robinete?

De asemenea, nu am reușit să aflu dacă și unde a fost studiat acest concept.

138
0 + 0
John Deters avatar
drapel cn
John Deters
Deși nu este un răspuns la întrebarea dvs., vechile mainframe CDC aveau o instrucțiune „Population Count”, CXi Xk, care ar scoate numărul de 1 biți setat în registrul Xk pentru a înregistra Xi. AKA „popcount” sau „instrucțiunea NSA”, utilizarea practică primară inițială pentru acest operator a fost teoretizată a fi criptoanaliza, sugerând că aceasta ar fi putut fi studiată sau cunoscută în anii 1960 și 70. Vedeți https://vaibhavsagar.com/blog/2019/09/08/popcount/#:~:text=Most%20CPU%20architectures%20in%20use%20today%20have%20an,%2800100110%29%20is%203% 20 și%20popcount%20%2801100000%29%20is%202. pentru mai multe informatii.
2
Răspunde
Dominic van der Zypen avatar
drapel br
Dominic van der Zypen
Este foarte interesant - mulțumesc @JohnDeters pentru acest comentariu! De asemenea, folosesc o funcție în [implementarea mea pe GitHub](https://github.com/dominiczypen/Majority_Feedback_Shift_Register/blob/main/mfsr.c) care se numește de fapt popcount(). Poate că folosirea popcount-ului care este încorporat în procesor ar fi mult mai rapidă
0
Răspunde
qwr avatar
drapel jp
qwr
x86 are și o instrucțiune popcount https://www.felixcloutier.com/x86/popcnt
3
Răspunde
b degnan avatar
drapel ca
b degnan
btw, în hardware-ul real, circuitele majoritare ocupă mult spațiu. Simplitatea pe care o vedeți în C este nivelul de poartă inexistent.
0
Răspunde
Puncte:2
fgrieu avatar Crypto
drapel ng
fgrieu

Citesc întrebarea ca cerând $b(n)$, cel mai mare posibil, astfel încât să putem prezenta puncte de atingere distincte (în număr impar) și $n$-stare de biți, conducând la o secvență periodică de (cea mai scurtă) perioadă cel puțin $b(n)$ trepte.

Am o constructie cu $b(n)=2n-2$ pentru $n\ge3$. Robinetele sunt următorii trei biți care vor ieși din MVFSR. Starea este zero, cu excepția următorului bit care va ieși din MVFSR. Iată o ilustrare cu $n=8$: timpul trece de la stânga la dreapta, MVSFR se deplasează în jos, următorul bit intră în partea de sus, cele trei atingeri sunt marcate cu *.

   0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0
   0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0
   0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0
   0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0
   0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0
*  0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0
*  0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1
*  1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1

Dacă permitem o singură atingere, ajungem la $b(n)=2n$.

sper ca $b(n)$ poate fi îmbunătățită (mărește), poate pentru a deveni exponențială, dar este deja mai mult decât $1$ de acest raspuns, și $2$ de acest comentariu.

0 + 0
Dominic van der Zypen avatar
drapel br
Dominic van der Zypen
Mulțumesc mult pentru răspunsul tău -> ar fi minunat să vezi că $b(n)$ a crescut pentru a deveni exponențial chiar și cu un număr mic de robinete plasate inteligent, poate doar $3$ robinete?
0
Răspunde
Puncte:2
Daniel S avatar Crypto
drapel ru
Daniel S

Aș ezita să pretind o limită inferioară mai bună decât 1.

Remarcăm că, pentru un vot majoritar, registrul de schimb de feedback (denumit în continuare MVFSR), dacă există $2k+1$ robinete si daca la un moment dat umplerea registrului are cel mult $k$ zerouri (respectiv cel mult $k$ ones), apoi registrul se va umple ulterior cu unu (respectiv cu zerouri) și va atinge un ciclu de 1.

De asemenea, se simte că există multă substanțialism în sensul că MVFSR cu umpleri rare cu o mulțime de zerouri este probabil să producă feedback-uri zero și umplerile dense cu o mulțime de unități sunt susceptibile să producă un feedback. Din punct de vedere euristic, acest lucru ar îndepărta densitatea de umplere de la 1/2 și ar duce la degenerarea de mai sus.

Este posibil să se producă MVFSR-uri cu robinete setate în progresie aritmetică care degenerează în intercalări ale registrelor mai mici și astfel care ating cicluri stabile de lungime egală cu numărul de registre mai mici, dar acest lucru nu pare o idee bună.

De asemenea, se poate observa că harta de la umplere până la umplere pentru un MVFSR are multe hărți două la unu, care plasează o limită superioară slabă pe durata ciclului final. În general umple unde $k+1$ din primul 2k$ robinetele sunt zero sau unu (adică acolo unde nu există exact $k$ zerouri și $k$ cei din primul 2k$ pozițiile de atingere) sunt umpleri în care cel mai vechi bit de atingere este irelevant pentru feedback și astfel creăm un doi la unu.

0 + 0
poncho avatar
drapel my
poncho
De fapt, următorul bit care este ciclat este inversul majorității robineților - prin urmare, nu cred că este posibilă o lungime a ciclului de 1 (deoarece un șir de biți identici deplasați va deveni în cele din urmă majoritar și astfel se va schimba în bitul opus). Desigur, o lungime a ciclului de 2 este foarte posibilă, cu excepția cazului în care s-a avut grijă cu plasarea robinetului...
0
Răspunde
Dominic van der Zypen avatar
drapel br
Dominic van der Zypen
Corect - și scuze dacă întrebarea a fost poate un pic înșelătoare... Am vrut să întreb cât de lungă se poate ajunge la o perioadă prin plasarea inteligentă a robineților și valoarea inițială de $b$
0
Răspunde
Puncte:2
avatar Crypto
drapel ph
bmm6o

Am scris ceva cod doar pentru configurațiile de robinet de forță brută și valorile de pornire pentru dimensiuni mici de registru. Deci am niște valori, mai degrabă decât un rezultat analitic.Desigur, rezultatele sunt condiționate de faptul că nu există erori în cod (https://github.com/bmm6o/MVFSR).

pentru lățimea 4, lungimea maximă a ciclului este de 8
pentru lățimea 5, lungimea maximă a ciclului este de 10
pentru lățimea 6, lungimea maximă a ciclului este de 12
pentru lățimea 7, lungimea maximă a ciclului este de 14
pentru lățimea 8, lungimea maximă a ciclului este de 48
pentru lățimea 9, lungimea maximă a ciclului este de 48
pentru lățimea 10, lungimea maximă a ciclului este de 80
pentru lățimea 11, lungimea maximă a ciclului este de 108
pentru lățimea 12, lungimea maximă a ciclului este de 140
pentru lățimea 13, lungimea maximă a ciclului este de 270
pentru lățimea 14, lungimea maximă a ciclului este de 270
pentru lățimea 15, lungimea maximă a ciclului este de 270
pentru lățimea 16, lungimea maximă a ciclului este de 480
pentru lățimea 17, lungimea maximă a ciclului este de 752
pentru lățimea 18, lungimea maximă a ciclului este de 1520

Poate fi riscant să generalizezi de la valori mici, dar pare să se dubleze aproximativ când lățimea crește cu 2. Această secvență nu este prezentă în OEIS.

Probabil ți-ai dat seama de asta, dar MVFSR-ul tău evoluează într-un mod astfel încât majoritatea statelor au exact 2 pre-imagini. Nu sunt sigur cum să folosesc asta pentru a face o estimare probabilistică a distribuției lungimii ciclului, dar se pare că ar fi util.

Pentru majoritatea scopurilor criptografice, punerea unei limite inferioare a lungimii maxime a ciclului nu este cea mai importantă întrebare. Mult mai importantă este lungimea minimă, sau cel puțin o modalitate de a caracteriza și de a evita ciclurile scurte. În acest fel, există o problemă serioasă cu MVFSR. Sub selecția optimă a robinetului, există doar cicluri de lungime 2n$.

0 + 0
kodlu avatar
drapel sa
kodlu
spuneți că doriți să legați lungimea minimă a ciclului, dar rezultatul dvs. spune „lungimea maximă a ciclului”
0
Răspunde
drapel ph
bmm6o
Corect. Nu sunt sigur că OP pune întrebarea corectă, dar până acum răspund la cea care a fost adresată. Plănuiesc să obțin și celelalte răspunsuri.
1
Răspunde
poncho avatar
drapel my
poncho
Am făcut o căutare complet independentă pentru lungimea maximă a ciclului (nici măcar nu m-am uitat la codul dvs.) și am venit cu aceleași rezultate - codul dvs. pare a fi corect
1
Răspunde
drapel ph
bmm6o
Mulțumesc, @poncho. Cred că sunt foarte surprins că nu este monoton.
0
Răspunde
poncho avatar
drapel my
poncho
Nu chiar atât de surprinzător; există lucruri mai simple (cum ar fi „care este ordinea maximă a unei permutări peste k obiecte”) care, de asemenea, nu sunt strict monotone...
0
Răspunde
poncho avatar
drapel my
poncho
De asemenea, am căutat în cealaltă direcție „pentru orice lățime și orice set de număr impar de robinete, care este lungimea minimă a ciclului”; pentru latime
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.