Генерация больших простых и псевдопростых чисел. Генерация (детерминистическая) больших простых с подбором разложения функции Эйлера

Петербургский Государственный Университет Путей Сообщения

кафедра “информатика и информационная безопасность ”

Лабораторная работа № 3

                                                                                                             Выполнил ст. гр. КИБ-708

                                                                                                             Таранин В.В.

                                                                                                             Проверил: Еремеев М.А.

Санкт-Петербург

2010

«Генерация больших простых и псевдопростых чисел»

Формирую простое число заданного размера посредством вероятностных тестов.

Беру большое число p = 5001.

Использую тест Ферма.

Осуществляю проверку соотношения bp - 1 = 1 (mod p) в качестве параметра b использую значения от 2 до 1999.

Так  уже при b = 2  bp - 1(mod p) = 4. Значит p = 5001 – составное.

Так  уже при b = 2  bp - 1(mod p) = 4. Значит p = 5007 – составное

Беру следующее нечётное число p = 5003, p = 5009.  Также проверяю соотношение теста Ферма при параметре b от 2 до 1999. При всех данных значениях число p проходит тест Ферма.

Для окончательной проверки данного числа на простоту, применяю тест Соловея-Штрассена. В качестве параметра x использую числа от 1 до 100. Проверяя следующее выражение:

(где  символ Лежандра. Для значений b являющихся квадратичными вычетами по модулю p , а b = x² mod p)

устанавливаю, что p = 1000003 –  псевдопростое число с вероятностью (½)¹⁰⁰ = 7.8*10^-31

Беру третье  число p = 949667 и проверяю его на простоту комбинированным способом. Для тех же условий, что и в предыдущем случае, число проходит тест Ферма. В качестве детерминированного теста использую метод пробных делений.

Необходимо проверить делимость числа p на все числа от 2 до , т.е. от 2 до 974.

Проверка показывает, что число p = 949667 – простое.

 «Генерация (детерминистическая) больших простых с подбором разложения функции Эйлера»

Формирую набор 10 простых чисел: (3, 5, 7, 9, 13, 15, 17, 19, 21).

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

Из указанного набора выбираю по 3 числа. К примеру (3, 5, 7).  Вычисляю число p₁

p₁ = 1 + 2*(3*5*7) = 211;

Выбираю b = 2 и проверяю соотношения:

1)  bp₁ - 1 = 1  (mod p) 

2)   для всех m_i Î {m₁, m₂, …, m_k}.

они выполняются, значит число 211 – простое;

Беру другой набор чисел (9, 13, 15). Выполняю ту же проверку. b = 2;

p₁ = 1 + 2*(9*13*15) = 3511;

проверяю соотношения.  Они выполняются, значит число 3511 – простое;

Беру другой набор чисел (17, 19, 21). Выполняю ту же проверку. b = 2;

p₁ = 1 + 2*(17*19*21) = 13567

проверяю соотношения. Они выполняются, значит число 13567 – простое;

«Генерация (детерминистическая) больших простых чисел по стандарту ГОСТ Р 34.10-94»

Для нахождения простого числа используется следующая формула:

p_i - 1= p_iN + 1

p₂ = p₃N + 1 = 7*10 + 1 = 71

1) 2p₃N = 1 mod p₂  = 2⁷⁰ = 1 mod 71 

2) 2^N ¹ 1 mod p₂  = 2¹⁰ = 30 mod 71 

p₁ = p₂N + 1 = 71*8 + 1 = 569

1) 2p₂N = 1 mod p₁  = 2^71*8 = 1 mod 569 

2) 2^N ¹ 1 mod p₁  = 2⁸ = 256 mod 569 

p₀ = p₁N + 1 = 569*34 + 1 = 19347

1) 2p₁N = 1 mod p₀  = 2^569*34 = 1 mod 19347 

2) 2^N ¹ 1 mod p₀  = 2³⁴ = 4042 mod 19347