Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

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

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

Свойства

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

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

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

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

Вариации

Вероятно простое Эйлера по основанию a — это целое число, выполняющее условия простоты, более сильные чем теорема: для любого простого p, a(p − 1)/2 равно по основанию p, где  — символ Лежандра. Вероятно простые Эйлера, являющиеся составными, называются псевдопростыми числами Эйлера — Якоби по основанию a.

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

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

См. также

Ссылки

Эта страница в последний раз была отредактирована 23 апреля 2018 в 06:31.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).