20101115, 05:59  #1 
Jul 2007
17 Posts 
Roots of 1 mod 2^n
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! 
20101115, 12:22  #2 
Mar 2009
2×19 Posts 
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 C1 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. 
20101115, 12:41  #3 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
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. 
20101115, 13:30  #4 
Mar 2009
2×19 Posts 
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. 
20101115, 13:59  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Last fiddled with by science_man_88 on 20101115 at 13:59 

20101115, 14:04  #6  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20101115, 14:11  #7 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
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. 
20101115, 17:19  #8  
Feb 2005
Bristol, CT
1001_{8} Posts 
Quote:
To have the longest period the highest power of 2 will have to be 1. Last fiddled with by WMHalsdorf on 20101115 at 17:41 Reason: Only need to test C1 

20101115, 19:05  #9  
Jul 2007
17 Posts 
Quote:
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. 

20101115, 19:09  #10 
Jul 2007
17 Posts 
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 C1 but has the longest period. C=15 has a power of only 2^1 in C1 but has a shorter period.

20101115, 19:19  #11  
Mar 2009
100110_{2} Posts 
Quote:
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^(52) = 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^(m2). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Extracting kth roots mod m  Dubslow  Miscellaneous Math  8  20121213 21:35 
primtive roots mod p^2  Peter Hackman  Math  2  20071024 06:41 
Perfect roots  grandpascorpion  Puzzles  4  20061001 13:57 
Primitive Roots  Numbers  Math  16  20050921 23:41 
What is the roots of NFS algorithm?  Annunaki  NFSNET Discussion  7  20030729 16:01 