> 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 John Cremona writes: > On 11 May 2017 at 08:16, Vincent Delecroix <20100.delecr...@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 > >> >> For very large p such as what you asked for is likely to be delicate (but I >> am not a specialist). >> >> Vincent >> >> >> On 11/05/2017 08:45, Johan S. H. Rosenkilde wrote: >>> >>> 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 >>> >>> >>> Panos Phronimos writes: >>> >>>> 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 >>> >>> >> >> -- >> 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+unsubscr...@googlegroups.com. >> To post to this group, send email to sage-support@googlegroups.com. >> Visit this group at https://groups.google.com/group/sage-support. >> For more options, visit https://groups.google.com/d/optout. -- 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+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
