I'm currently using a simple Galois LFSR (Linear Feedback Shift Register) algorithm for generating an iterative sequence for a locking mechanism (remove accidental and incidental issues in messing with somethings configuration). Keeping it simple is necessary because this is NOT A PC (a IBM XT with 64K ram had more resources than this thing).
So not a whole lot of processing power or memory is available. I've noticed using the Galois processing that the last N words of the sequence are all ordered (thus being easy to identify the end of sequence). Am I applying the algorithm incorrectly or something?
My version where RTYPE is the word size and POLYNOMIAL is the polynomial
Not sure if it's right or wrong because of the ordered end of sequence thought I would check here.
This can generate a 2^N sequence of numbers without repeated numbers but the last N words being ordered drives me a bit crazy. As stated I want to keep this simple without tables (such as SHA uses for example). I prefer disordered sequences. This works fine except the last N words are always ordered (think 1 2 3 as ordered and 8343 1 453 as not ordered). The only other way to do this is ignore the last N words that I can think of. Varying the polynomial I don't believe will change the last N words.
Cyb
Adendum (in case people are wondering)
Galois or Linear feedback shift register is described in detail on wikipedia here (I am being lazy).
Since I'm using this for a locking mechanism I prefer the following situations NOT to exist (LOL).
Easily predictable next value in sequence (IE in LFSR creates 0xFFFF 0x7FFF 0x3FFF 0x1FFF 0x0FFF 0x07FF 0x03FF 0x01FF 0x00FF ... etc at the end). The polynomial doesn't appear in the sequence (such as after 0 does in the LFSR technique).
SHA and block techniques use a seed table for there randomness. This is problematic for anything that has a limited amount of memory as the table consumes memory. The minimum table size is 1K of data last I checked (256 32 bit seeds I believe). There are random number sets available etc. etc. However block cipher techniques are not going to happen as I don't have the memory budget.
Cyb
So not a whole lot of processing power or memory is available. I've noticed using the Galois processing that the last N words of the sequence are all ordered (thus being easy to identify the end of sequence). Am I applying the algorithm incorrectly or something?
My version where RTYPE is the word size and POLYNOMIAL is the polynomial
Code:
[FONT="]RTYPE random(RTYPE)[/FONT]
[FONT="]{[/FONT]
[FONT="] [B]bool[/B] use_poly;[/FONT]
[FONT="]use_poly = (number & 0x01);[/FONT]
[FONT="]value >>= 1;[/FONT]
[B][FONT="]if[/FONT][/B][FONT="](use_poly)[/FONT]
[FONT="]{[/FONT]
[FONT="] value ^= POLYNOMIAL;[/FONT]
[FONT="]}[/FONT]
[B][FONT="]return[/FONT][/B][FONT="] value;[/FONT]
[FONT="]}[/FONT]This can generate a 2^N sequence of numbers without repeated numbers but the last N words being ordered drives me a bit crazy. As stated I want to keep this simple without tables (such as SHA uses for example). I prefer disordered sequences. This works fine except the last N words are always ordered (think 1 2 3 as ordered and 8343 1 453 as not ordered). The only other way to do this is ignore the last N words that I can think of. Varying the polynomial I don't believe will change the last N words.
Cyb
Adendum (in case people are wondering)
Galois or Linear feedback shift register is described in detail on wikipedia here (I am being lazy).
Since I'm using this for a locking mechanism I prefer the following situations NOT to exist (LOL).
Easily predictable next value in sequence (IE in LFSR creates 0xFFFF 0x7FFF 0x3FFF 0x1FFF 0x0FFF 0x07FF 0x03FF 0x01FF 0x00FF ... etc at the end). The polynomial doesn't appear in the sequence (such as after 0 does in the LFSR technique).
SHA and block techniques use a seed table for there randomness. This is problematic for anything that has a limited amount of memory as the table consumes memory. The minimum table size is 1K of data last I checked (256 32 bit seeds I believe). There are random number sets available etc. etc. However block cipher techniques are not going to happen as I don't have the memory budget.
Cyb
Last edited: