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.