Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Legendre symbol
Summary
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.
The Legendre symbol was introduced by Adrien-Marie Legendre in 1798 in the course of his attempts at proving the law of quadratic reciprocity. Generalizations of the symbol include the Jacobi symbol and Dirichlet characters of higher order. The notational convenience of the Legendre symbol inspired introduction of several other "symbols" used in algebraic number theory, such as the Hilbert symbol and the Artin symbol.
Let be an odd prime number. An integer is a quadratic residue modulo if it is congruent to a perfect square modulo and is a quadratic nonresidue modulo otherwise. The Legendre symbol is a function of and defined as
Legendre's original definition was by means of the explicit formula
By Euler's criterion, which had been discovered earlier and was known to Legendre, these two definitions are equivalent. Thus Legendre's contribution lay in introducing a convenient notation that recorded quadratic residuosity of a mod p. For the sake of comparison, Gauss used the notation aRp, aNp according to whether a is a residue or a non-residue modulo p. For typographical convenience, the Legendre symbol is sometimes written as (a | p) or (a/p). For fixed p, the sequence is periodic with period p and is sometimes called the Legendre sequence. Each row in the following table exhibits periodicity, just as described.
The following is a table of values of Legendre symbol with p ≤ 127, a ≤ 30, p odd prime.
There are a number of useful properties of the Legendre symbol which, together with the law of quadratic reciprocity, can be used to compute it efficiently.
Given a generator , if , then is a quadratic residue if and only if is even. This shows that half of the nonzero elements in are quadratic residues.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (2)
MATH-201: Analysis III
Calcul différentiel et intégral.
Eléments d'analyse complexe.
COM-401: Cryptography and security
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how