Ticket #210 (closed enhancement: fixed)
[with patch, positive review] discrete log and other generic functions
|Reported by:||was||Owned by:||somebody|
From David Kohel: > ... dlog in SAGE mod p is slow. Anyway, yes, PARI has a function znlog, which should be very fast: gp.znlog I'll have to add it to the PARI interface (libs/pari/gen.pyx) then that should give a very fast implementation mod p for p a not-too-big prime. E.g., -------------------- sage: p = 2^32+61 sage: a = gp.znprimroot(p); a Mod(2, 4294967357) sage: time gp.znlog(97, a) 498735128 CPU time: 0.00 s, Wall time: 0.05 s -------------------- I'm really glad I'm not writing everything in SAGE from scratch! If somebody on sage-dev sends me a patch that does what you want (see email below) instead of me having to do it, that would be nice... I won't work on this until probably a day from now... -- William On Mon, 22 Jan 2007 21:51:52 -0800, David R. Kohel <email@example.com> wrote: > Hi William, David, > > I produced the following baby examples in Magma for use in my course. > > First a prime for which p-1 is smooth: > > sage: p = 2^32+15 > sage: (p-1).factor() > 2 * 3^2 * 5 * 131 * 364289 > > Then one containing a "large" prime factor: > > sage: p = 2^32+61 > sage: (p-1).factor() > 2^2 * 1073741839 > > Both should take relatively trivial time to solve discrete logarithms, > but the former "should" recognize by initial trial division that the > problem is much easier. > > Unfortunately the problem in my book doesn't come back snappily: > > sage: FF = FiniteField(p) > sage: c = FF(4294967356) > sage: x = FF(2) > sage: c.log(x) > > This gets down to the following function: > > return arith.discrete_log_generic(self, a, n) # TODO update this function > > which does a BSGS (not even Pollard rho). > > Shouldn't Pari or gmp have a more reasonable implementation? > > This is at the level of IntegerMod_abstract rather than finite fields. > > --David > >
- Summary changed from discrete log to [with patch, needs review] discrete log and other generic functions
- Summary changed from [with patch, needs review] discrete log and other generic functions to [with patch, positive review] discrete log and other generic functions
Note: See TracTickets for help on using tickets.