Un registro a scorrimento a retroazione con riporto, generalmente indicato come FCSR, sigla di Feedback with Carry Shift Registers, è un tipo di registro simile al Registro a scorrimento a retroazione lineare (o LSFR) da cui differisce per la presenza di un registro secondario per la memorizzazione del riporto, o resto delle operazioni. Se N > 1 è un intero allora l'N-adico FCSR di lunghezza r è un dispositivo a stato finito con uno stato (a;z) = (a0,a1,...,ar-1;z) costituito da un vettore di elementi ai appartenenti a {0,1,...,N-1}=S ed un intero zA. Klapper and M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, in Journal of Cryptology vol. 10, pp. 111-147, 1997, R. Couture and P. L'Ecuyer, On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. vol. 62, pp. 799–808, 1994, ,M. Goresky and A. Klapper, Algebraic Shift Register Sequences, 2009, M. Goresky and A. Klapper, Efficient Multiply-with-Carry Random Number Generators with Optimal Distribution Properties, ACM Transactions on Modeling and Computer Simulation, vol 13, pp 310-321, 2003, . L'operazione di cambio di stato è determinata da un insieme di coefficienti q1,...,qn ed è definita come segue: calcolare s = qra0+qr-1a1+..+q1ar-1 + z. Esprimere s come s = ar+Nz''' con ar appartenente ad S. Il nuovo stato è quindi (a1,a2,...,ar;z'). Iterando il cambiamento di stato un FCSR genera un'infinita, eventualmente anche periodica, sequenza di numeri in S.
Gli FCSR sono utilizzati nei cifrari a flusso (ad esempio nell'F-FCSR), nella crittanalisi del summation generator (una primitiva crittografica creata nel 1985) e come generatore di numeri pseudo casuali nel metodo Quasi Monte Carlo (sotto il nome di "generatore Multiply With Carry (MWC)", inventato da Couture e L'EcuyerR. Couture, P. L'Ecuyer: On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. vol. 62, pagg. 799–808, 1994, ,, generalizzando un lavoro di Marsaglia e ZamanG. Marsaglia, A. Zaman: A new class of random number generators, Annals of Applied Probability, vol. 1, pagg. 462–480, 1991.
Gli FCSR sono analizzati utilizzando la teoria dei numeri. Associato all'FCSR c'è un intero di connessione q = qrNr + ... + q1N - 1. Associato alla sequenza di output c'è il numero N-adico a = a0 + a1N + a2N2+.... Il teorema fondamentale degli FCSR afferma che c'è un intero u tale che a = u/q, un numero razionale. La sequenza di output è strettamente periodica se e soltanto se u è compreso fra -q e 0. È possibile esprimere u come un polinomio quadratico semplice che coinvolge lo stato iniziale e qi.
C'è anche una rappresentazione esponenziale degli FCSR: se g è l'inverso di N modulo q, e la sequenza di output è strettamente periodica, allora ai = (Agi mod q) mod N, dove A è un intero. Ne consegue che il periodo è al massimo dell'ordine di N nel gruppo moltiplicativo di unità modulo q. Questo vale ancor di più quando q è primo e N è un elemento primitivo modulo q. Allora il periodo è q-1: in questo caso la sequenza di output è chiamata sequenza-l, sequenza lunga (o l-sequence'').
Note
Categoria:Algoritmi crittografici