I think that a database of the smallest primitive root for lots of primes would be useful, just to save time. Note that this information if cached should also be used by the function multiplicative_generator() for GF(p).
There is certainly no point in listing all of them for a given p! If g is one then the complete list is g**e mod p for e in range(p-1) where gcd(e,p-1)=1 I don't think this will help in solving dlog problems; what kcrisman says below about Artin's conjecture is true (it states that every integer which is not -1 or a square is a primitive root for infinitely many primes p). John 2009/7/31 kcrisman <[email protected]>: > > Most older # theory textbooks (or newer editions thereof) have a list > of smallest primitive roots of p for "small" p, as well as tables of > indices for index calculus. I'm not sure whether that is quite as > useful now, since any individual discrete log problem might be solved > (slowly) by finding a primitive root and then using that... It > couldn't hurt, of course. > > You should look for things related to the Artin conjecture if you > really want to know who might be interested in such tables or > calculations - I'm sure people researching this have done so. Gauss > in particular conjectured that 1/p has repeating decimal of length p-1 > for infinitely many p, which (if true) would prove the Artin > conjecture with n=10 (i.e., 10 is a primitive root for infinitely many > p). I think I have that right :) > > - kcrisman > > > On Jul 31, 7:06 am, Minh Nguyen <[email protected]> wrote: >> Hi David, >> >> On Fri, Jul 31, 2009 at 7:31 PM, David Joyner<[email protected]> wrote: >> >> > If you just recorded the smallest primitive roots I'll bet the database >> > would get a lot smaller:-) Do you need all the prim roots in the >> > CrypTool tutorial for a particular purpose, eg discrete logs? >> >> That is part of a chapter on number theory for cryptography. The >> chapter discusses primitive roots so I introduced the Sage command >> primitive_root() and wrote some code to do simple calculations >> relating to primitive roots. >> >> > I'd guess a database of the smallest prim roots mod p for all primes >> > out to a million (for starters) would be interesting to some >> > number-theorists. >> > I did a google search and could not find much online. >> >> Cool. Then I have a pretext to make more use of the machine sage.math :-) >> >> > I did find >> >> > Western, A. E. and Miller, J. C. P. Tables of Indices and Primitive >> > Roots. Cambridge, England: >> > Cambridge University Press, pp. xxxvii-xlii, 1968, >> >> > although I couldn't find what it had, and this page >> >http://www.ieeta.pt/~tos/p-roots.html >> > has a link to some related data. >> >> The author of that page also has done computations with the 3n + 1 >> conjecture. Earlier this year, I did some simple calculations relating >> to that conjecture. Perhaps I should revive that mini project. >> >> -- >> Regards >> Minh Van Nguyen > > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send an email to [email protected] To unsubscribe from this group, send an email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
