Results 1 to 3 of 3
Like Tree3Thanks
  • 1 Post By Sylvia104
  • 2 Post By Deveno

Math Help - generator of Z*p

  1. #1
    Newbie
    Joined
    Apr 2012
    From
    lebanon
    Posts
    18

    generator of Z*p

    if p,q are primes with p=2q+1, and we pick a random number g in Z*p, what is the probability that g is a generator of Z*p?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    Re: Generator of Z*p

    \mathbb Z_p^\times is cyclic of order p-1=2q and so has \varphi(2q) generators. The probability of picking a generator is thus

    \frac{\varphi(2q)}{2q}\ =\ \left\{ \begin{array} {cl} \dfrac12 & \text{if}\ q=2 \\\\ \dfrac{q-1}{2q} & \text{if}\ q>2 \end{array} \right.
    Thanks from billobillo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,397
    Thanks
    760

    Re: generator of Z*p

    note that if q is very large this is "nearly" 1/2 (even for the relatively small q = 3 it's already 1/3 (approx. 33%) and for q = 5 it's jumped to 2/5 (40%)). these odds are good enough that it often suffices to check 2,3,5 and 7 as possible generators for small values of p (i think 109 is the first prime where you have to use something else, and 6 works there, 191 is the smallest prime that has a relatively "large" smallest primitive element (19)...note that both of these are not of the form considered here since neither 54 nor 95 is prime).

    this is good news, since it's not always easy to tell if a given number *is* a generator. as far as i know, trial-and-error is still the best method.
    Thanks from Sylvia104 and billobillo
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generator for an ideal
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 4th 2011, 06:30 AM
  2. generator for groups.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 29th 2010, 12:10 AM
  3. Generator
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 27th 2010, 12:41 AM
  4. Generator of group
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 27th 2010, 12:24 AM
  5. generator matrix
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: November 22nd 2008, 12:06 AM

Search Tags


/mathhelpforum @mathhelpforum