Hey there! Sign in to join this conversationNew here? Join for free

periodicity in the discrete log algorithm modulo a prime Watch

    • Thread Starter
    Offline

    0
    ReputationRep:
    so I was playing around with the discrete log algorithm and found that if we compute

    10^{k}\mod  53 for k  \epsilon \mathbb{Z} _{53}, 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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    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
 
 
 
  • 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
    Will you be richer or poorer than your parents?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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

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