Тільки до обчислення Було Залуччя близьким 600 добровольців та 1600 компютерів, что працювать впродовж 220 днів. br/>
3.2 Алгоритми та програмна реалізація системи
Далі наведемо алгоритми, вікорістані безпосередно при напісанні кодом програми.
3.2.1 Обчислення а d (mоd m)
1.запісуємо число d у двійковій Системі числення:
= d02r + d12r-1 + ... + dr-12 + dr,
де di - 0 або 1, d0 = 1.
. Покладемо а0 = а, шкірних Наступний аi обчіслюємо за формулою
В
. аr и є Шуканов значень аd (mоd m).
Справедливість цього алгоритму віпліває з наступної формули:
.
3.2.2 Алгоритм Евкліда поиска НСД (а, b)
1.Обчіслюємо r - остачу від ділення а на b (Не порушуючі загальності, чи можемо вважаті а> b).
. Если r = 0, то b и є Шуканов число.
. Если r В№ 0, то замінюємо пару (а, b) на (b, r) i повторюємо спочатку.
3.2.3 Генератор простих чисел
Тут мається на увазі програма підбору й достатньо великих простих чисел. Принцип ее Дії грунтується на наступній теоремі. p align="justify"> Теорема. Нехай N, S - непарні натуральні числа, Такі, что N-1 = S * R, причому " простого дільніка q числа S $ таке натуральне а, что:
.
Тоді " Простий дільнік р числа N задовольняє
р 1 (mоd 2S).
Наслідок. Если віконані умови теореми и R? 4S +2, то N - просте число. p align="justify"> Маємо Наступний алгоритм:
. Обираємо S - Деяк просте число та R - хлопця з проміжку S? R? 4S +2.
. Перевіряємо число N = RS +1: Якщо N не прості, то Обираємо Інше R, пока не Знайдемо просте число. Побудоване таким чином, N > S 2 < span align = "justify">, а значити - має вдвічі більшій розряд.
. У разі необхідності беремо N в якості віхідного простого числа и повторюємо алгоритм, поки знайдення просте число не якщо й достатньо великим.
цею способ реалізується й достатньо просто и дозволяє на персональному комп ютері отрімуваті Прості числа порядком 10 10 < span align = "justify">.
3.3 Кріптоаналіз RSА
Розглянемо деякі Елементарні атаки на систему та Способи захисту від них.
