16-07-2023
В теории чисел теорема Прота является тестом простоты для чисел Прота.
Содержание |
Теорема Прота утверждает, что если p — это число Прота вида , где k — нечётно и , и для некоторого целого числа a выполняется сравнение:
то p — простое (называемое простым Прота).
Теорема Прота может быть использована для тестирования простоты чисел Прота, так как, если p — простое Прота, то любое выбранное a имеет шанс около 50% сработать.
Если p — квадратичный невычет по модулю a, то обратное утверждение также верно и испытание является окончательным. Такие a можно найти перебором небольших простых чисел, вычисляя символ Якоби до тех пор, пока не выполнится
Простые числа Прота образуют последовательность:
На июнь 2012 года, крупнейшее известное простое Прота, 19249 · 213018586 + 1, найдено проектом Seventeen or Bust. Оно имеет 3918990 десятичных цифр и является крупнейшим известным простым, не являющимся простым Мерсенна.[1]
Франсуа Прот (англ.) (1852—1879) опубликовал теорему около 1878 года.
Теорема Прота.