# Relationship between LCGs and LFSRs

Here:

https://en.wikipedia.org/wiki/Linear-feedback_shift_register

they wrote:

The linear feedback shift register has a strong relationship to linear congruential generators

What this relationship is all about? Are they mathematically equivalent in some way? In two cases, we can reach the maximum period. Maybe there are LCGs that generate the same numbers as the LFSRs? As far as I know, the LFSRs also have a problem with the low order bits, just like the LCG mod $$2^n$$. But do we have any deeper connections here, beyond the similarities?

• Given most LFSRs used in practice work over $GF(2)$ instead of $GF(2^n)$ I am wondering what your comment "problem with low order bits" may be about. Sep 14 at 4:51
• or do you just mean don't output the first so many bits since you'd be giving away the "seed" (sometimes used as the key) Sep 14 at 5:10

They're both linear which is of course a weakness from the cryptographic point of view. LCG is $$x_{t}\equiv (a x_{t-1}+c) \pmod n \qquad (1)$$ while LFSR is $$x_{t} \equiv (a_1 x_{t-1}+ a_2 x_{t-2}+\cdots+ a_L x_{t-L}) \pmod 2\qquad (2)$$
One could devise an $$L$$ term LCG $$x_{t}\equiv (a_1 x_{t-1}+a_2 x_{t-2}+\cdots+ a_L x_{t-L}) \pmod n$$ which could then be reduced mod 2 (both the $$x_t$$s and the $$a_i$$s reduced mod 2) to correspond to an LFSR, but that's a bit artificial, since one must pick a large size for $$n$$ and choose its properties (e.g., is $$n$$ prime, semiprime, is $$\gcd(a,n)=1$$) to get a relatively strong recurrence. So this would be overkill, with no appreciable gain in strength compared to (1) and a more complicated choice of the constants $$a_i$$ would be needed.