Discrete Logarithm

[Panos Phronimos]

Hello everyone,

I am trying to calculate a primitive element (g) of a big Finite Field:
GF(p) where p is prime number > 2^2048

So then, i could share a secret integer (r) as: m=g^r, but it seems impossible to calculate it with function primitive_element()
Is there another way i can use to calculate it?

Thanks in advance,
Panos

[Johan S. H. Rosenkilde]

Hi Panos

In GF(p) then an element g is primitive if its embedding into ZZ is
coprime with p-1. Since Euclidean algorithm is so fast, you can test
this:

sage: p = Primes().next(2^2048) #long
sage: g1 = 3
sage: gcd(g1, p-1)
3
sage: g2 = 5
sage: gcd(g2, p-1)
1

So 3 is not a primitive element in GF(p) but 5 is. (Since 5 is also a
prime, you could also have done g2.divides(p-1) instead)

Best,
Johan

[Vincent Delecroix]

Hi,

"primitive element" is meant as "generator for the multiplicative group
GF(p)^*" and not the additive group GF(p). The OP question is about the
former and Johan answer is about the latter.

For very large p such as what you asked for is likely to be delicate
(but I am not a specialist).

Vincent

[John Cremona]

On 11 May 2017 at 08:16, Vincent Delecroix <20100.d...@gmail.com> wrote:
> Hi,
>
> "primitive element" is meant as "generator for the multiplicative group
> GF(p)^*" and not the additive group GF(p). The OP question is about the
> former and Johan answer is about the latter.

Not really: generators of the additive group are coprime to p, not to p-1.

Perhaps Johan was thinking of the fact that if g is one multiplicative
generator (aka primitive root) then g^k is another if and only if
gcd(k,p-1)=1.

John Cremona

> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[Johan S. H. Rosenkilde]

> "primitive element" is meant as "generator for the multiplicative group
> GF(p)^*" and not the additive group GF(p). The OP question is about the
> former and Johan answer is about the latter.

Yes, I just realised that too - sorry about the noise. I'll think more
about the multiplicative group but offhand I don't really know...

Best,
Johan

[Dima Pasechnik]

Typically, a large proportion (specifically, phi(p-1), for phi() being Euler totient function) of GF(p)* consists of primitive elements.

I don't think anything better than picking an element at random and checking its primitivity is known.

   

Thanks in advance,
Panos

[Johan S. H. Rosenkilde]

> Not really: generators of the additive group are coprime to p, not to p-1.
>
> Perhaps Johan was thinking of the fact that if g is one multiplicative
> generator (aka primitive root) then g^k is another if and only if
> gcd(k,p-1)=1.

I think I should just not answer sage-support questions before properly
waking up...

In Cohen's "A course in computational number theory" he says (p. 25):
"To find a primitive root modulo p there seems to be no better way than
to proceed as follows", and then gives an algorithm which is essentially
what Dima suggested, trying 2, 3, ... until a primitive element is
found. Primitivity is tested by factoring p-1.

Best,
Johan

[Venkataraman S]

The German school thinks differently. There is a different (well known) algorithm due to Gauss. Take an arbitrary number a coprime to p. Find its order. If it is the primitive root, we are done. If not, choose another b and check whether order of ab is greater than the order of a. If it is, replace a by ab and repeat the procedure. If the order of ab is less than order of b, look for another b such that order of ab is greater than a. We get a sequence of elements whose orders are strictly increasing. Since the order is finite, the process must stop at some point yielding a primitive root. It is discussed in one of the books, either Zassenhaus and Pohst, or the slim volume written by Pohst.

[Dima Pasechnik]

One way or the other, the bottleneck is in the primitivity test.

[Venkataraman S]

I vaguely remember that if one can quickly find a quadratic non-residue, one can find a primitive root fast. I don't remember the exact connection now. Does anybody in the group have any reference?

[Justin C. Walker]

On May 12, 2017, at 20:52 , Venkataraman S wrote:

> I vaguely remember that if one can quickly find a quadratic non-residue, one can find a primitive root fast. I don't remember the exact connection now. Does anybody in the group have any reference?

Internet search can be helpful in times like this. Also, Cohen's "Course" is a great place to look.

HTH

Justin

--
Justin C. Walker, Curmudgeon at Large
Institute for the Absorption of Federal Funds
-----------
If it weren't for carbon-14, I wouldn't date at all.
-----------

[Panos Phronimos]

To whoever has the same problem in the future,

To solve my problem, I finally used Safe Primes so the procedure of finding a generator becomes really simpler.

Thanks everyone for your answers.