Kron(x, y) = Kronecker-Legendre symbol x over y.

Here are some notes from my program XICalc - Extra Precision Integer Calculator http://www.oocities.org/hjsmithh/download.html#XICalc :

The Kronecker symbol is an extension of the Jacobi symbol to all integers. It is variously written as (x/y) or (x|y) or (x vinculum y). Some values are:

where + is for +1 and − is for −1. For example Kron(3, 7) = −1, Kron(7, 3) = +1. This function is used internally by the Adleman function for prime number testing, and is part of the prime factorization by Elliptic Curve Method (ECM).## y =: -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 x = -9: 0 - + 0 - - 0 - - 0 + + 0 + + 0 - + 0 x = -8: - 0 + 0 + 0 - 0 - 0 + 0 + 0 - 0 - 0 + x = -7: - - 0 + + - + - - 0 + + - + - - 0 + + x = -6: 0 0 - 0 - 0 0 0 - 0 + 0 0 0 + 0 + 0 0 x = -5: - + - + 0 - - + - 0 + - + + 0 - + - + x = -4: - 0 + 0 - 0 + 0 - 0 + 0 - 0 + 0 - 0 + x = -3: 0 + - 0 + - 0 + - 0 + - 0 + - 0 + - 0 x = -2: - 0 + 0 + 0 - 0 - 0 + 0 + 0 - 0 - 0 + x = -1: - - + + - - + - - + + + - + + - - + + x = 0: 0 0 0 0 0 0 0 0 + 0 + 0 0 0 0 0 0 0 0 x = 1: + + + + + + + + + + + + + + + + + + + x = 2: + 0 + 0 - 0 - 0 + 0 + 0 - 0 - 0 + 0 + x = 3: 0 - - 0 - + 0 - + 0 + - 0 + - 0 - - 0 x = 4: + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + x = 5: + - - + 0 + - - + 0 + - - + 0 + - - + x = 6: 0 0 - 0 + 0 0 0 + 0 + 0 0 0 + 0 - 0 0 x = 7: + + 0 + - + + + + 0 + + + + - + 0 + + x = 8: + 0 + 0 - 0 - 0 + 0 + 0 - 0 - 0 + 0 + x = 9: 0 + + 0 + + 0 + + 0 + + 0 + + 0 + + 0

The algorithm for Kron(x, y) can be found in the C# source file PrimeFA.cs in my program XICalc. See download link above.

Return to Number Theory, Algorithms, and Real Functions

Return to Harry's Home Page

This page accessed times since Feb 17, 2006.

Page created by: hjsmithh@sbcglobal.net

Changes last made on Monday, 06-Aug-07 20:47:23 PDT