sequenza pseudocasuale poco casuale
grigio
pseudocasuali nel range 0,31.
Relativamente spesso, diciamo una volta ogni qualche decina
di sequenze generate, saltano all'occhio, all'interno della sequenza,
dei gruppi di numeri del tipo XYYX, oppure XYZYX, oppure XYZYZX
e simili che fanno intuire un algoritmo pseudorandom molto scarso.
E' possibile dire che tipo di algoritmo potrebbe essere? Un LFSR?
Cristiano
Direi di no. Gli LFSR falliscono sistematicamente solo un tipo di test; "a
occhio" sembrano ottimi.
E` possibile che l'algoritmo utilizzato, in realt�, non sia molto scarso. Se
te ne vuoi accertare seriamente, fammi sapere (basta usare uno dei tanti
programmi gratuiti sparsi per il WEB).
Cristiano
grigio
> grigio wrote:
> > Un dispositivo digitale genera delle sequenze di 40 numeri
> > pseudocasuali nel range 0,31.
> > Relativamente spesso, diciamo una volta ogni qualche decina
> > di sequenze generate, saltano all'occhio, all'interno della sequenza,
> > dei gruppi di numeri del tipo XYYX, oppure XYZYX, oppure XYZYZX
> > e simili che fanno intuire un algoritmo pseudorandom molto scarso.
> > E' possibile dire che tipo di algoritmo potrebbe essere? Un LFSR?
>
> Direi di no. Gli LFSR falliscono sistematicamente solo un tipo di test; "a
> occhio" sembrano ottimi.
Beh io molti anni fa ho crackato un dispositivo Dallas che usava
un LFSR per crittografare i dati. Per farlo mi sono studiato
lunghissime sequenze di 0 e 1 e ricordo che ogni tanto
trovavo dei pattern del tipo che ho descritto sopra. Spesso
c'era una sequenza seguita da una palindroma.
Per questo motivo ho immaginato che ci fosse di mezzo
anche qui un LFSR.
> E` possibile che l'algoritmo utilizzato, in realtà, non sia molto scarso.
Un algoritmo che genera spesso quelle configurazioni può non
essere scarso???
> Se
> te ne vuoi accertare seriamente, fammi sapere (basta usare uno dei tanti
> programmi gratuiti sparsi per il WEB).
Sfortunatamente quel dispositivo esce solo con un display, perciò
sarebbe tediosissimo trasferire i dati a mano per analizzarli.
Cristiano
> Beh io molti anni fa ho crackato un dispositivo Dallas che usava
> un LFSR per crittografare i dati.
Non stento a credere che tu l'abbia craccato! :-) Essendo un generatore
lineare, � particolarmente "debole".
E` strano che un LFSR "liscio" venga utilizzato per cifrare i dati (in
crittografia si usano FSR non lineari, proprio per rendere molto
difficoltoso il craccaggio).
> Per farlo mi sono studiato
> lunghissime sequenze di 0 e 1 e ricordo che ogni tanto
> trovavo dei pattern del tipo che ho descritto sopra. Spesso
> c'era una sequenza seguita da una palindroma.
> Per questo motivo ho immaginato che ci fosse di mezzo
> anche qui un LFSR.
L'apparente casualit� dipende anche dal polinomio di retroazione; se �
"denso" (cio� ha molti bit a 1) la sequenza in uscita sembra pi� caotica.
> Un algoritmo che genera spesso quelle configurazioni pu� non
> essere scarso???
Spesso l'occhio inganna. :-)
Se per� tu vedi evidenti "regolarit�", pu� anche essere che il generatore
(di qualunque tipo esso sia) abbia un periodo troppo corto.
Cristiano
Adam Atkinson
> Relativamente spesso, diciamo una volta ogni qualche decina
> di sequenze generate, saltano all'occhio, all'interno della sequenza,
> dei gruppi di numeri del tipo XYYX, oppure XYZYX, oppure XYZYZX
> e simili che fanno intuire un algoritmo pseudorandom molto scarso.
> E' possibile dire che tipo di algoritmo potrebbe essere? Un LFSR?
E ogni quanto ti aspetteresti un gruppo di almeno uno di questi tipi?
grigio
A occhio molto più raramente, ma non ho mai fatto un
conto: provo a farlo adesso, molto grossolano.
Prendiamo la sequenza XYYX, quella che ho notato più
frequentemente.
Con numeri da 0 a 31 ci possono essere un migliaio di combinazioni
tra il milione circa di tutti i possibili gruppi di 4 cifre, circa
una possibilità su 1000.
Su gruppi di 40 numeri può presentarsi in 36 posizioni diverse.
Perciò la probabilità che esca è di circa 36/1000, cioè una volta
ogni trenta sequenze.
Se ho fatto i conti esattamente, coinciderebbe perfettamente con
quanto riscontrato in realtà. Quindi è solo colpa dell'occhio che
riconosce meglio certe sequenze?
Adam Atkinson
> > E ogni quanto ti aspetteresti un gruppo di almeno uno di questi tipi?
>
> A occhio molto più raramente, ma non ho mai fatto un
> conto
Non l'ho fatto nemmeno io ma spesso farlo puo' sorprenderti.
> Se ho fatto i conti esattamente, coinciderebbe perfettamente con
> quanto riscontrato in realtà. Quindi è solo colpa dell'occhio che
> riconosce meglio certe sequenze?
E' possibile. Se riconosci come "strane" sequenze varie e ne vedi
una una volta su dieci, mi sa che fare questo calcolo anche
approssimativamente
possa essere opportuno prima di decidere che c'e' qualcosa che non va.
Elio Fabri
> E ogni quanto ti aspetteresti un gruppo di almeno uno di questi tipi?
Puo' essere pericoloso giudicare "a naso" se qualcosa e' poco o molto
probabile...
--
Elio Fabri