One way or the other, the bottleneck is in the primitivity test. On Friday, May 12, 2017 at 4:36:20 AM UTC+1, Venkataraman S wrote: > > 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. >
-- 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.
