In "On computing factors of cyclotomic polynomials", Richard P. Brent gives the identity

$$ 4 \Phi_n(x) = A_n(x)^2 - (-1)^{(n-1)/2} n B_n(x)^2 \qquad (1) $$

where $n$ is odd squarefree and $A_n,B_n$ can be computed in $O(\phi(n)/2)$

Let $N$ be composite and $x_0 \pmod N$ is of low multiplicative order $n$. The lhs of (1) vanishes $\pmod N$ and we have $A_n(x_0)^2 \equiv (-1)^{(n-1)/2} n B_n(x_0)^2 \pmod N$

If $B_n(x_0)$ is invertible $\pmod N$ one can compute the square root of $ (-1)^{(n-1)/2} n \pmod N$ in $O(\phi(n)/2)$. If it is not invertible one finds not trivial factor of $N$.

For general $N$ finding elements of low multiplicative order is hard, but for special cases like $(a^n - b^n)/(a-b)$, Fibonacci numbers $F_n = (\phi^n - \psi^n)/(\phi-\psi)$ extended with $\sqrt{5}$ it is easy.

Numerically experimenting with the special cases and taking into account the algebraic factorization, always computed the square root of $ (-1)^{(n-1)/2} n \pmod N$ for composite $N$.

For general $N$, $ (-1)^{(n-1)/2} n$ need not be square, so a nontrivial factor can be found.

(A) Is there a reason that efficiently finding an element of low multiplicative order $n$ implies $ (-1)^{(n-1)/2} n$ is a square?

(B) Are there $N$ of special form which are counterexamples to (A)?.

Using this method for square roots managed to find factors of $(p^p-1)/(p-1)$, but this was already known.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.