| dbo:abstract
|
- In sequence design, a Feedback with Carry Shift Register (or FCSR) is the arithmetic or with carry analog of a linear-feedback shift register (LFSR). If is an integer, then an N-ary FCSR of length is a finite state device with a state consisting of a vector of elements in and an integer . The state change operation is determined by a set of coefficients and is defined as follows: compute . Express s as with in . Then the new state is . By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in . FCSRs have been used in the design of stream ciphers (such as the F-FCSR generator), in the cryptanalysis of the summation combiner stream cipher (the reason Goresky and Klapper invented them), and in generating pseudorandom numbers for quasi-Monte Carlo (under the name Multiply With Carry (MWC) generator - invented by Couture and L'Ecuyer,) generalizing work of Marsaglia and Zaman. FCSRs are analyzed using number theory. Associated with the FCSR is a connection integer . Associated with the output sequence is the N-adic number The fundamental theorem of FCSRs says that there is an integer so that , a rational number. The output sequence is strictly periodic if and only if is between and . It is possible to express u as a simple quadratic polynomial involving the initial state and the qi. There is also an exponential representation of FCSRs: if is the inverse of , and the output sequence is strictly periodic, then , where is an integer. It follows that the period is at most the order of N in the multiplicative group of units modulo q. This is maximized when q is prime and N is a primitive element modulo q. In this case, the period is . In this case the output sequence is called an l-sequence (for "long sequence"). l-sequences have many excellent statistical properties that make them candidates for use in applications, including near uniform distribution of sub-blocks, ideal arithmetic autocorrelations, and the arithmetic shift and add property. They are the with-carry analog of m-sequences or maximum length sequences. There are efficient algorithms for FCSR synthesis. This is the problem: given a prefix of a sequence, construct a minimal length FCSR that outputs the sequence. This can be solved with a variant of Mahler and De Weger's lattice based analysis of N-adic numbers when ; by a variant of the Euclidean algorithm when N is prime; and in general by Xu's adaptation of the Berlekamp-Massey algorithm. If L is the size of the smallest FCSR that outputs the sequence (called the N-adic complexity of the sequence), then all these algorithms require a prefix of length about to be successful and have quadratic time complexity. It follows that, as with LFSRs and linear complexity, any stream cipher whose N-adic complexity is low should not be used for cryptography. FCSRs and LFSRs are special cases of a very general algebraic construction of sequence generators called Algebraic Feedback Shift Registers (AFSRs) in which the integers are replaced by an arbitrary ring R and N is replaced by an arbitrary non-unit in R. A general reference on the subject of LFSRs, FCSRs, and AFSRs is the book. (en)
- 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 z. 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 nelmetodo 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 = 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) (it)
- Регистр сдвига с обратной связью по переносу (англ. feedback with carry shift register, FCSR) — регистр битовых слов, арифметический аналог регистра сдвига с линейной обратной связью, отличается от него наличием регистра переноса. Применяется для генерации псевдослучайных последовательностей битов, а также использовался для создания потокового шифра F-FCSR. (ru)
|
| rdfs:comment
|
- Регистр сдвига с обратной связью по переносу (англ. feedback with carry shift register, FCSR) — регистр битовых слов, арифметический аналог регистра сдвига с линейной обратной связью, отличается от него наличием регистра переноса. Применяется для генерации псевдослучайных последовательностей битов, а также использовался для создания потокового шифра F-FCSR. (ru)
- In sequence design, a Feedback with Carry Shift Register (or FCSR) is the arithmetic or with carry analog of a linear-feedback shift register (LFSR). If is an integer, then an N-ary FCSR of length is a finite state device with a state consisting of a vector of elements in and an integer . The state change operation is determined by a set of coefficients and is defined as follows: compute . Express s as with in . Then the new state is . By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in . (en)
- 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 z. 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,...,a (it)
|
