3
$\begingroup$

Let $n=\frac{B^N-1}{B-1}$. Assume $n$ is congruent to 3 modulo 4.

We have the following:

  1. If $N$ is 1 modulo 4, then $N$ is quadratic residue modulo $n$ and $-N$ is quadratic non-residue. The square root is efficiently computable via Gauss sums since $B$ is $N$-th root of unity modulo $n$.

  2. If $N$ is 3 modulo 4, then $-N$ is quadratic residue modulo $n$ and $N$ is quadratic non-residue. The square root is efficiently computable via Gauss sums since $B$ is $N$-th root of unity modulo $n$.

  3. If $N$ is 1 modulo 4 and $kronecker(-N,n)=1$ then $n$ is composite and the kronecker symbol is efficiently computable. If $n$ were prime we will have $kronecker(-N,n)=legendre(-N,n)= -1$.

  4. If $N$ is 3 modulo 4 and $kronecker(N,n)=1$ then $n$ is composite.

(3) and (4) can be used as compositeness checking of $n$. If $N$ is not prime, we have algebraic factorization of $(x^N-1)/(x-1)$.

By Fermat's little theorem, (3) and (4) never happen for prime $N$.

What properties of the factorization of $n$ can we find if (3) or (4) happens?

For $B=2$ the sequence of $N$ starts $15,33,39,51,55,65$

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .