Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.