Тест Соловея — Штрассена

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 09:22, 12 мая 2016.

Теорема непсевдопростоты

TemplateTheoremIcon.svg Теорема Теорема
Если - не псевдопростое для основания , то оно не псевдопростое хотя бы для половины оснований.
Доказательство
Пусть число - псевдопростое для оснований .

Тогда рассмотрим множество оснований (все по )

Если по основанию - псевдопростое, то по этому основанию - тоже псевдопростое, , противоречие тому, что - не псевдопростое все элементы являются основанием, по которым - не псевдопростое если есть оснований, по которым число псевдопростое, то етсть и оснований, по которым число не псевдопростое.

Вывод: если есть множество оснований и число, то если его проверять, вероятность непрохождения теста равна 1/2.

Пусть есть различных оснований. Если для любого , то число является простым с вероятностью (если число не является числом Кармайка).

, где - символ Якоби

Если простое, то верно всегда.

Число , для которого выполняется выражение для некоторого параметра , называют эйлеровым псевдопростым по основанию .


Об Эйлеровом псевдопростом

TemplateTheoremIcon.svg Теорема Об Эйлеровом псевдопростом
Если эйлерово псевдопростое по основанию , то это просто псевдопростое по основанию .
Доказательство

!Обратное утверждение в общем случае неверно.


TemplateTheoremIcon.svg Теорема Теорема
Если для выполняется по основанию и не выполняется по основанию , то оно не выполняется по основанию .
Доказательство


TemplateTheoremIcon.svg Теорема Теорема
Пусть - составное число, , если такое , для которого выполняются 2 условия:
  1. ( - любые из этих простых)

Тогда для выражение по основанию не выполняется:

Доказательство
если , но при этом : слева 1, справа -1.

Надо доказать, что

Заметим, что

Предположим, что при некотором .

если , то , противоречие с тем, что - четное


, пусть

Рассмотрим

Тогда элементы множества являются основаниями, по которым - эйлерово псевдопростое, - множество множество оснований, по которым не является псевдопростым.

Если составное, то оно не пройдет с вероятностью 1/2.

различных оснований.
- вероятность того, что составное, если по основаниям - эйлерово псевдопростое.

Отсюда следует, что аналогов чисел Кармайка не существует (по определению Эйлера).

Это - тест Соловея-Штрассена.

Пример

TemplateExampleIcon.svg Пример Пример

Это число является простым с вероятностью 1/2.

Число - составное.