Communication
Install
Faster access than browser!

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, ... Expand index (39 more) »

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

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.

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.

Bob Vaughan

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

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.

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.

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).

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.

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.

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.

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.

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.

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").

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.

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 &minus;1 off the diagonal, such that CTC is a multiple of the identity matrix I. Thus, if the matrix has order n, CTC.

Congruence of squares

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

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.

Continued fraction factorization

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

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.

Coset

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.

Cryptography

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

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.

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.

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.

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.

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.

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.

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.

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.

Euclidean algorithm

. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION.

Euler's criterion

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

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.

Gauss's lemma (number theory)

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

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.

Generalized Riemann hypothesis

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

George Pólya

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

Goldwasser–Micali cryptosystem

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

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.

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.

Homomorphism

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).

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.

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.

Integer

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

Integer factorization

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

Issai Schur

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

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.

Jacobi symbol

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

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.

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.

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.

No description.

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.

Mathematics

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

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.

MIT Press

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

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).

Modulo operation

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

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.

NP-completeness

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

Number theory

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

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.

Oxford University Press

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

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.

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.

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.

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.

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.

Prime power

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

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).

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.

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

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.

A quadratic residue code is a type of cyclic code.

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.

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

Rabin cryptosystem

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

Raymond Paley

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

Ring (mathematics)

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

Semigroup

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

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.

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.

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.

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.

Subgroup

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 ∗.

Symmetric matrix

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

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.

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.

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.

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.

References

Hey! We are on Facebook now! »