> --- In email@example.com, Jose Ramón Brox
> <ambroxius@t...> wrote:
> > So, could we make that list in the group, sending
> theorems, facts, open
> > problems... related with orders? Primitive roots,
> 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.
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around