Patent ID: 7340496

Claim:
A method for determining the Nth state of an n-stage linear feedback shift register (LFSR) providing a result useful in applications including password generation, convergent signature analysis, and encryption, comprising steps of: building a look-up table of n-bit states for latch positions of said linear feedback shift register; obtaining a modulo remainder of said Nth state; and generating directly from said modulo remainder and said n-bit states said Nth state and, if in standard form, further comprising steps of: converting said LFSR to modular form; modulo (2 n −1) dividing a desired cycle count N to derive a remainder value N″; building said look-up table to include x, y, and z values, where x=LFSR latch position (0, 1, . . . , n−1); y=2 i for i=0, n−1 (for i=0, 1, 2, 3, . . . , n−1), giving values (0, 1, 2, 4, 8, . . . , 2 n−1 ); and z=n-bit state of said LFSR for (x, y); first determining all cycle rows Ci needed to binary add to said remainder value N″; for each said bit position y in a first said cycle row Ci, second determining said n-bit state z; for each bit set in each said n-bit state z, third determining for a next cycle row Ci said n-bit state z; and exclusive ORing all said n-bit states to determine said Nth state.