Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Теорема Сэлфриджа.

Читайте также:
  1. Определитель n-го порядка. Теорема о разложении определителя.
  2. Теорема (принцип максимума Понтрягина).
  3. Теорема 1.
  4. Теорема гипотез и Байесовские подходы.
  5. Теорема гипотез и Байесовские подходы.
  6. Теорема Диемитко.
  7. Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1).

Пусть n —1= . n – простое, a: 1) an —1≡1(mod n);

2) 1(mod n).

Доказательство:

Пусть n – простое число. Тогда (1) выполняется для всех a<n согласно теореме Ферма. В силу критерия Люка, найдется a: O n (a)= n —1 s<n —1 выполняется as 1(mod n), а поскольку , < n —1, то выполняется (2).

Возьмем q 1. Пусть a: 1) an —1≡1(mod n); 2) 1(mod n). Из (1) и (2) следует, что O n (a)\(n —1) и O n (a) не делит . Откуда из * следует, что \O n (a). Согласно Теореме 3 (п.1), O n (a)\φ(n) \ φ(n).

Рассматривая аналогичным образом q 2, q 3,…, qk, убеждаемся, что \φ(n), \φ(n), …, \φ(n). Тогда =(n —1)\φ(n). Но последнее возможно только в случае, когда n —1=φ(n), то есть тогда, когда n – простое число.

Теорема Сэлфриджа дает удобный критерий для доказательства простоты числа. На основании этой теоремы построены алгоритмы проверки чисел на простоту, которые требуют полной или частичной факторизации числа n —1, а потому называются n —1 – методами.

В общем случае мы можем говорить о том, что число n —1 по крайней мере четное.

В том случае, когда нам известно полное разложение проверяемого числа на множители, можно использовать следующий

 

тест Миллера на простоту:

Вход: n – число для проверки, n —1= - каноническое разложение, t – параметр надежности.

1. Выбрать t различных случайных чисел aj: 1 <aj<n

2. Для каждого aj вычислить ajn—1 mod n. Если какой-либо из результатов не равен «1», то идти на Выход с сообщением «n – составное число».

3. Для каждого qi выполнить:

3.1. Для каждого aj вычислить mod n. Если какой-либо из результатов не равен единице, то идти на шаг 3, взять следующее qi. Если все результаты равны «1», то идти на Выход с сообщением «вероятно, n – составное число».

4. Идти на Выход с сообщением «n – простое число».

Выход.

 

Замечание: Если t=n— 2, то слово «вероятно» на шаге 3.1. следует убрать.

Если число n было предварительно проверено на простоту вероятностным тестом Миллера-Рабина, то в тесте Миллера достаточно перебрать 4-6 значений aj.

Тест Миллера, основанный на теореме Сэлфриджа, пригоден для доказательства простоты любого нечетного числа, если известно разложение на простые сомножители числа, ему предстоящего. Однако этот тест достаточно трудоемок. Для некоторых чисел особого вида построены специальные доказательства простоты. Некоторые из таких чисел мы рассмотрим в п.3-4.


Дата добавления: 2015-09-07; просмотров: 254 | Нарушение авторских прав


Читайте в этой же книге: Теорема 1. | Символ Лежандра. | Тест на простоту Соловея-Штрассена. | Квадраты и псевдоквадраты. | Числа Блюма. | Криптосистема Блюма-Гольдвассер (Blum-Goldwasser). | Криптосистема Гольдвассер-Микали. | Теорема Диемитко. | Метод квадратичного решета. |
<== предыдущая страница | следующая страница ==>
Тест на простоту Миллера-Рабина.| Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1).

mybiblioteka.su - 2015-2024 год. (0.013 сек.)