Roots of 1 mod 2^n

[fenderbender]

I'm writing code which is using a "rolling hash" over a stream of numbers. This mostly consists of having a running total T which is updated with each new value in the stream as it comes in, something similar to:

T=0;
while (v= getNewValueFromStream() )
{
T=12345*(T+v);
}

This simple math is all done mod 2^32 or 2^64, the implicit size of the integer T.

So in practice, T is a linear sum of all the stream values. The weight of the last value is 12345, the weight of the second to last value is 12345^2, the weight of the Nth to last value is 12345^N.

This constant C (12345 in this example) is something I can choose. I'd like to choose it randomly (at runtime) so different hash functions can be used for different instances of my algorithm.

Obviously this constant C needs to be ODD. If it wasn't, the powers of 2 would accumulate and after 32 or 64 (or fewer) values, the value of C^N mod 2^32 would end up 0 and we'd be hashing just the last values in the whole stream.

Now my question is what conditions on C will give C^N the longest period before it repeats back to 1?

In math terms, for what conditions of C gives C^n != 1 mod 2^32
for n=1..N for the largest N?

I think this has to do with the roots of 1 mod 2^N but it's not as easy a rule as I thought.

For example, mod 2^32, I get the following periods:

C=3 N=2^30
C=5 N=2^30
C=7 N=2^29
C=9 N=2^29
C=11 N=2^30
C=13 N=2^30
C=15 N=2^28
C=17 N=2^28
C=19 N=2^30


In the end I want tp pick large random values of C which have a full period as long as possible.. 2^30 in this case.

So.. back to my question. What defines the length of this period, and how can I efficiently pick random C which have the longest possible period?

Thanks!

[Gammatester]

This looks a bit like a Linear Congruential Generator, if you write the code as

T = C*T + C*v mod m = C*T + V mod m, with m=2^32, V=C*v.

If V is a constant increment, Knuth (Seminumerical algorithms Ch. 3.2) and others give conditions for maximal length LCGs:

1. V and m are relatively prime,
2. C - 1 is divisible by all prime factors of m = 2^32
3. C - 1 is a multiple of 4 if m is a multiple of 4.

This would solve your problem for constant v. Your table shows that even for C-1 a multiple of 4 a maximum period is not reached. So I guess you cannot have a definite answer without knowing a good deal about the v values.

[science_man_88]

if v stays the same maybe you're right for the power of 2 idea but if v increases by 1 each time I don't see your point.

T=2*(T+v)

v=1 T=2*(0+1) = 2
v=2 T=2*(2+2) = 8
v=3 T=2*(8+3) = 22
.....

so it's only if v stays the same that I can easily see it following the powers of 2.

[Gammatester]

The point is that you cannot say much a about maximum period length if you do not know/list the v values. With C=12345 there are some obvious results: v=0 will always give T=0, i.e. a minum length period. If v is always even, T will allways even etc.

Fenderbender's literal C^N = 1 mod 2^32 question has another answer: C must be a primitive element mod 2^32 (i.e. C mod 8 = 3 or 5) and the maximum period is the Carmichael lambda(2^32) = 2^30.

But this holds only if all v=0 and the starting value T is odd.

[science_man_88]

Originally Posted by Gammatester

The point is that you cannot say much a about maximum period length if you do not know/list the v values. With C=12345 there are some obvious results: v=0 will always give T=0, i.e. a minum length period. If v is always even, T will allways even etc.

Fenderbender's literal C^N = 1 mod 2^32 question has another answer: C must be a primitive element mod 2^32 (i.e. C mod 8 = 3 or 5) and the maximum period is the Carmichael lambda(2^32) = 2^30.

But this holds only if all v=0 and the starting value T is odd.

if v=1 and C is even ? then statistically I think it has a 50% at each time it passes 2^32 in length that suggest 2*2^32 are needed to ensure a repeat of 1 mod 2^32 if so the period is likely 2^33.

[science_man_88]

Originally Posted by fenderbender

I'm writing code which is using a "rolling hash" over a stream of numbers. This mostly consists of having a running total T which is updated with each new value in the stream as it comes in, something similar to:

T=0;
while (v= getNewValueFromStream() )
{
T=12345*(T+v);
}

This simple math is all done mod 2^32 or 2^64, the implicit size of the integer T.

So in practice, T is a linear sum of all the stream values. The weight of the last value is 12345, the weight of the second to last value is 12345^2, the weight of the Nth to last value is 12345^N.

This constant C (12345 in this example) is something I can choose. I'd like to choose it randomly (at runtime) so different hash functions can be used for different instances of my algorithm.

Obviously this constant C needs to be ODD. If it wasn't, the powers of 2 would accumulate and after 32 or 64 (or fewer) values, the value of C^N mod 2^32 would end up 0 and we'd be hashing just the last values in the whole stream.

Now my question is what conditions on C will give C^N the longest period before it repeats back to 1?

In math terms, for what conditions of C gives C^n != 1 mod 2^32
for n=1..N for the largest N?

I think this has to do with the roots of 1 mod 2^N but it's not as easy a rule as I thought.

For example, mod 2^32, I get the following periods:

C=3 N=2^30
C=5 N=2^30
C=7 N=2^29
C=9 N=2^29
C=11 N=2^30
C=13 N=2^30
C=15 N=2^28
C=17 N=2^28
C=19 N=2^30


In the end I want tp pick large random values of C which have a full period as long as possible.. 2^30 in this case.

So.. back to my question. What defines the length of this period, and how can I efficiently pick random C which have the longest possible period?

Thanks!

I notice you bring up all but v again is there a reason is it pseudo-randomly picked ? is so then this question is made harder as v is also unknown and has influence on the C value needed.

[science_man_88]

effectively for N times through the loop you calculate T as (C^N*T) +(C^N*v)

but 3 of these variables are undefined to me, and hence the fourth as it changes based on those 3.

[WMHalsdorf]

Originally Posted by fenderbender

For example, mod 2^32, I get the following periods:

C=3 N=2^30
C=5 N=2^30
C=7 N=2^29
C=9 N=2^29
C=11 N=2^30
C=13 N=2^30
C=15 N=2^28
C=17 N=2^28
C=19 N=2^30


In the end I want tp pick large random values of C which have a full period as long as possible.. 2^30 in this case.

So.. back to my question. What defines the length of this period, and how can I efficiently pick random C which have the longest possible period?

Thanks!

You have to test C-1 for powers of 2.
To have the longest period the highest power of 2 will have to be 1.

[fenderbender]

Originally Posted by science_man_88

I notice you bring up all but v again is there a reason is it pseudo-randomly picked ? is so then this question is made harder as v is also unknown and has influence on the C value needed.

Actually what I expect to do is pick a random odd value for C and test it for whatever conditions are necessary to insure the longest period.
From empirical testing, half of all odd C give the maximum period so I shouldn't have to reject too many.

My post is to figure out just what those conditions on C are!

I can actually measure the period for the 2^32 case by a simple loop. It's not practical to test the period for 2^64.. it's about a week of computation.

[fenderbender]

Originally Posted by WMHalsdorf

You have to test C-1 for powers of 2.
To have the longest period the highest power of 2 will have to be 1.

This isn't sufficient.. if you look at the table of values I posted it doesn't match your conditions. C=13 has a power of 2^2 in C-1 but has the longest period. C=15 has a power of only 2^1 in C-1 but has a shorter period.

[Gammatester]

Originally Posted by WMHalsdorf

You have to test C-1 for powers of 2.
To have the longest period the highest power of 2 will have to be 1.

This is obviously wrong as the simplified version C=7 for 2^5 shows:
7 17 23 1

The sequence for 5 is:
5 25 29 17 21 9 13 1

and for 19:
19 9 11 17 3 25 27 1

These two samples have maximum length of 2^(5-2) = 8. I have already given the general solution for 2^m, m>=4. Choose C with C mod 8 = 3 or 5. Then the (maximum) length of the sequence is 2^(m-2).