4 ms·
The problem of generating a non-repeating (2^n)-1 n-bit numbers permutation is equivalent to generating a m-sequence (http://en.wikipedia.org/wiki/Maximum_lengt
by aortega 13y ago
The problem of generating a non-repeating (2^n)-1 n-bit numbers permutation is equivalent to generating a m-sequence (http://en.wikipedia.org/wiki/Maximum_length_sequence http://en.wikipedia.org/wiki/Maximum_length_sequence) and the simplest way is a n-bit LFSR with a primitive poly, called maximal LFSR. It's so much simpler and faster (some XORs and n bits of memory), I cannot see why they chose that weird prime multiplication algorithm, in fact right now I'm not completely sure that algorithm is correct.
- aortega 13y agoFurthermore, is not that a way to describe a Linear Congruential Generator (You know, rand()?) http://en.wikipedia.org/wiki/Linear_congruential_generator http://en.wikipedia.org/wiki/Linear_congruential_generator by looking at the source (https://github.com/zmap/zmap/blob/master/src/cyclic.c#L164 https://github.com/zmap/zmap/blob/master/src/cyclic.c#L164) it really looks like it, specifically a Lehmer random number generator. That would mean the period of the generator is not exactly 2^32 but it repeats 15 IPs... EDIT: Now I see it, it actually generates numbers over 2^32 but the code just skips them...nasty! I'm surely missing something, or else that's a usenix paper wasting 2 pages explaining rand()
- tptacek 13y agoIt's not literally rand, but is a form of LCG, just tuned for IP addresses. I agree with you about the formal impact of the "math" here. The irony is that I'm not impressed by the scanner stuff, and easily impressed by simple math!
- pbsd 13y agoA 32-bit LFSR generates a sequence of bits with period 2^32-1; what you really want is a Lehmer-like generator using arithmetic in GF(2^32).
- tptacek 13y agoYou mathematicians, with your... understanding of the basic mathematics behind things we developers already use every day, you all think you're better than us, don't you? DON'T YOU?! Can't I just be left to be impressed by a direct use of the math behind a crappy textbook random number generator in peace? -.-
- pbsd 13y agoI'm not 100% sure if that was tongue-in-cheek or not, so I'll clarify: I was disagreeing with aortega. This is not a typical PRNG, where the seed generally marks the initial point of the same sequence. Choosing a random generator matters, because we want a different permutation every time, not simply a different starting point. It is akin to running a block cipher in OFB mode with a different key each time. What they are doing modulo 2^32 + 15 is IMO the simplest way to achieve that goal. Yes, you could do it without overflowing 2^32 using a binary field; you could also cook your own mini block-cipher. But that increases the complexity of the code and is not really faster everywhere.
- tptacek 13y agoIt was 100% tongue-in-cheek, but I'm happy to be extracting even more information from you by having my poor attempts at humor misconstrued. :)
- aortega 13y ago>Choosing a random generator matters, because we want a different permutation every time, not simply a different starting point. Ah thanks, now it makes more sense, I knew I was missing something. What about choosing different prime polys for a galois lfsr? I believe you will get the same result.
- aortega 13y agoAlso you could XOR the LFSR output with any number to get a different permutation each time.
- tga_d 13y agoWhat does "GF(2^32)" mean in this context?
- pbsd 13y agoIt's the finite field with 2^32 elements. There are several equivalent representations, but we typically work with it as the polynomials with coefficients modulo 2 modulo an irreducible polynomial of degree 32, e.g., x^32 + x^7 + x^3 + x^2 + 1. For more, see [1]. [1] https://en.wikipedia.org/wiki/Finite_field_arithmetic https://en.wikipedia.org/wiki/Finite_field_arithmetic