You are Here: Home >< Maths

# periodicity in the discrete log algorithm modulo a prime Watch

1. so I was playing around with the discrete log algorithm and found that if we compute

for , then this is periodic with period 13 - wolfram alpha has the values here.

My question is whether this is a coincidence, or is there anything special about 10 and 53?

It also turns out that 4,6,7,9 and 11 are periodic with period 26. obviously periods will divide p-1. I haven't checked any higher bases.

Is something going on here?

(Also considering encryption with Diffie–Hellman is it a weakness if the base you choose is periodic modulo your prime? Is there a way of determining whether it is periodic or not, apart from actually checking?)

I think I might be missing something extremely obvious. anyway. any info would be appreciated, thanks in advance.
2. I've been doing a few more calculations, and it keeps on getting stranger, and it feels like I keep on understanding less.

However I now know after a bit of research that if we choose our prime to be a 'safe prime' i.e. p, s.t. p= 2q+1, where q is prime, then the only possible periods are 1,2,q and p. Ideally we want a period of p, so since periods of 1 and 2 are trivial (bases 1 and (p-1) respectively) we only need to check the value of b^q mod p. if this is congurent to 1, then our base b has periodicity q.

So, experimenting with large primes of this form, for example 1000667=2.500333+1, we have for example, choosing a base of 37997 (which happens to be prime), that 37997^500333 (mod 1000667) is congruent to 1. hence this base may not be appropriate.

then I chose as another example 40009 (also prime) we have 40009^500333 (mod 1000667) is 1000666 or -1, hence 40009 will have period p. or will it? is the value of -1 significant?

i might now take a look at primes of this form in general, then try to look at all bases, and find their periods, and try to see if some patterns emerge.

One thing I was also wondering was whether the discrete log is suitable for pseudorandom number generation? my instinct says no, since each number is exactly dependent on the one before. however given a large enough modulus and, staying with in periodicity, exactly how random are the numbers? i have looked at some statistical tests to determine randomness, but it is complicated. i'm sure there is an answer somewhere.
3. So i've narrowed it down. conjecture: working modulo p, if p-1 =mn, then a^m will be congruent to exactly n different values. (if a is not a multiple of p)

eg if m= p-1, then it will take one value (1) via FLT.

eg working mod 7

7-1 =6 = 2.3

so x^2 will take 3 different values: wolfram alpha (1,2,4)

similarly x^3 will take 2 different values: wolfram alpha (1,-1)

is this a basic corollary of some theorem?

EDIT: p is prime, as before

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: December 4, 2010
Today on TSR

### Oxford grad sues for £1m

Claims damages because he didn't get a first

### Oxford Circus station evacuated

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.