85 relations: AC0, Adleman–Pomerance–Rumely primality test, Agrawal's conjecture, AKS primality test, Algorithm, Analytic number theory, Baillie–PSW primality test, Big O notation, Carl Pomerance, Carmichael number, Charles E. Leiserson, Clifford Stein, Co-NP, Composite number, Computational complexity theory, Coprime integers, Counterexample, Cryptography, Deterministic algorithm, Divisibility rule, Elliptic curve primality, Euler pseudoprime, Factorization, Fermat primality test, Fermat's little theorem, Fibonacci number, Fibonacci polynomials, Frobenius pseudoprime, Gary Miller (computer scientist), Generalized Riemann hypothesis, George B. Purdy, Greatest common divisor, Integer factorization, Introduction to Algorithms, Jacobi symbol, John Selfridge, Journal of Computer and System Sciences, L (complexity), Leonard Adleman, Lucas primality test, Lucas pseudoprime, Lucas sequence, Manindra Agrawal, Mathematics, Miller–Rabin primality test, Modular arithmetic, Multiplicative order, NC (complexity), Neeraj Kayal, Nitin Saxena, ..., NP (complexity), P (complexity), P-complete, Pocklington primality test, Primality certificate, Prime number, Primitive root modulo n, Primorial, Probable prime, Proth's theorem, Pseudocode, Pseudoprime, Quantum computing, Randomized algorithm, Recursion, Remainder, Richard Crandall, Ron Rivest, RP (complexity), RSA (cryptosystem), Sample space, Samuel S. Wagstaff Jr., Shor's algorithm, Sieve of Eratosthenes, Solovay–Strassen primality test, Sophie Germain prime, Springer Science+Business Media, Strong pseudoprime, The Art of Computer Programming, Thomas H. Cormen, Time complexity, Trial division, Vaughan Pratt, Wilson's theorem, ZPP (complexity). Expand index (35 more) » « Shrink index
AC0 is a complexity class used in circuit complexity.
In computational number theory, the Adleman–Pomerance–Rumely primality test is an algorithm for determining whether a number is prime.
In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test.
The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in a paper titled "PRIMES is in P".
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers.
The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is a probable prime.
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.
Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist.
In number theory, a Carmichael number is a composite number n which satisfies the modular arithmetic congruence relation: for all integers b which are relatively prime to n. They are named for Robert Carmichael.
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof.
Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science.
In computational complexity theory, co-NP is a complexity class.
A composite number is a positive integer that can be formed by multiplying together two smaller positive integers.
Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.
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 logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule or law.
Cryptography or cryptology (from κρυπτός|translit.
In computer science, a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.
A divisibility rule is a shorthand way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits.
In mathematics elliptic curve primality testing techniques are among the quickest and most widely used methods in primality proving.
In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and (where mod refers to the modulo operation).
In mathematics, factorization (also factorisation in some forms of British English) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind.
The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.
Fermat's little theorem states that if is a prime number, then for any integer, the number is an integer multiple of.
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones: Often, especially in modern usage, the sequence is extended by one more initial term: By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.
In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers.
In number theory, a Frobenius pseudoprime is a pseudoprime that passes a specific probable prime test described by Jon Grantham in a 1998 preprint and published in 2000.
Gary Lee Miller is a professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States.
The Riemann hypothesis is one of the most important conjectures in mathematics.
George Barry Purdy (20 February 1944 - 30 December 2017) was a mathematician and computer scientist who specialized in cryptography, combinatorial geometry and number theory.
In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
Jacobi symbol for various k (along top) and n (along left side).
John Lewis Selfridge (February 17, 1927 in Ketchikan, Alaska – October 31, 2010 in DeKalb, Illinois), was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.
The Journal of Computer and System Sciences (JCSS) is a peer-reviewed scientific journal in the field of computer science.
In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space.
Leonard Adleman (born December 31, 1945) is an American computer scientist.
In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known.
Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.
In mathematics, the Lucas sequences U_n(P,Q) and V_n(P, Q) are certain constant-recursive integer sequences that satisfy the recurrence relation where P and Q are fixed integers.
Manindra Agrawal (born 20 May 1966) is a professor at the Department of Computer Science and Engineering and the Deputy Director at the Indian Institute of Technology, Kanpur.
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.
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 number theory, given an integer a and a positive integer n with gcd(a,n).
In complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.
Neeraj Kayal (नीरज कयाल) is an Indian computer scientist.
Nitin Saxena (नितिन सक्सेना) (born 3 May 1981) is an Indian scientist in mathematics and theoretical computer science.
In computational complexity theory, NP (for nondeterministic polynomial time) is a complexity class used to describe certain types of decision problems.
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.
In complexity theory, a decision problem is P-complete (complete for the complexity class '''P''') if it is in P and every problem in P can be reduced to it by an appropriate reduction.
In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer.
In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime.
A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
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 mathematics, and more particularly in number theory, primorial is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, only prime numbers are multiplied.
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 number theory, Proth's theorem is a primality test for Proth numbers.
Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.
A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime.
Quantum computing is computing using quantum-mechanical phenomena, such as superposition and entanglement.
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.
Recursion occurs when a thing is defined in terms of itself or of its type.
In mathematics, the remainder is the amount "left over" after performing some computation.
Richard E. Crandall (December 29, 1947 – December 20, 2012) was an American physicist and computer scientist who made contributions to computational number theory.
Ronald Linn Rivest (born May 6, 1947) is a cryptographer and an Institute Professor at MIT.
In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.
RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission.
In probability theory, the sample space of an experiment or random trial is the set of all possible outcomes or results of that experiment.
Samuel Standfield Wagstaff Jr. (born 21 February 1945) is an American mathematician and computer scientist, whose research interests are in the areas of cryptography, parallel computation, and analysis of algorithms, especially number theoretic algorithms.
Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization formulated in 1994.
In mathematics, the sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.
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.
In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also 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 number theory, a probable prime is a number that passes a primality test.
The Art of Computer Programming (sometimes known by its initials TAOCP) is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis.
Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein.
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
Trial division is the most laborious but easiest to understand of the integer factorization algorithms.
Vaughan Pratt (born on April 12, 1944) is a Professor Emeritus at Stanford University, who was an early pioneer in the field of computer science.
In number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is (using the notations of modular arithmetic), one has that the factorial (n - 1)!.
In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.