On 16/02/2008, David Kohel <[EMAIL PROTECTED]> wrote: > > Hi John, > > > I'm not sure I understand the end of your message. Nowhere does the > > code I have in mind assume that anything is cyclic, let alone of prime > > order: the bsgs and dlog functions will terminate if there is no > > solution, with a ValueError. > > Since baby-step, giant-step is deterministic, you can do so. A > Pollard-rho > algorithm is probabilistic with similar expected runtime, but often > faster, > and uses less memory. However, it can fail to terminate if the > discrete > logarithm is not satisfied. For generic abelian groups one should > have > both BSGS and Pollard rho algorithms available, and it should be > possible > to use exponent or group order bounds, exact group exponents and > orders, > and factored group orders, when this information is available.
I agree with all that. In my bsgs for elliptic curves, I use the group order if it is known, otherwise the Hasse bounds, and cache the factorization of the order. John > > --David > > > -- John Cremona --~--~---------~--~----~------------~-------~--~----~ 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://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
