  Communication
Free Faster access than browser!

# Primality test

A primality test is an algorithm for determining whether an input number is prime. 

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

## AC0

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.

## Agrawal's conjecture

In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test.

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

## Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

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

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

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

## Carl Pomerance

Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist.

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

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

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

## Co-NP

In computational complexity theory, co-NP is a complexity class.

## Composite number

A composite number is a positive integer that can be formed by multiplying together two smaller positive integers.

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

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

## Counterexample

In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule or law.

## Cryptography

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

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

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

## Elliptic curve primality

In mathematics elliptic curve primality testing techniques are among the quickest and most widely used methods in primality proving.

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

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

## Fermat primality test

The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.

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

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

## Fibonacci polynomials

In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers.

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

## Gary Miller (computer scientist)

Gary Lee Miller is a professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States.

## Generalized Riemann hypothesis

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

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

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

## Integer factorization

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

## Introduction to Algorithms

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

## Jacobi symbol

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

## John Selfridge

John Lewis Selfridge (February 17, 1927 in Ketchikan, Alaska &ndash; October 31, 2010 in DeKalb, Illinois), was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.

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

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

Leonard Adleman (born December 31, 1945) is an American computer scientist.

## 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 &minus; 1 be already known.

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

## 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

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

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.

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

## Multiplicative order

In number theory, given an integer a and a positive integer n with gcd(a,n).

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

## Neeraj Kayal

Neeraj Kayal (नीरज कयाल) is an Indian computer scientist.

## Nitin Saxena

Nitin Saxena (नितिन सक्सेना) (born 3 May 1981) is an Indian scientist in mathematics and theoretical computer science.

## NP (complexity)

In computational complexity theory, NP (for nondeterministic polynomial time) is a complexity class used to describe certain types of decision problems.

## P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.

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

## Pocklington primality test

In mathematics, the Pocklington&ndash;Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer.

## Primality certificate

In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime.

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

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

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

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

## Proth's theorem

In number theory, Proth's theorem is a primality test for Proth numbers.

## Pseudocode

Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.

## Pseudoprime

A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime.

## Quantum computing

Quantum computing is computing using quantum-mechanical phenomena, such as superposition and entanglement.

## Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.

## Recursion

Recursion occurs when a thing is defined in terms of itself or of its type.

## Remainder

In mathematics, the remainder is the amount "left over" after performing some computation.

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

## Ron Rivest

Ronald Linn Rivest (born May 6, 1947) is a cryptographer and an Institute Professor at MIT.

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

## RSA (cryptosystem)

RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission.

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

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

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

## Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.

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

## Sophie Germain 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.

## Strong pseudoprime

In number theory, a probable prime is a number that passes a primality test.

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

## Thomas H. Cormen

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein.

## Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

## Trial division

Trial division is the most laborious but easiest to understand of the integer factorization algorithms.

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

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

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

## References

Hey! We are on Facebook now! »