On Nov 19, 2007, at 10:10 AM, David Joyner wrote:
>> 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. Yes. (In fact, almost linear time.) > Knowing the group structure of G, ie > the invariants, is tantamount to knowing the factorization of N, > isn't it? Yes. > If "yes", then what does "efficiently works" mean? "Efficiently works" means that it has a very efficient implementation of baby-step/giant-step and various algorithms built on top of that. Of course this is a terrible algorithm for factoring integers, it's not even sub-exponential, in the case of two large prime factors. With the group Z/NZ, all the best algorithms take advantage of extra structure. But if you have a "generic" group where you don't know much else about the structure --- all you know is how to add and invert --- then baby-step/giant-step is pretty much the best you can do. Drew's thesis makes good reading on this topic: http://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf 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/ -~----------~----~----~----~------~----~------~--~---
