David, 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.
I don't currently use the Weil pairing in the elliptic curve case. But for any derived class where extra structure means that a customised algorithm would have better performance than the black box one can just implement its own special-purpose algorithm. As a special case of the above, the general-purpose algorithms are *not* intended to be used for groups of cryptographic size! The documentation makes (or will make) this clear. John On 14/02/2008, David Kohel <[EMAIL PROTECTED]> wrote: > > Hi, > > I find this discussion interesting since this was a project I > proposed > for magma, implemented by Paulette Lieby. The idea was to take any > finite abelian group G, create a wrapper A = GenericAbelianGroup(G), > passing in various parameters: > > magma> GenericAbelianGroup; > Intrinsic 'GenericAbelianGroup' > > Signatures: > (<Any> O) -> GrpAbGen > [ > IdIntrinsic: MonStgElt, > AddIntrinsic: MonStgElt, > InverseIntrinsic: MonStgElt, > UseRepresentation: BoolElt, > Order: RngIntElt, > UserGenerators: SetEnum, > ProperSubset: BoolElt, > RandomIntrinsic: MonStgElt, > ComputeStructure: BoolElt, > UseUserGenerators: BoolElt, > PollardRhoRParam: RngIntElt, > PollardRhoTParam: RngIntElt, > PollardRhoVParam: RngIntElt > ] > > Creates a generic abelian group whose universe is O. > Additional information can be passed using the parameters. > > Such a wrapper should allow the translation between multiplicative and > additive notation, > with the challenge to do so efficiently (any overhead could kill > efficiency). The idea I had > was precisely the waste I saw in dozens of independent implementations > of baby-step, > giant-step and Pollard rho algorithms (not called generic black box > groups for nothing!), > and their excessive support. Write once and re-use. > > Creation of subclasses in SAGE or specific constructors should make it > easier to manage > the large number of parameters which can be passed in to optimise a > given instance. > > An important note is that this infrastructure is used for group > calculations for Jacobians > of hyperelliptic curves over finite fields but it fails to take into > account the Weil pairing > which reduces the problem to cyclic group calculations! Discrete > logarithms in non-cyclic > groups are very expensive [relative to the group exponent]. They are > potentially also > dangerous since implementations assuming cyclicity can fail to > terminate on non-cyclic > input. > > Thus, as a warning, ignoring useful information like the Weil pairing > and MOV reductions, > smooth factors in the group order, and pathologies like non-cyclic > groups, should not be > omitted by focusing on large prime order groups. > > > --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 -~----------~----~----~----~------~----~------~--~---
