6

This is a partially computer theoretic question, but is probably closer to math.

I remember finding a paper from 1980's or so that had a proof of the fact that finding the order of a group element is no easier in then performing a factorization of the order of the group.

By no easier I mean that if there is a polynomial (in $\log(n)$ where $n$ is the order of the group) algorithm for finding the order of an element then there is a polynomial algorithm for the factorization of $n$. I am particularly interested in the special situation where the group is $\mathbb{Z}^*_p$ but I think the result might have been more general.

Does anyone by chance know the name of the paper? I have been trying to find it but can't. I believe it might have had some connection to elliptic cryptography but I'm not sure. Thank you for any leads.

ps.: If you know an easy proof of this that would also work.

Edit: Just to clarify it's easy to get element order in poly time if you are given the factorization of the group order as input. The claim I seem to remember is that there is no method which is in general more efficient than first factoring.

I haven't read the proof (since I didn't need it and didn't really have time at the time), but my best guess would be you could use randomly chosen group elements to get factors of the group size. The tricky bit would be 1) showing that you're gonna get lucky often enough (that's probably just a counting argument of some sort) and 2) getting rid of the randomness somehow.

DRF
  • 5,167
  • Finding the order of an element of a subgroup $G$ of $S_n$ is certainly a lot faster than finding the order of $G$, although both are polynomial in $n$. So perhaps you should say what you mean by "no easier". For the question to make any real sense, you also need to specify the input. – Derek Holt Mar 12 '15 at 15:26
  • @DerekHolt Good point. I was really thinking about $\mathbb{Z}^*_p$ but I'm not exactly sure how general the result was. – DRF Mar 12 '15 at 15:34
  • This seems a bit complicated even for ${\mathbb Z}_p^$. If we could solve the discrete log problem in polynomial time, then we could find element orders in ${\mathbb Z}_p^$ in polynomial time. But could we factorize $p-1$? I don't know much about this, but it seems that the answer to that is yes with high probability, and definitely yes if the Extended Riemann Hypothesis is true. – Derek Holt Mar 12 '15 at 15:49
  • If you take $Z_n^\times$ for $n$ a product of two primes instead of $n$ prime, then being able to find the order of group elements quickly implies that you can break the RSA for modulus $n$. – j.p. Mar 12 '15 at 16:33
  • I somehow doubt that your memory is correct: If $p = 2qr+1$ where $q$ and $r$ are primes both of about the same size, then one is unlikely to find elements of order $q$ without knowing $r$. Maybe you read the implication the other way round (which is true)? – j.p. Mar 12 '15 at 17:32
  • @j.p. Hmm I'm not sure I'm reading the comments right. I think that if you want to know the order of a group element you (in general) need to factor the group order first. I.e. that finding the order of a group element in general is at least as hard as factoring the group size. Which it seems to me we are in agreement. Certainly if you can factor you can get element order in poly time (with the factors as input). – DRF Mar 12 '15 at 17:53
  • @j.p. I don't see the point of your last comment. How does not being able to find elements of order $q$ affect the claim? The claim is of the type "if we can solve one hard problem then we can solve another hard problem", which is difficult to refute. – Derek Holt Mar 12 '15 at 17:54
  • @DerekHolt: What use does an order-finding algorithm have if you can get only elements of order $p-1$ or $\frac{p-1}{2}$? – j.p. Mar 12 '15 at 18:09
  • @DRF: We seem to agree. My comment with $p=2qr+1$ was about the fact, that you won't get lucky often enough. – j.p. Mar 12 '15 at 18:13
  • 1
    My first comment shows that my other comments are wrong: To factor $p=2qr+1$ just break the RSA with modulus $qr$. The order of elements in $\mathbb{Z}/qr\mathbb{Z}^\times$ give divisors of $\lambda(qr)$ that allow factoring $qr$. – j.p. Mar 13 '15 at 13:49

1 Answers1

3

I ended up finding the paper after all. It's Meijer, A. R. "Groups, Factoring, and Cryptography." Math. Mag. 69, 103-109, 1996.

Unfortunately the only online copy seems to be available through JStor to which I don't have access, but the free preview states:

"We shall prove that finding the order of an element in a group is, in general, at least as hard as factoring, in the sense that if one had a fast method of finding orders, one would also have a fast method of factoring."

DRF
  • 5,167
  • NB: One can register with JSTOR for "free on-line access" to six articles per month of this kind, something I find useful from time to time. The arrangement has changed since I first set up my account (which I linked to my Google login, similarly as I did here on StackExchange), but the mechanism is simple and reasonably unobtrusive. – hardmath Apr 29 '19 at 19:41