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 Washington http://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/ -~----------~----~----~----~------~----~------~--~---
