프로트의 정리(Proth's theorem)는 정수론에서 프로트 수(Proth number)에 대한 소수 판별법을 제공하는 정리이다. 1878년 프랑스의 수학자 프랑수아 프로트(François Proth, 1852–1879)가 발표하였다.
프로트 수는 홀수 k와 양의 정수 n에 대하여 p = k·2ⁿ + 1의 형태로 표현되며, 2ⁿ > k인 조건을 만족하는 정수를 말한다. 프로트의 정리에 따르면, 어떤 프로트 수 p에 대하여 다음 조건을 만족하는 정수 a가 존재할 경우 p는 소수(素數)이다.
a^(p-1)/2 ≡ -1 (mod p)
이때 p를 프로트 소수(Proth prime)라고 부른다. 이 정리의 역 또한 성립하는데, 즉 프로트 수 p가 소수라면 위 조건을 만족하는 a가 반드시 존재한다. 실제로 p가 소수일 경우 무작위로 선택한 a가 위 조건을 만족할 확률은 약 50%이다. 따라서 이 정리는 프로트 수에 대한 효율적인 소수 판별 도구로 사용된다.
실용적인 구현에서는 a를 이차 비잉여(quadratic nonresidue)로 선택하는 방식이 주로 사용된다. 이 경우 테스트는 결정적(deterministic)으로 작동하며, 라스베이거스 알고리즘(Las Vegas algorithm)의 형태를 띤다.
프로트의 정리는 포클링턴-레머 소수 판별법(Pocklington-Lehmer primality test)을 이용하여 증명할 수 있으며, 페팽의 테스트(Pépin's test)는 k=1인 특수한 경우에 해당한다.
가장 작은 프로트 소수들은 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 등이다. 2016년 기준으로 알려진 가장 큰 프로트 소수는 10223 × 2^31172165 + 1이며, 이는 9,383,761자리의 수로 PrimeGrid 분산 컴퓨팅 프로젝트를 통해 발견되었다. 이는 메르센 소수가 아닌 소수 중 가장 큰 것으로 알려져 있다.
