Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It appears that if you have a finite field, F_p, and you can factor the order of the field, p-1, then you can easily construct an arbitrary nth root of unity in F_p and also check that it be primitive or no (if you can factor n).

So extending this to direct product F_p X F_q isomorphic to the ring Z/nZ, what prevents this from happening and determining the order of an arbitrary element of Z/nZ (n=pq). It is because we do not know (p-1)*(q-1), is that correct? Since we do not know the order of Z/nZ, we can not so easily construct an arbitrary element with specific order. In any case if we knew the order of Z/nZ we could factor n straight away.

Obviously knowing the order of an arbitrary element of Z/nZ enables us to quickly factor n, since the order of Z/nZ is simply a multiple of this element's order. So if we can compute 1 element's order easily, we can surely do a few, and, equally easily we will be able to find the order of Z/nZ by combining these orders.

My question is : what factoring approaches directly try to compute the order of elements in Z/nZ?

It seems that all factoring approaches (with the exception of quadratic congruences) are essentially versions of this (elliptic curve finds orders of elements in an elliptic curve, Shor's algorithm appears to be based on finding the order using a quantum oracle, also, clearly this also connects factoring and discrete log).

Is there anything that is directly based on this that manages to quickly determine the order of elements in Z/nZ without knowing the order of Z/nZ? Or what was the farthest this approach got?

share|cite|improve this question
I don't see how factoring $p-1$ gives you arbitrary roots of unity, unless you can find a generator. – Thomas Andrews Dec 12 '12 at 14:38
@ThomasAndrews There are $\phi(p-1)$ generators, so it may be hard to find one, but not hard to stumble upon one :) Also, to find $r$th roots ($r\ll p$), you don't even need a full generator. – Hagen von Eitzen Dec 12 '12 at 15:00
Stumbling upon a generator won't give you primitive roots of an arbitrary order $n$. You still need $n$ to divide $p-1=$ the order of the multiplicative group. Roots of unity of arbitrary order only exist in extension fields of $\mathbb{F}_p$. - Oh, a more careful reading reveals that you are only interested in roots of unity inside the prime field. Then finding a primitive element is, indeed, enough. – Jyrki Lahtonen Dec 12 '12 at 15:26
I'm not sure, if this is what you are looking for, but isn't that one branch in Rabin-Miller essentially based on stumbling upon an unexpected element of order two? Finding such an element (other than $-1$) immediately gives you a factorization. – Jyrki Lahtonen Dec 12 '12 at 15:33
Sure, lots might be generators, but proving that it a particular element is a generator is non-trivial. You basically have to compute $g^{(p-1)/q}$ for each prime divisor $q$ of $p-1$. Unless you can tell me something more efficient. @HagenvonEitzen – Thomas Andrews Dec 12 '12 at 15:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.