## Re: [PrimeNumbers] Re: Modulo orders

Expand Messages
• 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
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.