Electronics > Projects, Designs, and Technical Stuff
Algorithm for calculating previous states of LFSR counters ?
ataradov:
--- Quote from: 0culus on July 03, 2019, 01:54:30 am ---All zero is a lockup state, so that won't work.
--- End quote ---
Not for the XNOR-based LFSR. In that case all-1s is a lock up state. LFSR can't naturally produce its lock up state, so you could never arrive at it.
0culus:
--- Quote from: ataradov on July 03, 2019, 01:57:05 am ---
--- Quote from: 0culus on July 03, 2019, 01:54:30 am ---All zero is a lockup state, so that won't work.
--- End quote ---
Not for the XNOR-based LFSR. In that case all-1s is a lock up state. LFSR can't naturally produce its lock up state, so you could never arrive at it.
--- End quote ---
Ahh, I missed the XNOR part. My bad.
T3sl4co1l:
It runs same forwards as backwards, no? So just do the same thing with the inverted matrix. (I'd... have to read that rather in depth to know if the matrix representation even is invertible, but it should be?)
That gives you access to a parallel computing approach. Sample the space with a series of exponentiated shortcuts, then linear search from each of those points. You could binary search if the sequence were ordered, but it's not that kind of ring unfortunately. Actually, is that wrong? It's a linear function, so it has to work with superposition. But with XOR rather than addition-with-carry, there's still no ordering to it?
You can certainly precalculate the steps nearest to zero, saving a few there; but I'm not sure that there's anything more to find beyond that? It gets to be more of a crypto question...
Tim
cur8xgo:
--- Quote from: T3sl4co1l on July 03, 2019, 02:20:47 am --- It gets to be more of a crypto question...
--- End quote ---
ya I bet if you read about weaknesses of LSFR based security or LSFR predictability you will get a few papers or articles that show how to break them without brute force
or at least a clear statement that brute force is the only way
Siwastaja:
Needing no data and completely fitting CPU registers, this is a problem that should parallelize very well. Try to run it on GPU so you have hundreds of the shader CPUs executing in parallel? Give each one a different start state from your sparse precomputed table.
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version