Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Re: Modulo orders

Expand Messages
  • Sarad AV
    Hello, ... Finding a primive root in (Fp)* is easy if we know the prime factorisation of p-1. We do the following: 1.) Find the factorization of p-1. 2.) p-1=
    Message 1 of 3 , Jun 20, 2005
    • 0 Attachment
      Hello,

      > --- In primenumbers@yahoogroups.com, Jose Ramón Brox
      >
      > <ambroxius@t...> wrote:

      > > So, could we make that list in the group, sending
      > definitions,
      > theorems, facts, open
      > > problems... related with orders? Primitive roots,
      > discrete
      > logarithms... whatever. If you

      Finding a primive root in (Fp)* is easy if we know the
      prime factorisation of p-1.

      We do the following:

      1.) Find the factorization of p-1.

      2.) p-1= q1*q2*…*qn , the prime factors of p-1

      3.) Then we find
      Order1 = g^(p-1)/q1
      Order2 = g^(p-1)/q2
      [...]
      Ordern = g^(p-1)/qn

      4.) For (1<=i<=n), if any of Order_i = 1, the given
      element is not a generator. We test another random
      element less than p until we find a generator. There
      are precisely phi(p-1) generators in (Fp)*. You will
      eventually end up finding one.

      There are algorithms for solving the discrete log
      problem like the Siver-Pohlig-Hellman which rely on
      our ability to factor p-1 and the algorithm works well
      when all the factors of p-1 are small.

      Sarad.


      __________________________________________________
      Do You Yahoo!?
      Tired of spam? Yahoo! Mail has the best spam protection around
      http://mail.yahoo.com
    Your message has been successfully submitted and would be delivered to recipients shortly.