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) » « Shrink index
Adrien-Marie Legendre (18 September 1752 – 10 January 1833) was a French mathematician.
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 is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.
Robert Charles "Bob" Vaughan FRS (born 24 March 1945) is a British mathematician, working in the field of analytic number theory.
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 (10 December 1804 – 18 February 1851) was a German mathematician, who made fundamental contributions to elliptic functions, dynamics, differential equations, and number theory.
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).
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.
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.
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 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.
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.
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").
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.
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.
In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.
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.
In number theory, the continued fraction factorization method (CFRAC) is an integer factorization algorithm.
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.
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 or cryptology (from κρυπτός|translit.
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.
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.
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.
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.
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.
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.
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.
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.
. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION.
In number theory Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime.
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 in number theory gives a condition for an integer to be a quadratic residue.
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than.
The Riemann hypothesis is one of the most important conjectures in mathematics.
George Pólya (Pólya György; December 13, 1887 – September 7, 1985) was a Hungarian mathematician.
The Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982.
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.
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.
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 (born August 26, 1944) is an American mathematician, working in the fields of analytic number theory and mathematical analysis.
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.
An integer (from the Latin ''integer'' meaning "whole")Integer 's first literal meaning in Latin is "untouched", from in ("not") plus tangere ("to touch").
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.
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 for various k (along top) and n (along left side).
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.
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.
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.
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 (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
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.
The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts (United States).
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value—the modulus (plural moduli).
In computing, the modulo operation finds the remainder after division of one number by another (sometimes called modulus).
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.
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
Number theory, or in older usage arithmetic, is a branch of pure mathematics devoted primarily to the study of the integers.
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 (OUP) is the largest university press in the world, and the second oldest after Cambridge University Press.
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.
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.
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 (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.
A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
In mathematics, a prime power is a positive integer power of a single prime number.
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).
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).
The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization.
Raymond Edward Alan Christopher Paley (7 January 1907 – 7 April 1933) was an English mathematician.
In mathematics, a ring is one of the fundamental algebraic structures used in abstract algebra.
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.
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.
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.
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.
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 ∗.
In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose.
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.
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.
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.
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.
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.