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

https://en.wikipedia.org/wiki/Legendre_symbol

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 publications (2)

Attacks on some post-quantum cryptographic protocols: The case of the Legendre PRF and SIKE

Novak Kaluderovic

Post-quantum cryptography is a branch of cryptography which deals with cryptographic algorithms whose hardness assumptions are not based on problems known to be solvable by a quantum computer, such as

EPFL2022

We take an approach toward Counting the number of integers n for which the curve (n),: y(2) = x(3) - n(2)x has 2-Selmer groups of a given size. This question was also discussed in a pair of papers by

2009

Related concepts (25)

Quadratic reciprocity

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is: Let p and q be distinct odd prime numbers, and define the Legendre symbol as: Then: This law, together with its supplements, allows the easy calculation of any Legendre symbol, making it possible to determine whether there is an integer solution for any quadratic equation of the form for an odd prime ; that is, to determine the "perfect squares" modulo .

Legendre symbol

Jacobi symbol

Jacobi symbol k/n for various k (along top) and n (along left side). Only 0 ≤ k < n are shown, since due to rule (2) below any other k can be reduced modulo n. Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of −1 is a quadratic residue, and if k is a quadratic residue modulo a coprime n, then k/n = 1, but not all entries with a Jacobi symbol of 1 (see the n = 9 and n = 15 rows) are quadratic residues. Notice also that when either n or k is a square, all values are nonnegative.

Related courses (3)

MATH-201: Analysis III

Calcul différentiel et intégral: Eléments d'analyse vectorielle, intégration par partie, intégrale curviligne, intégrale de surface, théorèmes de Stokes, Green, Gauss, fonctions harmoniques; Eléments

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

ENV-521: Multivariate statistics with R in environment

Introduction to multivariate data analysis and modelling. The course helps for a critical choice of methods and their integration in a research planning. It prepares for complexe data analysis in vari

Related lectures (34)

Residues Theorem Applications

Explores applications of the residues theorem in various scenarios, with a focus on Laurent series development.

Extreme Problems in Diophantine Approximation and Dynamics

Explores the Logarithmic Law, geodesic flows, hyperbolic surfaces, and rare events in probability.

RSA Cryptography: Primality Testing and Quadratic Residues

Explores RSA cryptography, covering primality testing, quadratic residues, and cryptographic applications.