Registri a scorrimento a retroazione con riporto
# Registri a scorrimento a retroazione con riporto

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) = $(a_0,a_1,...,a_{r-1};z)$ costituito da un vettore di elementi $a_i$ appartenenti a {0,1,...,N-1}=S ed un intero z.

L'operazione di cambio di stato è determinata da un insieme di coefficienti $q_1,...,q_n$ ed è definita come segue: calcolare s = $q_ra_0+q_{r-1}a_1+..+q_1a_{r-1}$ + z. Esprimere s come s = $a_r+Nz'$ con $a_r$ appartenente ad S. Il nuovo stato è quindi $(a_1,a_2,...,a_r;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'Ecuyer, generalizzando un lavoro di Marsaglia e Zaman.

Gli FCSR sono analizzati utilizzando la teoria dei numeri. Associato all'FCSR c'è un intero di connessione q = $q_rN^r$ + ... + $q_1N$ - 1. Associato alla sequenza di output c'è il numero N-adico a = $a_0$ + $a_1N$ + $a_2N^2+....$ 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 $q_i.$

C'è anche una rappresentazione esponenziale degli FCSR: se g è l'inverso di N modulo q, e la sequenza di output è strettamente periodica, allora $a_i$ = $(Ag^i$ 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).

