Faster access than browser!
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) »
AC0
AC0 is a complexity class used in circuit complexity.
New!!: Primality test and AC0 · See more »
Adleman–Pomerance–Rumely primality test
In computational number theory, the Adleman–Pomerance–Rumely primality test is an algorithm for determining whether a number is prime.
New!!: Primality test and Adleman–Pomerance–Rumely primality test · See more »
Agrawal's conjecture
In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test.
New!!: Primality test and Agrawal's conjecture · See more »
AKS primality 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".
New!!: Primality test and AKS primality test · See more »
Algorithm
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
New!!: Primality test and Algorithm · See more »
Analytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers.
New!!: Primality test and Analytic number theory · See more »
Baillie–PSW primality test
The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is a probable prime.
New!!: Primality test and Baillie–PSW primality test · 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!!: Primality test and Big O notation · See more »
Carl Pomerance
Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist.
New!!: Primality test and Carl Pomerance · See more »
Carmichael number
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.
New!!: Primality test and Carmichael number · See more »
Charles E. Leiserson
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof.
New!!: Primality test and Charles E. Leiserson · See more »
Clifford Stein
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.
New!!: Primality test and Clifford Stein · See more »
Co-NP
In computational complexity theory, co-NP is a complexity class.
New!!: Primality test and Co-NP · See more »
Composite number
A composite number is a positive integer that can be formed by multiplying together two smaller positive integers.
New!!: Primality test and Composite number · See more »
Computational complexity theory
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.
New!!: Primality test and Computational complexity theory · 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!!: Primality test and Coprime integers · See more »
Counterexample
In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule or law.
New!!: Primality test and Counterexample · See more »
Cryptography
Cryptography or cryptology (from κρυπτός|translit.
New!!: Primality test and Cryptography · See more »
Deterministic algorithm
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.
New!!: Primality test and Deterministic algorithm · See more »
Divisibility rule
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.
New!!: Primality test and Divisibility rule · See more »
Elliptic curve primality
In mathematics elliptic curve primality testing techniques are among the quickest and most widely used methods in primality proving.
New!!: Primality test and Elliptic curve primality · See more »
Euler pseudoprime
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).
New!!: Primality test and Euler pseudoprime · See more »
Factorization
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.
New!!: Primality test and Factorization · See more »
Fermat primality test
The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.
New!!: Primality test and Fermat primality test · See more »
Fermat's little theorem
Fermat's little theorem states that if is a prime number, then for any integer, the number is an integer multiple of.
New!!: Primality test and Fermat's little theorem · See more »
Fibonacci number
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.
New!!: Primality test and Fibonacci number · See more »
Fibonacci polynomials
In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers.
New!!: Primality test and Fibonacci polynomials · See more »
Frobenius pseudoprime
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.
New!!: Primality test and Frobenius pseudoprime · See more »
Gary Miller (computer scientist)
Gary Lee Miller is a professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States.
New!!: Primality test and Gary Miller (computer scientist) · See more »
Generalized Riemann hypothesis
The Riemann hypothesis is one of the most important conjectures in mathematics.
New!!: Primality test and Generalized Riemann hypothesis · See more »
George B. Purdy
George Barry Purdy (20 February 1944 - 30 December 2017) was a mathematician and computer scientist who specialized in cryptography, combinatorial geometry and number theory.
New!!: Primality test and George B. Purdy · See more »
Greatest common divisor
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.
New!!: Primality test and Greatest common divisor · See more »
Integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.
New!!: Primality test and Integer factorization · See more »
Introduction to Algorithms
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
New!!: Primality test and Introduction to Algorithms · See more »
Jacobi symbol
Jacobi symbol for various k (along top) and n (along left side).
New!!: Primality test and Jacobi symbol · See more »
John Selfridge
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.
New!!: Primality test and John Selfridge · See more »
Journal of Computer and System Sciences
The Journal of Computer and System Sciences (JCSS) is a peer-reviewed scientific journal in the field of computer science.
New!!: Primality test and Journal of Computer and System Sciences · See more »
L (complexity)
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.
New!!: Primality test and L (complexity) · See more »
Leonard Adleman
Leonard Adleman (born December 31, 1945) is an American computer scientist.
New!!: Primality test and Leonard Adleman · See more »
Lucas primality test
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.
New!!: Primality test and Lucas primality test · See more »
Lucas pseudoprime
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.
New!!: Primality test and Lucas pseudoprime · See more »
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.
New!!: Primality test and Lucas sequence · See more »
Manindra Agrawal
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.
New!!: Primality test and Manindra Agrawal · See more »
Mathematics
Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
New!!: Primality test 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!!: Primality test and Miller–Rabin primality test · 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!!: Primality test and Modular arithmetic · See more »
Multiplicative order
In number theory, given an integer a and a positive integer n with gcd(a,n).
New!!: Primality test and Multiplicative order · See more »
NC (complexity)
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.
New!!: Primality test and NC (complexity) · See more »
Neeraj Kayal
Neeraj Kayal (नीरज कयाल) is an Indian computer scientist.
New!!: Primality test and Neeraj Kayal · See more »
Nitin Saxena
Nitin Saxena (नितिन सक्सेना) (born 3 May 1981) is an Indian scientist in mathematics and theoretical computer science.
New!!: Primality test and Nitin Saxena · See more »
NP (complexity)
In computational complexity theory, NP (for nondeterministic polynomial time) is a complexity class used to describe certain types of decision problems.
New!!: Primality test and NP (complexity) · See more »
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.
New!!: Primality test and P (complexity) · See more »
P-complete
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.
New!!: Primality test and P-complete · See more »
Pocklington primality test
In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer.
New!!: Primality test and Pocklington primality test · See more »
Primality certificate
In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime.
New!!: Primality test and Primality certificate · 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!!: Primality test and Prime number · 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!!: Primality test and Primitive root modulo n · See more »
Primorial
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.
New!!: Primality test and Primorial · 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!!: Primality test and Probable prime · See more »
Proth's theorem
In number theory, Proth's theorem is a primality test for Proth numbers.
New!!: Primality test and Proth's theorem · See more »
Pseudocode
Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.
New!!: Primality test and Pseudocode · See more »
Pseudoprime
A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime.
New!!: Primality test and Pseudoprime · See more »
Quantum computing
Quantum computing is computing using quantum-mechanical phenomena, such as superposition and entanglement.
New!!: Primality test and Quantum computing · See more »
Randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.
New!!: Primality test and Randomized algorithm · See more »
Recursion
Recursion occurs when a thing is defined in terms of itself or of its type.
New!!: Primality test and Recursion · See more »
Remainder
In mathematics, the remainder is the amount "left over" after performing some computation.
New!!: Primality test and Remainder · See more »
Richard Crandall
Richard E. Crandall (December 29, 1947 – December 20, 2012) was an American physicist and computer scientist who made contributions to computational number theory.
New!!: Primality test and Richard Crandall · See more »
Ron Rivest
Ronald Linn Rivest (born May 6, 1947) is a cryptographer and an Institute Professor at MIT.
New!!: Primality test and Ron Rivest · See more »
RP (complexity)
In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.
New!!: Primality test and RP (complexity) · See more »
RSA (cryptosystem)
RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission.
New!!: Primality test and RSA (cryptosystem) · See more »
Sample space
In probability theory, the sample space of an experiment or random trial is the set of all possible outcomes or results of that experiment.
New!!: Primality test and Sample space · See more »
Samuel S. Wagstaff Jr.
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.
New!!: Primality test and Samuel S. Wagstaff Jr. · See more »
Shor's algorithm
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.
New!!: Primality test and Shor's algorithm · See more »
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.
New!!: Primality test and Sieve of Eratosthenes · 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!!: Primality test and Solovay–Strassen primality test · See more »
Sophie Germain prime
In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime.
New!!: Primality test and Sophie Germain prime · 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!!: Primality test and Springer Science+Business Media · See more »
Strong pseudoprime
In number theory, a probable prime is a number that passes a primality test.
New!!: Primality test and Strong pseudoprime · See more »
The Art of Computer Programming
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.
New!!: Primality test and The Art of Computer Programming · See more »
Thomas H. Cormen
Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein.
New!!: Primality test and Thomas H. Cormen · See more »
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
New!!: Primality test and Time complexity · See more »
Trial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms.
New!!: Primality test and Trial division · See more »
Vaughan Pratt
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.
New!!: Primality test and Vaughan Pratt · See more »
Wilson's theorem
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)!.
New!!: Primality test and Wilson's theorem · See more »
ZPP (complexity)
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.
New!!: Primality test and ZPP (complexity) · See more »
Redirects here:
Compositeness test, Detecting primes, Isprime, Primality Testing, Primality proving, Primality testing, Primality tests, Prime testing.
References
[1] https://en.wikipedia.org/wiki/Primality_test
