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.
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."