Author 
Message 
DGoncz@aol.com science forum Guru Wannabe
Joined: 25 Oct 2005
Posts: 122

Posted: Thu Jul 13, 2006 1:48 am Post subject:
Period of random number generators



Hello, sci.math.
I am confused about the period of the random number generator (a^n +
b^n) mod c.
Assuming a, b, and c pairwise coprime, as is usually done to maximize
period, that is...
t is used to represent the period of a random number generator in many
writings.
t((a^n) mod c)  c1 where  means divides.
That's has something to do with 0 being "forbidden"; if (a,c)=1 then
a^n =/= 0 mod c. It just can't happen for any power of a. Er, any
postive power?
Arithmetically (a^n + b^n) mod c = ((a^n) mod c + (b^n) mod c) mod c
0 is not forbidden because (a^n) mod c + (b^n) mod c can equal c.
So does t( ( a^n + b^n ) mod c ) divide c, or c1, or what?
Doug 

Back to top 


Gerry Myerson science forum Guru
Joined: 28 Apr 2005
Posts: 871

Posted: Thu Jul 13, 2006 3:31 am Post subject:
Re: Period of random number generators



In article <1152755326.219017.207450@75g2000cwc.googlegroups.com>,
"Doug Goncz" <DGoncz@aol.com> wrote:
Quote:  I am confused about the period of the random number generator (a^n +
b^n) mod c.
Assuming a, b, and c pairwise coprime, as is usually done to maximize
period, that is...
t is used to represent the period of a random number generator in many
writings.
t((a^n) mod c)  c1 where  means divides.
That's has something to do with 0 being "forbidden"; if (a,c)=1 then
a^n =/= 0 mod c. It just can't happen for any power of a. Er, any
postive power?
Arithmetically (a^n + b^n) mod c = ((a^n) mod c + (b^n) mod c) mod c
0 is not forbidden because (a^n) mod c + (b^n) mod c can equal c.
So does t( ( a^n + b^n ) mod c ) divide c, or c1, or what?

Working mod c, a^(n + c  1) + b^(n + c  1) = a^n + b^n,
so certainly the period divides c  1.

Gerry Myerson (gerry@maths.mq.edi.ai) (i > u for email) 

Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Thu Jul 13, 2006 3:52 am Post subject:
Re: Period of random number generators



Doug Goncz wrote:
Quote:  Hello, sci.math.
I am confused about the period of the random number generator (a^n +
b^n) mod c.
Assuming a, b, and c pairwise coprime, as is usually done to maximize
period, that is...
t is used to represent the period of a random number generator in many
writings.
t((a^n) mod c)  c1 where  means divides.
That's has something to do with 0 being "forbidden"; if (a,c)=1 then
a^n =/= 0 mod c. It just can't happen for any power of a. Er, any
postive power?
Arithmetically (a^n + b^n) mod c = ((a^n) mod c + (b^n) mod c) mod c
0 is not forbidden because (a^n) mod c + (b^n) mod c can equal c.
So does t( ( a^n + b^n ) mod c ) divide c, or c1, or what?

Hi, Doug:
Assuming that the "period" you are asking about refers
to what value of n gives rising to a repeating sequence,
think in terms of Fermat's little theorem.
Since a,b are relatively prime to c, we have (a,b,c > 1):
a^phi(c) = 1 mod c
b^phi(c) = 1 mod c
where phi(c) is the Euler phi function of c, ie. the number
of integers between 1 and c1 that are coprime to c.
So the period is a divisor of phi(c), because:
a^0 + b^0 = a^phi(c) + b^phi(c) mod c
and similarly with any exponent that is a multiple of ph(c).
regards, chip 

Back to top 


DGoncz@aol.com science forum Guru Wannabe
Joined: 25 Oct 2005
Posts: 122

Posted: Thu Jul 13, 2006 9:59 am Post subject:
Re: Period of random number generators



Gerry and Chip have shown t( ( (a^n) + (b^n) ) mod c)  phi (c) or c1.
Are any values forbidden? It seems to me that exactly one value must be
forbidden for this RNG to have such possible periods.
Doug
Doug Goncz (I) wrote:
Quote:  Hello, sci.math.
I am confused about the period of the random number generator (a^n +
b^n) mod c.
Assuming a, b, and c pairwise coprime, as is usually done to maximize
period, that is...
t is used to represent the period of a random number generator in many
writings.
t((a^n) mod c)  c1 where  means divides.
That's has something to do with 0 being "forbidden"; if (a,c)=1 then
a^n =/= 0 mod c. It just can't happen for any power of a. Er, any
postive power?

Yes, we are talking about postive powers here.
Quote:  Arithmetically (a^n + b^n) mod c = ((a^n) mod c + (b^n) mod c) mod c
0 is not forbidden because (a^n) mod c + (b^n) mod c can equal c.
So does t( ( a^n + b^n ) mod c ) divide c, or c1, or what?
Doug 


Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Thu Jul 13, 2006 1:34 pm Post subject:
Re: Period of random number generators



Doug Goncz wrote:
Quote:  Gerry and Chip have shown t( ( (a^n) + (b^n) ) mod c)  phi (c) or c1.
Are any values forbidden? It seems to me that exactly one value must be
forbidden for this RNG to have such possible periods.
Doug
Doug Goncz (I) wrote:
Hello, sci.math.
I am confused about the period of the random number generator (a^n +
b^n) mod c.
Assuming a, b, and c pairwise coprime, as is usually done to maximize
period, that is...
t is used to represent the period of a random number generator in many
writings.
t((a^n) mod c)  c1 where  means divides.
That's has something to do with 0 being "forbidden"; if (a,c)=1 then
a^n =/= 0 mod c. It just can't happen for any power of a. Er, any
postive power?
Yes, we are talking about postive powers here.
Arithmetically (a^n + b^n) mod c = ((a^n) mod c + (b^n) mod c) mod c
0 is not forbidden because (a^n) mod c + (b^n) mod c can equal c.
So does t( ( a^n + b^n ) mod c ) divide c, or c1, or what?
Doug

The value c1 is correct only if c is prime, when phi(c) = c1.
regards, chip 

Back to top 


DGoncz@aol.com science forum Guru Wannabe
Joined: 25 Oct 2005
Posts: 122

Posted: Thu Jul 13, 2006 2:51 pm Post subject:
Re: Period of random number generators



Anybody, under which condition would it be correct to write
t((a^n) + b^n) mod c) = lcm ( t((a^n) mod c, t((b^n) mod c) ?
Doug Goncz (I) wrote:
Quote:  Hello, sci.math.
I am confused about the period of the random number generator (a^n +
b^n) mod c.
Assuming a, b, and c pairwise coprime, as is usually done to maximize
period, that is...
t is used to represent the period of a random number generator in many
writings.

Doug 

Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Thu Jul 13, 2006 5:54 pm Post subject:
Re: Period of random number generators



Doug Goncz wrote:
Quote:  Anybody, under which condition would it be correct to write
t((a^n) + b^n) mod c) = lcm ( t((a^n) mod c, t((b^n) mod c) ?
Doug Goncz (I) wrote:
Hello, sci.math.
I am confused about the period of the random number generator (a^n +
b^n) mod c.
Assuming a, b, and c pairwise coprime, as is usually done to maximize
period, that is...
t is used to represent the period of a random number generator in many
writings.

Hi, Doug:
To adopt your notation, if gcd( t((a^n) mod c, t((b^n) mod c ) = 1
then t((a^n) + b^n) mod c) = lcm ( t((a^n) mod c, t((b^n) mod c).
However it is not true in general as the following example shows,
even if a,b,c are coprime.
Let a = 4, b = 7, c = 9. Then a,b are both of multiplicative order
3 in Z/9Z*, but the sequence a^n + b^n mod c is simply constant:
(4 + 7) mod 9 = 2
(16 + 49) mod 9 = 2
(64 + 343) mod 9 = 2,
etc.
regards, chip 

Back to top 


DGoncz@aol.com science forum Guru Wannabe
Joined: 25 Oct 2005
Posts: 122

Posted: Thu Jul 13, 2006 6:21 pm Post subject:
Re: Period of random number generators



Er, I guess then
t((a^n) + (b^n) mod c)  lcm ( t((a^n) mod c, t((b^n) mod c)
right, Chip?
Doug
Chip Eastham wrote:
Quote:  Doug Goncz wrote:
Anybody, under which condition would it be correct to write
t((a^n) + b^n) mod c) = lcm ( t((a^n) mod c, t((b^n) mod c) ?
Doug Goncz (I) wrote:
Hello, sci.math.
I am confused about the period of the random number generator (a^n +
b^n) mod c.
Assuming a, b, and c pairwise coprime, as is usually done to maximize
period, that is...
t is used to represent the period of a random number generator in many
writings.
Hi, Doug:
To adopt your notation, if gcd( t((a^n) mod c, t((b^n) mod c ) = 1
then t((a^n) + b^n) mod c) = lcm ( t((a^n) mod c, t((b^n) mod c).
However it is not true in general as the following example shows,
even if a,b,c are coprime.
Let a = 4, b = 7, c = 9. Then a,b are both of multiplicative order
3 in Z/9Z*, but the sequence a^n + b^n mod c is simply constant:
(4 + 7) mod 9 = 2
(16 + 49) mod 9 = 2
(64 + 343) mod 9 = 2,
etc.
regards, chip 


Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Thu Jul 13, 2006 6:47 pm Post subject:
Re: Period of random number generators



Doug Goncz wrote:
Quote:  Er, I guess then
t((a^n) + (b^n) mod c)  lcm ( t((a^n) mod c, t((b^n) mod c)
right, Chip?
Doug
Chip Eastham wrote:
Doug Goncz wrote:
Anybody, under which condition would it be correct to write
t((a^n) + b^n) mod c) = lcm ( t((a^n) mod c, t((b^n) mod c) ?
Doug Goncz (I) wrote:
Hello, sci.math.
I am confused about the period of the random number generator (a^n +
b^n) mod c.
Assuming a, b, and c pairwise coprime, as is usually done to maximize
period, that is...
t is used to represent the period of a random number generator in many
writings.
Hi, Doug:
To adopt your notation, if gcd( t((a^n) mod c, t((b^n) mod c ) = 1
then t((a^n) + b^n) mod c) = lcm ( t((a^n) mod c, t((b^n) mod c).
However it is not true in general as the following example shows,
even if a,b,c are coprime.
Let a = 4, b = 7, c = 9. Then a,b are both of multiplicative order
3 in Z/9Z*, but the sequence a^n + b^n mod c is simply constant:
(4 + 7) mod 9 = 2
(16 + 49) mod 9 = 2
(64 + 343) mod 9 = 2,
etc.
regards, chip

Yes, that much we can prove!
regards, chip 

Back to top 


DGoncz@aol.com science forum Guru Wannabe
Joined: 25 Oct 2005
Posts: 122

Posted: Thu Jul 13, 2006 7:04 pm Post subject:
Re: Period of random number generators



Chip Eastham wrote:
Quote:  Doug Goncz wrote:
Er, I guess then
t((a^n) + (b^n) mod c)  lcm ( t((a^n) mod c, t((b^n) mod c)
right, Chip?
Yes, that much we can prove!
regards, chip

Awsome! I take nap now... zzzzzz....
Doug 

Back to top 


Google


Back to top 



The time now is Wed Jun 20, 2018 7:47 am  All times are GMT

