MathOverflow is a question and answer site for professional mathematicians. 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

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.

share|cite|improve this question

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.