Search   Memberlist   Usergroups
 Page 1 of 1 [10 Posts]
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) | c-1 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 c-1, or what?

Doug
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

"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) | c-1 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 c-1, 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)
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) | c-1 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 c-1, or what?

Hi, Doug:

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 c-1 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
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 c-1.

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) | c-1 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 c-1, or what? Doug
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 c-1. 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) | c-1 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 c-1, or what? Doug

The value c-1 is correct only if c is prime, when phi(c) = c-1.

regards, chip
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
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
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
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
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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [10 Posts]
 The time now is Tue Sep 25, 2018 1:10 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am a subset of natural number levine121323@yahoo.com Math 1 Fri Jul 21, 2006 6:17 am reference books for formulaes in stochastic analysis and ... Michael11 Math 0 Thu Jul 20, 2006 12:38 am spectrum of a symmetric tridiagonal random matrix pf.buonsante@gmail.com Math 0 Wed Jul 19, 2006 9:45 am Another look at triangle number factoring. Dan11 Math 2 Tue Jul 18, 2006 7:05 pm