This link gives information on the methods used by Magma http://magma.maths.usyd.edu.au/magma/htmlhelp/text565.htm
If I computed correctly then none of -1, -2, -3, -7, or -11 are quadratic residues mod p. Hence it seems Magma used the standard linear sieve in this example. This is what http://www.cs.toronto.edu/~cvs/dlog also uses. I wonder what accounts for the huge time difference. Perhaps the following: in http://www.cs.toronto.edu/~cvs/dlog the author uses the Lanczos algorithm for the linear algebra phase. It is stated in the Magma manual that this makes the search for discrete logs much slower (but also uses less memory). Michel To David Kohel: index calculus for discrete logs uses linear algebra mod p-1 (not 2). For factorization it needs only linear algebra mod 2. On Mar 25, 2:13 am, "William Stein" <[EMAIL PROTECTED]> wrote: > On 3/24/07, Michel <[EMAIL PROTECTED]> wrote: > > > > > > > I tested the plain version. It computed the log of > > > y=74854337848345720324273746248836352273 > > > modulo > > > p=241336555202451377063690009552755901639 > > (128bit) > > with base > > g=132937783468242454805077125996488454291 > > > in 15704.5 (setup time) + 18681.4 seconds on a 1.6GHz > > laptop with 1Gb. > > (the answer is 4711999358070443542788028291655182016) > > > I don't know how competitive this is (what does Magma do?). > > On the 1.8Ghz sage.math, Magma does this in 3 minutes (186.389 seconds) total, > which is vastly faster than the 9.5 hours that > <http://www.cs.toronto.edu/~cvs/dlog> > took to do the problem. I don't know what MAGMA is doing though. > > INPUT TO MAGMA: > y:=74854337848345720324273746248836352273; > p := 241336555202451377063690009552755901639; > g := 132937783468242454805077125996488454291; > time d := Log(GF(p)!g, GF(p)!y); > print d; > > OUTPUT > Magma V2.13-5 Sat Mar 24 2007 03:51:57 on sage [Seed = 71778470] > Type ? for help. Type <Ctrl>-D to quit. > Time: 185.600 > 4711999358070443542788028291655182016 > > Total time: 186.389 seconds, Total memory usage: 466.02MB > > -- William > > The > > > > > program only > > works for primes of the form p=rq+1 with q prime and r small. > > This is because one needs to do linear algebra modulo p-1 > > and for this one needs to know the factorization of p-1. > > > (In the accompagnying paper the author states however > > that one can pretend (p-1)/2 to be prime. Either the linear algebra > > works, or it doesn't. In the latter case one discovers a factor of > > p-1. > > This idea does not seem to be implemented however). > > > There is a also a version which uses the NFS but the author > > seems to imply it is less stable. > > > Michel > > > On Mar 24, 12:00 am, "Justin C. Walker" <[EMAIL PROTECTED]> wrote: > > > On Mar 23, 2007, at 10:16 , Michel wrote: > > > > > That looks like a good link. I just read through the article there and > > > > the author > > > > really seems to know his stuff. > > > > > There is GPL'ed code for the index calculus method over GF(p) > > > > as well as some other things. I didn't managed to compile it (yet?) > > > > as I don't have NTL installed outside sage. > > > > I think you should be able to do this by changing NTLPREFIX in the > > > Makefile to point to the library and headers in SAGE_ROOT. > > > > Justin > > > > -- > > > Justin C. Walker, Curmudgeon at Large > > > Director > > > Institute for the Enhancement of the Director's Income > > > ----------- > > > Nobody knows the trouble I've been > > > ----------- > > -- > William Stein > Associate Professor of Mathematics > University of Washingtonhttp://www.williamstein.org --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
