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₀,a₁,...,a_r-1;z) costituito da un vettore di elementi a_i appartenenti a {0,1,...,N-1}=S ed un intero z^[1][2][3][4]. L'operazione di cambio di stato è determinata da un insieme di coefficienti q₁,...,q_n ed è definita come segue: calcolare s = q_ra₀+q_r-1a₁+..+q₁a_r-1 + z. Esprimere s come s = a_r+Nz' con a_r appartenente ad S. Il nuovo stato è quindi (a₁,a₂,...,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^[5], generalizzando un lavoro di Marsaglia e Zaman^[6].

Gli FCSR sono analizzati utilizzando la teoria dei numeri. Associato all'FCSR c'è un intero di connessione q = q_rN^r + ... + q₁N - 1. Associato alla sequenza di output c'è il numero N-adico a = a₀ + a₁N + a₂N²+.... 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^[1].

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ⁱ 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).