Tester si un nombre est prime
Primality testing determines si un nombre est prime. Apprendre trial division, Miller-Rabin, et deterministic tests.
- 1
Primality tests: Trial division (check divisibility by primes up to sqrt(n) — slow for large n), Fermat (a^(n-1) ≡ 1 mod n — fooled by Carmichael numbers), Miller-Rabin (probabilistic, fast, widely used), AKS (deterministic, polynomial time, but slow in practice), BPSW (probabilistic, no known counterexamples). For crypto, Miller-Rabin with 40+ rounds is standard.
- 2 Vérificateur de nombres premiers →
Test a number for primality. The tool uses Miller-Rabin with multiple rounds. For small numbers (< 2^64), deterministic checks are used. For large numbers, the result is "probably prime" with error probability < 2^-80 (with enough rounds).
- 3 Calculatrice de diviseurs →
If the number is composite, factor it to see its prime factors. This confirms the primality test result — a composite number will have factors other than 1 and itself. Factoring is much harder than primality testing for large numbers (basis of RSA security).
Questions fréquentes
- Is Miller-Rabin ever wrong?
- Miller-Rabin is probabilistic — a composite number has at most 1/4 chance of passing each round. With 40 rounds, the error probability is (1/4)^40 ≈ 10^-24. For practical purposes, this is never wrong. For deterministic results on numbers < 3.3×10^24, testing specific bases (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) is sufficient.
- Why not use the AKS test?
- AKS is deterministic and polynomial-time (theoretically important), but it is much slower than Miller-Rabin in practice. The constant factors are large. For practical applications, Miller-Rabin with enough rounds is preferred — it is faster and the error probability is negligible.