Вероятное простое число

В теории чисел вероятное простое число ( PRP ) — это целое число , которое удовлетворяет определенному условию, которому удовлетворяют все простые числа , но которому не удовлетворяет большинство составных чисел . Различные типы вероятных простых чисел имеют разные конкретные условия. Хотя могут существовать сложные простые числа (так называемые псевдопростые числа ), это условие обычно выбирается для того, чтобы сделать такие исключения редкими.

Тест Ферма на составность, основанный на малой теореме Ферма , работает следующим образом: учитывая целое число n , выберите некоторое целое число a, которое не кратно n ; (обычно мы выбираем a в диапазоне 1 < a < n − 1 ). Рассчитать ^{п - 1} по модулю н . Если результат не равен 1, то n составное. Если результат равен 1, то n , скорее всего, будет простым; n тогда называется вероятным простым числом по основанию a . Слабое вероятное простое число по основанию a — это целое число, которое является вероятным простым числом по основанию a , но не является сильным вероятным простым числом по основанию a (см. ниже).

Для фиксированной базы a составное число обычно не является вероятным простым (т. е. псевдопростым) по отношению к этой базе. Например, до 25×10 ⁹, существует 11 408 012 595 нечетных составных чисел, но только 21 853 псевдопростых числа по основанию 2. ^[1]^: 1005 Количество нечетных простых чисел в одном интервале равно 1 091 987 404.

Характеристики

Вероятностная простота является основой эффективных проверки простоты алгоритмов , которые находят применение в криптографии . Эти алгоритмы обычно носят вероятностный характер. Идея состоит в том, что, хотя существуют составные вероятные простые числа, составляющие основу a для любого фиксированного a , мы можем надеяться, что существует некоторый фиксированный P <1 такой, что для любого данного составного n , если мы выберем a наугад, тогда вероятность того, что n является псевдопростым основание a не превосходит P . Если мы повторим этот тест k раз, каждый раз выбирая новое a , вероятность того, что n будет псевдопростым для всех проверенных a , следовательно, не превысит P. ^к, и поскольку она уменьшается экспоненциально, требуется лишь умеренное k , чтобы сделать эту вероятность пренебрежимо малой (по сравнению, например, с вероятностью аппаратной ошибки компьютера).

К сожалению, это неверно для слабых вероятных простых чисел, поскольку существуют числа Кармайкла ; но это верно для более тонких понятий вероятной простоты, таких как сильные вероятные простые числа ( P = 1/4, алгоритм Миллера-Рабина ) илиВероятные простые числа Эйлера ( P = 1/2, алгоритм Соловея – Штрассена ).

Даже когда требуется детерминированное доказательство простоты, первым полезным шагом будет проверка вероятной простоты. Это может быстро (с уверенностью) исключить большинство композитов.

Тест PRP иногда сочетается с таблицей маленьких псевдопростых чисел, чтобы быстро установить простоту заданного числа, меньшего некоторого порога.

Вариации

Вероятное простое число Эйлера по основанию a — это целое число, которое обозначается простым согласно несколько более сильной теореме, согласно которой для любого простого p a числа ^{( п −1)/2} равно $({\tfrac {a}{p}})$ по модулю p , где $({\tfrac {a}{p}})$ — символ Якоби . Вероятное простое число Эйлера, которое является составным, называется псевдопростым числом Эйлера – Якоби с основанием a . Наименьшее псевдопростое число Эйлера-Якоби по основанию 2 равно 561. ^[1]^: 1004 Существует 11347 псевдопростых чисел Эйлера-Якоби по основанию 2, которые меньше 25 · 10. ⁹. ^[1]^: 1005

Этот тест можно улучшить, используя тот факт, что единственными квадратными корнями из 1 по модулю простого числа являются 1 и -1. Запишите n = d · 2 ^с + 1, где d нечетно. Число n является сильным вероятным простым числом ( SPRP ) по основанию a , если:

a^{d}\equiv 1{\pmod {n}},\;

или

a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ for some }}0\leq r\leq s-1.\,

Составное сильное вероятное простое число по основанию a называется сильным псевдопростым числом по основанию a . Каждое сильное вероятное простое число по основанию a также является вероятным простым числом Эйлера по тому же основанию, но не наоборот.

Наименьшее сильное псевдопростое основание 2 — 2047. ^[1]^: 1004 Существует 4842 сильных псевдопростых числа по основанию 2, число которых меньше 25·10. ⁹. ^[1]^: 1005

Существуют также вероятные простые числа Люка , которые основаны на последовательностях Люка . Критерий вероятного простого числа Лукаса можно использовать отдельно. Критерий простоты Бэйли -ПСВ сочетает в себе тест Лукаса и сильный вероятностный тест простого числа.

Пример проверки сильного вероятного простого числа

Чтобы проверить, является ли 97 сильным вероятным простым основанием 2:

Шаг 1: Найдите $d$ $d$ и $s$ $s$ для чего $96=d\cdot 2^{s}$ $96=d\cdot 2^{s}$ , где $d$ $d$ странно
- Начиная с $s=0$ , $d$ было бы $96$
- Увеличение $s$ , мы видим это $d=3$ и $s=5$ , с $96=3\cdot 2^{5}$
Шаг 2: Выберите $a$ , $1<a<97-1$ . мы выберем $a=2$ .
Шаг 3: Рассчитайте $a^{d}{\bmod {n}}$ , то есть $2^{3}{\bmod {9}}7$ . Поскольку это не соответствует $1$ , продолжаем проверять следующее условие
Шаг 4: Рассчитайте $2^{3\cdot 2^{r}}{\bmod {9}}7$ $2^{3\cdot 2^{r}}{\bmod {9}}7$ для $0\leq r<s$ $0\leq r<s$ . Если оно соответствует $96$ $96$ , $97$ $97$ вероятно, является простым. В противном случае, $97$ $97$ определенно является составным
- $r=0:2^{3}\equiv 8{\pmod {97}}$
- $r=1:2^{6}\equiv 64{\pmod {97}}$
- $r=2:2^{12}\equiv 22{\pmod {97}}$
- $r=3:2^{24}\equiv 96{\pmod {97}}$
Поэтому, $97$ является сильным вероятным простым основанием 2 (и, следовательно, является вероятным простым основанием 2).

См. также

Внешние ссылки

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .

[PSW-1] Перейти обратно: ^а ^б ^с ^д ^и Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .

[1]

v т и Классы простых чисел
По формуле	Ферма ( $2 2 н + 1$ ) Мерсенн ( $2 п - 1$ ) Двойной Мерсенн ( $2 2 п -1 - 1$ ) Вагстафф $(2 п + 1)/3$ Прот ( $k \cdot2 н + 1$ ) Факториал ( $n! \pm 1$ ) Первобытный ( $p n # \pm 1$ ) Евклид ( $p n # + 1$ ) Пифагорейский ( $4 n + 1$ ) Пьерпон ( $2 м \cdot3 н + 1$ ) Квартан ( $х 4 + и 4$ ) Солинас ( $2 м \pm 2 н \pm 1$ ) Каллен ( $n \cdot2 н + 1$ ) Вудалл ( $n \cdot2 н - 1$ ) Кубинский ( $х 3 - и 3)/(Икс - у$ ) Лейланд ( $x и + и х$ ) Сабит ( $3\cdot2 н - 1$ ) Уильямс ( $(b -1)\cdot b н - 1$ ) Миллс ( $⌊ А 3 н ⌋$ )
По целочисленной последовательности	Фибоначчи Лукас Пелл Ньюман–Шэнкс–Уильямс Перрин
По свойству	Виферих ( пара ) Стена–Солнце–Солнце Вулстенхолм Уилсон Удачливый удачливый Рамануджан Пиллаи Обычный Сильный Штерн Суперсингулярная (эллиптическая кривая) Суперсингулярная (теория самогона) Хороший Супер Хиггс Высокий коэффициент Уникальный
Базово -зависимый	палиндромный Эмирп Репунит $(10 н - 1)/9$ Перестановочный Круговой Усекаемый Минимальный Нежный Первобытный Полный отчет Уникальный Счастливый Себя Смарандаш-Веллин Стробограмматический двугранный тетрадный
Узоры	Твин ( $р, р + 2$ ) Двойная цепь ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Тройка ( $p, p +2 или p +4, p +6$ ) Четверка ( $р, р +2, р +6, р +8$ ) k -кортеж Двоюродный брат ( $п, р + 4$ ) Сексуальный ( $п, п + 6$ ) Чен Софи Жермен/Сейф ( $п, 2п +1$ ) Каннингем ( $п, 2 п \pm 1, 4 п \pm 3, 8 п \pm 7, ...$ ) Арифметическая прогрессия ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Сбалансированный ( $последовательные p - n, p, p + n$ )
По размеру	Мега (1 000 000+ цифр) Самый крупный известный список
Комплексные числа	Айронстоун прайм Гауссово простое число
Составные числа	Псевдопростой каталанский Эллиптический Эйлер Эйлер-Якоби Ферма Фробениус Лукас Перрин Сомер-Лукас Сильный Число Кармайкла Почти премьер Полупервоклассный Сфеническое число Интерпрайм Пагубный
Связанные темы	Вероятное простое число Промышленный класс Prime Незаконный премьер Формула простых чисел Премьер-разрыв
Первые 60 простых чисел	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
Список простых чисел