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

В теории чисел ( вероятное простое число 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 ⁹ JSTOR (PDF) Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . 2006210 . .

[PSW-1] Перейти обратно: ^а ^б ^с ^д ^Это Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹ JSTOR (PDF) Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . 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 \pm1, 2n \pm 1, 4n \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
Список простых чисел