Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

Quadratic residue

Index Quadratic residue

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: Otherwise, q is called a quadratic nonresidue modulo n. Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers. [1]

89 relations: Adrien-Marie Legendre, American Mathematical Society, Big O notation, Bob Vaughan, Carl Friedrich Gauss, Carl Gustav Jacob Jacobi, Character sum, Chinese remainder theorem, Cipolla's algorithm, Class number formula, Coin flipping, Complex number, Computational hardness assumption, Conference graph, Conference matrix, Congruence of squares, Congruence relation, Continued fraction factorization, Coprime integers, Coset, Cryptography, Cubic reciprocity, Dirichlet character, Dirichlet L-function, Dirichlet's theorem on arithmetic progressions, Discrete logarithm, Disquisitiones Arithmeticae, Dixon's factorization method, Domain of a function, Euclidean algorithm, Euler's criterion, Field (mathematics), Gauss's lemma (number theory), General number field sieve, Generalized Riemann hypothesis, George Pólya, Goldwasser–Micali cryptosystem, Group (mathematics), Hensel's lemma, Homomorphism, Hugh Lowell Montgomery, Ideal class group, Integer, Integer factorization, Issai Schur, Ivan Vinogradov, Jacobi symbol, Joseph-Louis Lagrange, Klein four-group, Kronecker symbol, ..., Legendre symbol, Leonhard Euler, Mathematics, Miller–Rabin primality test, MIT Press, Modular arithmetic, Modulo operation, Multiplicative group of integers modulo n, NP-completeness, Number theory, Oblivious transfer, Oxford University Press, Paley graph, Parameterized complexity, Peter Gustav Lejeune Dirichlet, Pierre de Fermat, Prime number, Prime power, Primitive root modulo n, Probable prime, Quadratic form, Quadratic reciprocity, Quadratic residue code, Quadratic residuosity problem, Quadratic sieve, Rabin cryptosystem, Raymond Paley, Ring (mathematics), Semigroup, Skew-symmetric matrix, Solovay–Strassen primality test, Springer Science+Business Media, Square number, Subgroup, Symmetric matrix, Tonelli–Shanks algorithm, Unit (ring theory), Zero divisor, Zolotarev's lemma. Expand index (39 more) »

Adrien-Marie Legendre

Adrien-Marie Legendre (18 September 1752 – 10 January 1833) was a French mathematician.

New!!: Quadratic residue and Adrien-Marie Legendre · See more »

American Mathematical Society

The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, advocacy and other programs.

New!!: Quadratic residue and American Mathematical Society · See more »

Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

New!!: Quadratic residue and Big O notation · See more »

Bob Vaughan

Robert Charles "Bob" Vaughan FRS (born 24 March 1945) is a British mathematician, working in the field of analytic number theory.

New!!: Quadratic residue and Bob Vaughan · See more »

Carl Friedrich Gauss

Johann Carl Friedrich Gauss (Gauß; Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields, including algebra, analysis, astronomy, differential geometry, electrostatics, geodesy, geophysics, magnetic fields, matrix theory, mechanics, number theory, optics and statistics.

New!!: Quadratic residue and Carl Friedrich Gauss · See more »

Carl Gustav Jacob Jacobi

Carl Gustav Jacob Jacobi (10 December 1804 – 18 February 1851) was a German mathematician, who made fundamental contributions to elliptic functions, dynamics, differential equations, and number theory.

New!!: Quadratic residue and Carl Gustav Jacob Jacobi · See more »

Character sum

In mathematics, a character sum is a sum of values of a Dirichlet character χ modulo N, taken over a given range of values of n. Such sums are basic in a number of questions, for example in the distribution of quadratic residues, and in particular in the classical question of finding an upper bound for the least quadratic non-residue modulo N. Character sums are often closely linked to exponential sums by the Gauss sums (this is like a finite Mellin transform).

New!!: Quadratic residue and Character sum · See more »

Chinese remainder theorem

The Chinese remainder theorem is a theorem of number theory, which states that if one knows the remainders of the Euclidean division of an integer by several integers, then one can determine uniquely the remainder of the division of by the product of these integers, under the condition that the divisors are pairwise coprime.

New!!: Quadratic residue and Chinese remainder theorem · See more »

Cipolla's algorithm

In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form where x,n \in \mathbf_, so n is the square of x, and where p is an odd prime.

New!!: Quadratic residue and Cipolla's algorithm · See more »

Class number formula

In number theory, the class number formula relates many important invariants of a number field to a special value of its Dedekind zeta function.

New!!: Quadratic residue and Class number formula · See more »

Coin flipping

Coin flipping, coin tossing, or heads or tails is the practice of throwing a coin in the air and checking which side is showing when it lands to choose between two alternatives, sometimes to resolve a dispute between two parties.

New!!: Quadratic residue and Coin flipping · See more »

Complex number

A complex number is a number that can be expressed in the form, where and are real numbers, and is a solution of the equation.

New!!: Quadratic residue and Complex number · See more »

Computational hardness assumption

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where efficiently typically means "in polynomial time").

New!!: Quadratic residue and Computational hardness assumption · See more »

Conference graph

In the mathematical area of graph theory, a conference graph is a strongly regular graph with parameters v, and It is the graph associated with a symmetric conference matrix, and consequently its order v must be 1 (modulo 4) and a sum of two squares.

New!!: Quadratic residue and Conference graph · See more »

Conference matrix

In mathematics, a conference matrix (also called a C-matrix) is a square matrix C with 0 on the diagonal and +1 and −1 off the diagonal, such that CTC is a multiple of the identity matrix I. Thus, if the matrix has order n, CTC.

New!!: Quadratic residue and Conference matrix · See more »

Congruence of squares

In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.

New!!: Quadratic residue and Congruence of squares · See more »

Congruence relation

In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure.

New!!: Quadratic residue and Congruence relation · See more »

Continued fraction factorization

In number theory, the continued fraction factorization method (CFRAC) is an integer factorization algorithm.

New!!: Quadratic residue and Continued fraction factorization · See more »

Coprime integers

In number theory, two integers and are said to be relatively prime, mutually prime, or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1.

New!!: Quadratic residue and Coprime integers · See more »


In mathematics, if G is a group, and H is a subgroup of G, and g is an element of G, then Only when H is normal will the set of right cosets and the set of left cosets of H coincide, which is one definition of normality of a subgroup.

New!!: Quadratic residue and Coset · See more »


Cryptography or cryptology (from κρυπτός|translit.

New!!: Quadratic residue and Cryptography · See more »

Cubic reciprocity

Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x3 ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence x3 ≡ p (mod q) is solvable if and only if x3 ≡ q (mod p) is solvable.

New!!: Quadratic residue and Cubic reciprocity · See more »

Dirichlet character

In number theory, Dirichlet characters are certain arithmetic functions which arise from completely multiplicative characters on the units of \mathbb Z / k \mathbb Z. Dirichlet characters are used to define Dirichlet ''L''-functions, which are meromorphic functions with a variety of interesting analytic properties.

New!!: Quadratic residue and Dirichlet character · See more »

Dirichlet L-function

In mathematics, a Dirichlet L-series is a function of the form Here χ is a Dirichlet character and s a complex variable with real part greater than 1.

New!!: Quadratic residue and Dirichlet L-function · See more »

Dirichlet's theorem on arithmetic progressions

In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n is a non-negative integer.

New!!: Quadratic residue and Dirichlet's theorem on arithmetic progressions · See more »

Discrete logarithm

In the mathematics of the real numbers, the logarithm logb a is a number x such that, for given numbers a and b. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that.

New!!: Quadratic residue and Discrete logarithm · See more »

Disquisitiones Arithmeticae

The Disquisitiones Arithmeticae (Latin for "Arithmetical Investigations") is a textbook of number theory written in Latin by Carl Friedrich Gauss in 1798 when Gauss was 21 and first published in 1801 when he was 24.

New!!: Quadratic residue and Disquisitiones Arithmeticae · See more »

Dixon's factorization method

In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method.

New!!: Quadratic residue and Dixon's factorization method · See more »

Domain of a function

In mathematics, and more specifically in naive set theory, the domain of definition (or simply the domain) of a function is the set of "input" or argument values for which the function is defined.

New!!: Quadratic residue and Domain of a function · See more »

Euclidean algorithm


New!!: Quadratic residue and Euclidean algorithm · See more »

Euler's criterion

In number theory Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime.

New!!: Quadratic residue and Euler's criterion · See more »

Field (mathematics)

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined, and behave as when they are applied to rational and real numbers.

New!!: Quadratic residue and Field (mathematics) · See more »

Gauss's lemma (number theory)

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue.

New!!: Quadratic residue and Gauss's lemma (number theory) · See more »

General number field sieve

In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than.

New!!: Quadratic residue and General number field sieve · See more »

Generalized Riemann hypothesis

The Riemann hypothesis is one of the most important conjectures in mathematics.

New!!: Quadratic residue and Generalized Riemann hypothesis · See more »

George Pólya

George Pólya (Pólya György; December 13, 1887 – September 7, 1985) was a Hungarian mathematician.

New!!: Quadratic residue and George Pólya · See more »

Goldwasser–Micali cryptosystem

The Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982.

New!!: Quadratic residue and Goldwasser–Micali cryptosystem · See more »

Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set of elements equipped with an operation that combines any two elements to form a third element and that satisfies four conditions called the group axioms, namely closure, associativity, identity and invertibility.

New!!: Quadratic residue and Group (mathematics) · See more »

Hensel's lemma

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a polynomial equation has a simple root modulo a prime number, then this root corresponds to a unique root of the same equation modulo any higher power of, which can be found by iteratively "lifting" the solution modulo successive powers of.

New!!: Quadratic residue and Hensel's lemma · See more »


In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces).

New!!: Quadratic residue and Homomorphism · See more »

Hugh Lowell Montgomery

Hugh Lowell Montgomery (born August 26, 1944) is an American mathematician, working in the fields of analytic number theory and mathematical analysis.

New!!: Quadratic residue and Hugh Lowell Montgomery · See more »

Ideal class group

In number theory, the ideal class group (or class group) of an algebraic number field is the quotient group where is the group of fractional ideals of the ring of integers of, and is its subgroup of principal ideals.

New!!: Quadratic residue and Ideal class group · See more »


An integer (from the Latin ''integer'' meaning "whole")Integer 's first literal meaning in Latin is "untouched", from in ("not") plus tangere ("to touch").

New!!: Quadratic residue and Integer · See more »

Integer factorization

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.

New!!: Quadratic residue and Integer factorization · See more »

Issai Schur

Issai Schur (January 10, 1875 – January 10, 1941) was a Russian mathematician who worked in Germany for most of his life.

New!!: Quadratic residue and Issai Schur · See more »

Ivan Vinogradov

Ivan Matveevich Vinogradov (a; 14 September 1891 – 20 March 1983) (not to be confused with Askold Ivanovich Vinogradov of the Bombieri-Vinogradov theorem) was a Soviet mathematician, who was one of the creators of modern analytic number theory, and also a dominant figure in mathematics in the USSR.

New!!: Quadratic residue and Ivan Vinogradov · See more »

Jacobi symbol

Jacobi symbol for various k (along top) and n (along left side).

New!!: Quadratic residue and Jacobi symbol · See more »

Joseph-Louis Lagrange

Joseph-Louis Lagrange (or;; born Giuseppe Lodovico Lagrangia, Encyclopædia Britannica or Giuseppe Ludovico De la Grange Tournier, Turin, 25 January 1736 – Paris, 10 April 1813; also reported as Giuseppe Luigi Lagrange or Lagrangia) was an Italian Enlightenment Era mathematician and astronomer.

New!!: Quadratic residue and Joseph-Louis Lagrange · See more »

Klein four-group

In mathematics, the Klein four-group (or just Klein group or Vierergruppe, four-group, often symbolized by the letter V or as K4) is the group, the direct product of two copies of the cyclic group of order 2.

New!!: Quadratic residue and Klein four-group · See more »

Kronecker symbol

In number theory, the Kronecker symbol, written as \left(\frac an\right) or (a|n), is a generalization of the Jacobi symbol to all integers n. It was introduced by.

New!!: Quadratic residue and Kronecker symbol · See more »

Legendre symbol

No description.

New!!: Quadratic residue and Legendre symbol · See more »

Leonhard Euler

Leonhard Euler (Swiss Standard German:; German Standard German:; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, logician and engineer, who made important and influential discoveries in many branches of mathematics, such as infinitesimal calculus and graph theory, while also making pioneering contributions to several branches such as topology and analytic number theory.

New!!: Quadratic residue and Leonhard Euler · See more »


Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

New!!: Quadratic residue and Mathematics · See more »

Miller–Rabin primality test

The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test.

New!!: Quadratic residue and Miller–Rabin primality test · See more »

MIT Press

The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts (United States).

New!!: Quadratic residue and MIT Press · See more »

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value—the modulus (plural moduli).

New!!: Quadratic residue and Modular arithmetic · See more »

Modulo operation

In computing, the modulo operation finds the remainder after division of one number by another (sometimes called modulus).

New!!: Quadratic residue and Modulo operation · See more »

Multiplicative group of integers modulo n

In modular arithmetic, the integers coprime (relatively prime) to n from the set \ of n non-negative integers form a group under multiplication modulo n, called the multiplicative group of integers modulo n. Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n. Hence another name is the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo n. Here units refers to elements with a multiplicative inverse, which in this ring are exactly those coprime to n. This group, usually denoted (\mathbb/n\mathbb)^\times, is fundamental in number theory.

New!!: Quadratic residue and Multiplicative group of integers modulo n · See more »


In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

New!!: Quadratic residue and NP-completeness · See more »

Number theory

Number theory, or in older usage arithmetic, is a branch of pure mathematics devoted primarily to the study of the integers.

New!!: Quadratic residue and Number theory · See more »

Oblivious transfer

In cryptography, an oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred.

New!!: Quadratic residue and Oblivious transfer · See more »

Oxford University Press

Oxford University Press (OUP) is the largest university press in the world, and the second oldest after Cambridge University Press.

New!!: Quadratic residue and Oxford University Press · See more »

Paley graph

In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue.

New!!: Quadratic residue and Paley graph · See more »

Parameterized complexity

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output.

New!!: Quadratic residue and Parameterized complexity · See more »

Peter Gustav Lejeune Dirichlet

Johann Peter Gustav Lejeune Dirichlet (13 February 1805 – 5 May 1859) was a German mathematician who made deep contributions to number theory (including creating the field of analytic number theory), and to the theory of Fourier series and other topics in mathematical analysis; he is credited with being one of the first mathematicians to give the modern formal definition of a function.

New!!: Quadratic residue and Peter Gustav Lejeune Dirichlet · See more »

Pierre de Fermat

Pierre de Fermat (Between 31 October and 6 December 1607 – 12 January 1665) was a French lawyer at the Parlement of Toulouse, France, and a mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality.

New!!: Quadratic residue and Pierre de Fermat · See more »

Prime number

A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.

New!!: Quadratic residue and Prime number · See more »

Prime power

In mathematics, a prime power is a positive integer power of a single prime number.

New!!: Quadratic residue and Prime power · See more »

Primitive root modulo n

In modular arithmetic, a branch of number theory, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, for every integer a coprime to n, there is an integer k such that gk ≡ a (mod n).

New!!: Quadratic residue and Primitive root modulo n · See more »

Probable prime

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers.

New!!: Quadratic residue and Probable prime · See more »

Quadratic form

In mathematics, a quadratic form is a homogeneous polynomial of degree two in a number of variables.

New!!: Quadratic residue and Quadratic form · See more »

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.

New!!: Quadratic residue and Quadratic reciprocity · See more »

Quadratic residue code

A quadratic residue code is a type of cyclic code.

New!!: Quadratic residue and Quadratic residue code · See more »

Quadratic residuosity problem

The quadratic residuosity problem in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not.

New!!: Quadratic residue and Quadratic residuosity problem · See more »

Quadratic sieve

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve).

New!!: Quadratic residue and Quadratic sieve · See more »

Rabin cryptosystem

The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization.

New!!: Quadratic residue and Rabin cryptosystem · See more »

Raymond Paley

Raymond Edward Alan Christopher Paley (7 January 1907 – 7 April 1933) was an English mathematician.

New!!: Quadratic residue and Raymond Paley · See more »

Ring (mathematics)

In mathematics, a ring is one of the fundamental algebraic structures used in abstract algebra.

New!!: Quadratic residue and Ring (mathematics) · See more »


In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

New!!: Quadratic residue and Semigroup · See more »

Skew-symmetric matrix

In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative; that is, it satisfies the condition In terms of the entries of the matrix, if aij denotes the entry in the and; i.e.,, then the skew-symmetric condition is For example, the following matrix is skew-symmetric: 0 & 2 & -1 \\ -2 & 0 & -4 \\ 1 & 4 & 0\end.

New!!: Quadratic residue and Skew-symmetric matrix · See more »

Solovay–Strassen primality test

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime.

New!!: Quadratic residue and Solovay–Strassen primality test · See more »

Springer Science+Business Media

Springer Science+Business Media or Springer, part of Springer Nature since 2015, is a global publishing company that publishes books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.

New!!: Quadratic residue and Springer Science+Business Media · See more »

Square number

In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself.

New!!: Quadratic residue and Square number · See more »


In group theory, a branch of mathematics, given a group G under a binary operation ∗, a subset H of G is called a subgroup of G if H also forms a group under the operation ∗.

New!!: Quadratic residue and Subgroup · See more »

Symmetric matrix

In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose.

New!!: Quadratic residue and Symmetric matrix · See more »

Tonelli–Shanks algorithm

The Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used within modular arithmetic to solve for a congruence r of the form r2 ≡ n (mod p), where p is a prime.

New!!: Quadratic residue and Tonelli–Shanks algorithm · See more »

Unit (ring theory)

In mathematics, an invertible element or a unit in a (unital) ring is any element that has an inverse element in the multiplicative monoid of, i.e. an element such that The set of units of any ring is closed under multiplication (the product of two units is again a unit), and forms a group for this operation.

New!!: Quadratic residue and Unit (ring theory) · See more »

Zero divisor

In abstract algebra, an element of a ring is called a left zero divisor if there exists a nonzero such that, or equivalently if the map from to that sends to is not injective.

New!!: Quadratic residue and Zero divisor · See more »

Zolotarev's lemma

In number theory, Zolotarev's lemma states that the Legendre symbol for an integer a modulo an odd prime number p, where p does not divide a, can be computed as the sign of a permutation: where ε denotes the signature of a permutation and πa is the permutation of the nonzero residue classes mod p induced by multiplication by a. For example, take a.

New!!: Quadratic residue and Zolotarev's lemma · See more »

Redirects here:

Least quadratic non-residue, Modular square root, Quadratic congruence, Quadratic congruences, Quadratic excess, Quadratic non-residue, Quadratic nonresidue, Quadratic residues, Quadratic residuosity, Square root mod n, Square root modulo n.


[1] https://en.wikipedia.org/wiki/Quadratic_residue

Hey! We are on Facebook now! »