On Nov 19, 2007 7:27 AM, David Harvey <[EMAIL PROTECTED]> wrote: > > > On Nov 19, 2007, at 6:59 AM, David Joyner wrote: > > >> Further down the road, Drew Sutherland is thinking about writing a C+ > >> + library for computing things like orders, exponents, structures of > >> generic abelian groups. Basically you give it a "black box" that > >> knows how to add group elements, invert group elements, produce the > >> identity, and produce random elements, and it efficiently works out > >> the structure of the group, etc. No firm plans yet though.... I'm > > > > How do you produce a random element without knowing the > > generators of the group? And, for an abelian group, the > > generators give you the "invariants" quickly don't they? > > Oh boy.... you guys have exhausted my meagre knowledge on this > subject pretty quickly :-) > > I think the idea is supposed to be that part of the definition of the > black box is that it can produce random elements, regardless of > whether you know the generators. So for example, suppose our group is > the multiplicative group of Z/NZ, for some large N whose > factorisation we don't know. It's pretty easy to produce random > elements of this group (or at least, every time you write down a > random integer in [0, N), you have either found a random element, or > can easily find a non-trivial factor of N by taking the gcd with N). > But it's very hard to find generators (should be roughly equivalent > to factoring N?).
Okay. But this raises another (possibly dumber) question. Say N is the product of 2 very large primes. In the case of G = ZZ/NZZ, addition, inversion and random elements can be produced in polynomial time I asume. Knowing the group structure of G, ie the invariants, is tantamount to knowing the factorization of N, isn't it? If "yes", then what does "efficiently works" mean? I'm just curious, not trying to be discouraging. In fact, the opposite - it sounds potentially very interesting... > > And yes, once you have the generators, I guess you have everything > else very easily. > > > david > > > > > --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
