Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

If I've got an LFSR, let's say a 16-bit Fibonacci LFSR as shown in the corresponding wikipedia article, which generates maximum length sequences, could I use it to create word sequences instead of bit sequences?

Staying with the wiki example, let's say I got a 16-bit LFSR with the following primitive polynomial: $x^{16} + x^{14} + x^{13} + x^{11} + 1$ which results in the usage of taps: 16 14 13 11. Now, if I just use the standard LFSR, the process would look as follos:

TAP:  1                                       11      13  14      16  
  +-->[1] [0] [1] [0] [1] [1] [0] [0] [1] [1] [1] [0] [0] [0] [0] [1]---+ 
  |                                            |       |   |            |
  +-------------------------------------------XOR-----XOR-XOR------<----+

The LFSR generates a sequence of length $2^{16}-1=65535$ bits until it reaches its original internal state again. Now, what would happen if the single bits in the state were replaced by whole words as shown in the next figure (w are changing 32-bit words)?

TAP:  1                                       11      13  14      16  
  +-->[w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w] [w]---+
  |                                            |       |   |            |
  +-------------------------------------------XOR-----XOR-XOR------<----+ 

Would this return a sequence of 65535 32-bit words before it reaches its initial state again?

(Please note: I don't want to collect 32bit from output of a "bit-wise" LFSR to form a word, I'm merely interested in the above problem )

share|improve this question
add comment

1 Answer 1

Sure enough, if you use xor with the words, what you do have is the bitwise LFSR repeated 32 times in parallel, each in a different state, but each one having a $2^{16}-1$ period, so the period of your construction should be $2^{16}-1$ as well. If LFSR period wasn't exactly $2^{16}-1$ this will be another history.

share|improve this answer
    
Oh yes, veiewing it from that perspective answers my question quite illustrative, thanks! –  Hagge Knar Oct 21 '13 at 10:26
1  
@HaggeKnar I suppose you could use other operations than XOR in your feedback function to make the 32 parallel registers more interacting with each other. But then it won't be linear anymore (at least not linear respective to XOR). –  Paŭlo Ebermann Oct 21 '13 at 16:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.