Math 2.0

concept

Primality test

Summary

A primality test is an algorithm that decides whether a given natural number is prime. Unlike factorization, it does not need to find the factors of a composite number.

Remarks

The simplest test is trial division by the primes up to n\sqrt{n}, but it is slow for large nn. Probabilistic tests, such as the Fermat test and the Miller–Rabin test, are fast but can accept a composite number with a small probability. In 2002, Agrawal, Kayal and Saxena gave the first deterministic test that runs in polynomial time without an unproven hypothesis.

Explanations

L1 human

A primality test answers the question "is nn prime?". For numbers with hundreds of digits, this is much easier than finding the factors of nn.

What this node needs for W2
  • edge defines in: at least one definition (0 of 1)
  • edge instance_of in: at least two examples (0 of 2)
  • edge not_instance_of in: at least one non-example (0 of 1)
  • edge specializes both: the more general notions and the special cases (0 of 1)

The writing levels say how complete the text of a node is. They do not measure its truth.

What this needs

To read this node, read these 3 nodes in this order. The foundations come first, and the list ends with this node.

Divisibility, definition, no evidence levelDivisibilitydefinitionPrime number, definition, no evidence levelPrime numberdefinitionPrimality test, concept, no evidence levelPrimality testconcept
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Divisibility definition
  2. Prime number definition
  3. Primality test concept

What depends on this

1 node uses this node, directly or through other nodes.

Sources

  1. Web https://en.wikipedia.org/wiki/Primality_test, lead section

What links here

Used by