Georgi Guninski on Thu, 24 Dec 2020 17:03:01 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Merry Christmas and kronecker() challenge


Merry Christmas and all the best in 2021!

This is offtopic, but let me try:

https://mathoverflow.net/questions/379135/the-kronecker-symbol-and-factorization-of-n-fracbn-1b-1

The kronecker symbol and factorization of n=(B^N−1)/(B−1)

Let n=(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.

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

(3) and (4) can be used as compositeness checking of n.
By Fermat's little theorem, (3) never happens for prime N.

This is closely related to the algebraic factorization of (x^N-1)/(x-1).

>What properties of the factorization of n or N can we find via (3)?
>Does the algebraic factorization explains it? If N is large, we can't
compute the algebraic factorization and via reciprocity we have
information about factorization of N.