Re: Periodicity of a^n mod c

From: Doug Goncz (dgoncz_at_aol.com)
Date: 09/25/04 

Date: 25 Sep 2004 00:52:19 GMT

>From: James Waldby j-waldby@pat7.com

>Message-ID: <415450D9.AEBAC634@pat7.com>

>I think the reason Marsaglia (and Knuth) concentrate on those cases
>is that they lead to maximum-length sequences from linear congruential
>random number generators.

Yes.

>>From before, you quoted two formulae for cycle-lengths t of the sequence
>a^n % p^B, which are [writing % for mod; (,) for gcd; and | for divides]
> [i] t = p^B/(a-1,p^B) when a%p == 1
> [ii] t = 2*p^B/(a+1,p^B) when a%p == -1
>with B>0, p odd prime.

To write is to learn.

0 < a < c
(a,c) = 1
a^0 = 1 trivially
c = p^B
0 < t
a^t % c = 1
0 < h < t
a^h % c != 1

Yes? Is this a suitable definition of t?

t | phi(c)
phi(p^B) = (p-1)/(p^(B-1))
phi(p^B) < p^B
t< p^B
t<c

>Now phi(p^B) = (p-1)(p^(B-1)) < p^B therefore t < p^B.
>If (a,p)=1 and a%p != 1, then (a-1,p^B)=1 and [i] reduces to t = p^B
>which cannot be.

Agreed. [i] does not apply. t < p^B.

But how do I get from (a,p)=1 and a%p != 1 to

(a-1, p^B) = 1?

It's as if, in between, (a-1, p) = 1....

Are we looking at something like, say:

(a,p) = 1
a % p != m so
(a-m , p^B) = 1?

if a%p != m then a-m % p != 0

is that why (a-m , p^B) = 1?

> If (a,p)=1 and a%p != -1, then (a+1,p^B)=1 and
>[ii] reduces to t = 2*p^B > phi(p^B) which cannot be.

Yes, this would happen the same way. Did I get it?

Yours,
Doug Goncz ( ftp://users.aol.com/DGoncz/incoming )
Student member SAE for one year.
I love: Dona, Jeff, Kim, Mom, Neelix, Tasha, and Teri, alphabetically.
I drive: A double-step Thunderbolt with 657% range.

Quantcast