Teste de Primalidade

Small-number primality testing

A positive integer n > 1 counts as prime when its only positive divisors are 1 and n itself. The plainest deterministic test is trial division: ask whether any prime p ≤ √n divides n. That runs in O(√n), which stays comfortable up to roughly 10¹². Take n = 97: since √97 ≈ 9.85, the only candidates are 2, 3, 5, 7, and none of them divides 97, so it's prime. When you need to screen a whole range, the Sieve of Eratosthenes precomputes every prime up to a bound in O(N log log N). For the much larger n behind cryptographic keys, Miller-Rabin returns a probabilistic answer in O(k log³ n), while AKS is deterministic in O(log⁶ n) but carries a constant too large to be useful in practice. Mersenne primes Mₚ = 2ᵖ − 1 get their own specialised test, Lucas-Lehmer. That's how the largest known prime turned up, M82589933 (24 million digits, GIMPS 2018).

Where primality testing is used

• RSA key generation — the whole keypair rests on picking large random primes p, q.
• OpenSSL, GnuPG and cryptographic libraries run Miller-Rabin against several bases every time they generate a key.
• Diffie-Hellman / ElGamal rely on safe primes p = 2q + 1 where q is prime as well.
• Competitive programming — number-theory problems lean on sieves and small primality checks all the time.

FAQ

Why test only up to √n? Write n = a · b with a ≤ b and you get a ≤ √n, so every composite is guaranteed a factor inside that range.

Is Miller-Rabin reliable? The error drops to 4^(−k) as you add random bases k. Crypto usually settles on k = 40, which pushes the odds of a wrong answer to astronomical levels.

Why is 1 not considered prime? Allowing it would wreck unique factorisation, since 6 = 2·3 = 1·2·3 = 1·1·2·3 … all become valid.

When should I use a sieve instead of trial division? Reach for the sieve once you need every prime up to N, or many tests across the same range. It spreads the cost over all the queries.