0
$\begingroup$

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?

  • 0
    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. @HagenvonEitzen2012-12-12

0 Answers 0