FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
Period of random number generators
Post new topic   Reply to topic Page 1 of 1 [10 Posts] View previous topic :: View next topic
Author Message
DGoncz@aol.com
science forum Guru Wannabe


Joined: 25 Oct 2005
Posts: 122

PostPosted: Thu Jul 13, 2006 7:04 pm    Post subject: Re: Period of random number generators Reply with quote

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
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Thu Jul 13, 2006 6:47 pm    Post subject: Re: Period of random number generators Reply with quote

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

PostPosted: Thu Jul 13, 2006 6:21 pm    Post subject: Re: Period of random number generators Reply with 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:
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

PostPosted: Thu Jul 13, 2006 5:54 pm    Post subject: Re: Period of random number generators Reply with quote

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

PostPosted: Thu Jul 13, 2006 2:51 pm    Post subject: Re: Period of random number generators Reply with 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:

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

PostPosted: Thu Jul 13, 2006 1:34 pm    Post subject: Re: Period of random number generators Reply with quote

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
Back to top
DGoncz@aol.com
science forum Guru Wannabe


Joined: 25 Oct 2005
Posts: 122

PostPosted: Thu Jul 13, 2006 9:59 am    Post subject: Re: Period of random number generators Reply with 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:
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
Back to top
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Thu Jul 13, 2006 3:52 am    Post subject: Re: Period of random number generators Reply with quote

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:

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 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
Back to top
Gerry Myerson
science forum Guru


Joined: 28 Apr 2005
Posts: 871

PostPosted: Thu Jul 13, 2006 3:31 am    Post subject: Re: Period of random number generators Reply with quote

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) | 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)
Back to top
DGoncz@aol.com
science forum Guru Wannabe


Joined: 25 Oct 2005
Posts: 122

PostPosted: Thu Jul 13, 2006 1:48 am    Post subject: Period of random number generators Reply with 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?

Doug
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [10 Posts] View previous topic :: View next topic
The time now is Tue Nov 21, 2017 6:06 am | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0269s ][ Queries: 20 (0.0046s) ][ GZIP on - Debug on ]