I had been thinking of the following -- mayby some of this is already in place.
We define a base class called (say) abstract_finite_abelian_group. This will have virtual functions (to be replaced by real functions by derived classes) as follows: add(x,y): return x*y (or x+y, etc) sub(x,y): return x*y^-1 (or x-y, etc) inv(x): return x^-1 (or -x, etc) identity(): return 1 (or 0, etc) zmul(n,x): return x^n (or n*x, etc) -- this one for the Z-module structure [The last one could also be implemented generically, of course, but there might need to be different implementations in groups where inversion is free compared with those where it is not]. group_order(): returns the group order if known, else None; derived classes should cache the order in .__order group_order_bounds(): return (lb,ub) where lb<=__order<=ub: this is crucial for computing orders of elements in a group whose order is not (yet) known. Of course, if the group order is known then lb=ub=__order. The deal now is: any derived class which instantaites these (sorry for the C++ jargon) gets to use these functions provided by the class abstract_finite_abelian_group: bsgs(x,y,lb,ub): returns an integer n such that zmul(n,x)==y with lb<=n<=ub or raise a ValueError if there is none, Using BabyStepGiantStep dlog(x,y): returns an integer n such that zmul(n,x)==y and 0<=n<order(x) order(x): returns the order of x ...and some other useful things I have in mind. I can easily write such a class, since I have in fact written all these functions anyway for elliptic curve groups and would just have to abstract that. Then we just have to add abstract_finite_abelian_group to the list of base classes for finite fields and elliptic curves over finite fields (and anything else), make sure that they do implement the necessary functions, and bingo. On rereading Robert B's posting, I see that I am not using the python-esque functionality, but I think that is because I have been thinking of the basic group operations as methods of the group class rather than of the element class. I'm not sure if either is better. John On 14/02/2008, Robert Bradshaw <[EMAIL PROTECTED]> wrote: > > At the expense of having to write the algorithm twice (once for > additive groups, once for multiplicative groups, though one could > wrap one in the other via a wrapper, or maybe being even more clever > by swapping the tp_add and tp_mul function pointer slots in the type) > I can't help but mention that Python/Cython already has a much more > natural way of handling abstract groups than manually passing > function pointers around. Specifically, a*b (or a+b) gives the group > law, and ~a (or -a) the inverse, and the "one" which need only be > computed once (then cached) should be available via G(1). Of course, > this is really passing function pointers around in the background, > but would be easier to follow. > > I'll concede that if the group operations are *extremely* cheap the > the overhead of two (rather than one) C function call might impact > performance. I think a additive group -> multiplicative group wrapper > could be written as to be very thin too. > > > - Robert > > > > On Feb 13, 2008, at 2:22 PM, David Harvey wrote: > > > On Feb 13, 2008, at 5:09 PM, Nick Alexander wrote: > > > >> John also needs identity and inverses, which requires passing in > >> three or functions. Or, more likely a struct, which in an OO > >> language, I call an object. > >> > >> To me, that means you're writing a special purpose "abstract group" > >> wrapper for discrete logs, which is fine. But I believe the heavier > > > > This would be great to have in sage. I wanted to work on something > > like this in collaboration with Andrew Sutherland a few months back, > > but that whole annoying thesis thing got in the way. Our idea was to > > have the underlying abstract group algorithms (like computing > > discrete logs, exponents of groups, orders of groups, group > > structures etc) written in C++ with templates. Andrew has had a lot > > of experience with this. One instantiation would be a black box using > > C function pointers, which we could then plug into a cython class to > > perform the arithmetic. > > > > 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 -~----------~----~----~----~------~----~------~--~---
