Виконано експериментальне дослідження швидкодії алгоритмів генерації простих чисел методом пробних поділів і методами малої теореми Ферма, Рабина Міллера і Соловея Штрассена, що використовують фільтр поділу на малі прості числа. Для кожного з методів представлені тимчасові залежності швидкості генерації від числа розрядів, отримані усередненням великого ансамблю приватних реалізацій.

Анотація наукової статті з математики, автор наукової роботи - Кукало Іван Анатолійович, Міклін Павло Олександрович, Литвинов Рудольф Вікторович


Область наук:
  • Математика
  • Рік видавництва: 2007
    Журнал: Доповіді Томського державного університету систем управління і радіоелектроніки

    Наукова стаття на тему 'Алгоритми генерації псевдопростих чисел в «Borland C ++ 3. 1»'

    Текст наукової роботи на тему «Алгоритми генерації псевдопростих чисел в« Borland C ++ 3. 1 »»

    ?УДК 681.3.067

    І.А. Кукало, П.А. Міклін, Р.В. Литвинов

    Алгоритми генерації псевдопростих чисел в «Бог! Апа С ++ 3.1»

    Виконано експериментальне дослідження швидкодії алгоритмів генерації простих чисел методом пробних поділів і методами малої теореми Ферма, Рабина - Міллера і Соловея - Штрассена, що використовують фільтр поділу на малі прості числа. Для кожного з методів представлені тимчасові залежності швидкості генерації від числа розрядів, отримані усередненням великого ансамблю приватних реалізацій.

    В кінці XX - початку XXI ст. світова спільнота вступила в нову технологічну епоху - епоху інформаційних технологій. Ця індустрія займається виробництвом, обробкою, зберіганням і передачею інформації. Він стала невід'ємною частиною світової господарської системи, цілком самостійним і досить значним сектором економіки. Залежність сучасного суспільства від інформаційних технологій настільки висока, що збої в інформаційних системах здатні привести до значних суспільних і міждержавним інцидентів.

    Передача інформації - ключова галузь для інформаційних технологій, яка відає питаннями транспортування інформації. Однак саме при транспортуванні інформація найбільше вразлива до різного роду зловживань. Дійсно, вузли зберігання і обробки даних з огляду на їх компактності можна фізично захистити від доступу зловмисників, чого не скажеш про лінії зв'язку протяжністю багато сотні або тисячі кілометрів, захистити їх практично неможливо. Тому саме для каналів передачі інформації досить актуальна проблема захисту інформації. Найважливішу роль у вирішенні цієї проблеми відіграє криптографія. Її привабливість полягає в тому, що на відміну від інших підходів криптографічні методи захисту інформації засновані на перетворенні самої інформації і ніяк не пов'язані з характеристиками її матеріальних носіїв, внаслідок чого найбільш універсальні і потенційно дешеві в реалізації.

    Важливим поняттям в криптографії є ​​ключ - змінний елемент шифру, який застосовується для шифрування конкретного повідомлення. При створенні ключів в сучасних асиметричних криптосистемах і їх розподіл між користувачами використовуються великі прості числа, розрядність (біти) яких може досягати декількох сотень або навіть тисяч. Арифметичні операції з такими числами на звичайних ПК вимагають створення спеціального програмного забезпечення [1], в тому числі реалізації швидких алгоритмів генерації простих чисел [2]. Величезна розрядність цих чисел, що диктується сучасними вимогами безпеки, робить детерміновані алгоритми малоефективними. В даний час для цієї мети використовуються методи генерації чисел, простоту яких можна забезпечити з ймовірністю не менше 1-2 128.

    1. Базовий метод генерації великих простих чисел з використанням фільтра поділу на малі прості числа

    Цей метод спирається на теорему Евкліда про нескінченність безлічі простих чисел. Алгоритм роботи методу наступний: генерується псевдовипадкове число п, потім здійснюється тестування цього числа на простоту будь-яким з методів [3]. Спроба триває до тих пір, поки не знайдеться просте число або кількість спроб N не стане рівним

    де К > 1 - коефіцієнт запасу; [...] - операція взяття цілої частини.

    Формула (1) отримана на основі закону розподілу простих чисел, який показує, що ймовірність випадково обраного числа виявитися простим дорівнює 1 / 1ПП. Алгоритм базового методу може бути представлений наступними кроками:

    (1)

    1) задаємо I - нижня межа діапазону, в якому повинно знаходитися просте число;

    2) задаємо і - верхня межа діапазону, в якому повинно знаходитися просте число;

    3) перевіримо коректність завдання діапазону 2 < I < і;

    4) підрахуємо максимальну кількість спроб г ^ 100 ([log2u] +1);

    5) г ^ г - 1;

    6) якщо г < 0, то ліміт спроб вичерпано (подія має дуже малу ймовірність; в наших дослідженнях жодного разу не реалізувалося; в разі його реалізації, необхідно перезапустити програму);

    7) виберемо в заданому інтервалі і < п < I випадкове число п;

    8) якщо п менше, ніж 1999 року, то тестування виконується методом пробного поділу на всі відомі (табульованого) прості числа, менші, ніж п. Якщо дільник існує, то переходимо на крок 5;

    9) якщо п більше, ніж 1999 року, то тестування виконується методом пробного поділу на всі відомі (табульованого) прості числа, менші, ніж 1999. (Цей крок дозволяє виключити 85% складених чисел [1].) Якщо дільник існує, то переходимо на крок 5;

    10) тестуємо п на простоту обраним методом;

    11) якщо тест негативний, переходимо на крок 5;

    12) якщо тест позитивний, то згенеровано просте число в заданому діапазоні. Цей алгоритм реалізований у вигляді програми, написаної на мові програмування

    С ++ і не залежить явно від особливостей того чи іншого тесту, оформленого у вигляді підпрограми, що викликається на кроці 8.

    2. Алгоритми тестування на простоту

    2.1. Метод пробних поділів

    Цей тест являє собою спеціально написану на мові програмування С ++ функцію. Він заснований на пробному послідовному розподілі згенерованого псевдослучайного числа п на всі цілі числа від 2 до [2].

    2.2. Метод на основі малої теореми Ферма

    Тест також оформлений у вигляді спеціально написаної функції. Він використовує твердження малої теореми Ферма про те, що якщо п просте, то виконується умова: при всіх а е {2,3, ..., п-1}, для яких НСД (а, п) = 1, має місце порівняння

    Протилежне твердження невірно. Якщо порівняння (2) не виконано, хоча б для одного а е {2,3, ..., п-1}, то п - складене.

    Для скорочення часу генерації зручно використовувати в якості а ( «свідка» простоти), відомі (табульованого) прості числа, що дозволяє виключити перевірку умови НОД (а, п) = 1. Тоді можна застосувати наступний імовірнісний алгоритм тестування на простоту: г ^ 1.

    Вибираємо з упорядкованого за величиною масиву простих чисел пана е просте число.

    Перевіряємо здійсненність порівняння (2):

    якщо порівняння не виконано, то відповідь «п - складене»;

    якщо порівняння виконано, то г ^ г + 1;

    якщо г < і, то переходимо до кроку 2;

    якщо г > і, то відповідь «п - псевдопростое з точністю 1 - 2 і», де і >1 - коефіцієнт точності.

    2.3. Метод на основі тесту Соловея - Штрассена

    Цей метод заснований на наступній теоремі. Для будь-якого непарного п наступні умови еквівалентні: п - просте, для будь-якого а е ^ виконується порівняння

    а '

    п-1 _

    1 (mod п).

    (2)

    (3)

    Тоді можна використовувати наступний імовірнісний алгоритм тестування на простоту:

    1) г ^ 1;

    2) вибираємо з упорядкованого за величиною масиву простих чисел пана е просте число;

    3) перевіряємо здійсненність порівняння (3);

    4) якщо порівняння не виконано, то відповідь «п - складене»;

    5) якщо порівняння виконано, то г ^ г + 1;

    6) якщо г < U, то переходимо до кроку 2;

    7) якщо г > U, то відповідь «п - псевдопростое з точністю 1 - 2 і», де U > 1 - коефіцієнт точності.

    2.4. Метод на основі тесту Міллера - Рабина

    Нехай п - непарне і п - 1 = 2st; t - непарне. Якщо число п є простим, то при всіх а > 2 виконується порівняння

    an-1 = 1 (mod п). (4)

    t 2t qS_11

    Тому, розглядаючи елементи at, a2t, ..., a2 t, можна помітити, що або серед них знайдеться рівний -1 (mod n), або at = 1 (mod n). На цьому зауваженні заснований наступний імовірнісний тест простоти:

    1) г ^ 1;

    2) вибираємо з упорядкованого за величиною масиву простих чисел пана е просте число;

    3) обчислюємо at (mod п);

    4) якщо at = +1 (mod п), то переходимо до кроку 3;

    / T / t tt tt \ 2s 1

    5) (a), (a), (a) ... (a) (mod п) до тих пір, поки не з'явиться -1;

    6) якщо жодна з цих чисел не дорівнює -1, то відповідь «п - складене»;

    7) якщо ми досягли -1, то г ^ г + 1;

    8) якщо г < U, то переходимо до кроку 2;

    9) якщо г > U, то відповідь «п - псевдопростое з точністю 1 - 4 U», де U > 1 - коефіцієнт точності.

    2.5. Метод генерації псевдовипадкових чисел

    Необхідні для роботи описаних вище алгоритмів псевдовипадкові числа формувалися лінійним конгруентним генератором виду

    Xi + 1 = (Xi | a + 1) modm ,

    де a = 6364136223846793005; m = Параметри a і m були взяті з таблиці результатів спектрального тесту [1]. При цих числах послідовність має максимальну довжину періоду і має гарні статистичними властивостями. Для того щоб тести завжди проводилися з різними числами, перебір даної псевдослучайной послідовності починався з різного члена цієї послідовності, номер якого, в свою чергу, генерувався вбудованим в Borland C ++ 3.1 генератором псевдовипадкових чисел.

    3. Результати численних експериментів

    Описані вище алгоритми були реалізовані у вигляді спеціальних програм, написаних на мові Borland C ++ 3.1 з використанням модулів для елементарних арифметичних операцій з великими числами [1]. У тілі програми був організований лічильник часу її роботи. Час генерації простого (псевдопростого) числа було вихідним параметром програми, так само як саме число і кількість зайнятих їм біт. Програма, що реалізує будь-якої з описаних вище методів, запускалася не менше 25 разів на ПК з наступними параметрами: Toshiba Satellite L100-194 15 "XGA СМ-1700 / 256Мб DDRII ^ O ^ / DVD-RW / WiFi / WXPh. Час генерації усереднюються за всіма отриманими реалізацій.

    Результати роботи програм представлені на рис. 1 у вигляді залежностей часу генерації від числа біт. Особливістю залежностей 2-4 є їх флуктуірует характер. Амплітуда флуктуацій зменшується з ростом числа реалізацій, які використовуються при отриманні усередненої залежності (на одиничних реалізаціях амплітуда флуктуацій на порядок вище). Наявність флуктуацій обумовлено імовірнісним характером алгоритмів генерації простих чисел, що відповідають кривим 2-4. Подібні флуктуації відсутні на кривій 1, що відповідає детерминированному алгоритму пробних поділів.

    Як відомо [4], теоретична складність обчислень методу пробних поділів (крива 1) оцінюється співвідношенням

    N = О {4П), (5)

    де п - досліджуване число.

    s

    S я

    й Л <і К

    <і Л

    PQ

    10 9 8 76 5 '4 321

    100 200 300 400 500 600 700 800 900 1000 Розрядність числа, біт

    Мал. 1. Залежність часу генерації простого числа від кількості розрядів: 1 - методом пробного ділення; 2 - методом на основі тесту Міллера - Рабина; 3 - методом на основі малої теореми Ферма; 4 - методом на основі тесту Соловея - Штрассена;

    5 - теоретична оцінка складності обчислень

    У свою чергу теоретична складність обчислень методів на основі тесту Міллера - Рабина (2), малої теореми Ферма (3) і тесту Соловея - Штрассена (4) оцінюється як [5]

    N = O (log3 n) = O (k3

    -V- ,. (6)

    де до, - розрядність числа. Таким чином, обчислювальна складність у останніх трьох тестів не нижче, ніж у методу пробних поділів (О (^ 3 п) << О (п0 5)), що демонструється кривими на рис. 1. Висока обчислювальна складність методу пробних поділів робить його малопридатним для практичної реалізації.

    Крива 5 на рис. 1 описується залежністю N = 8,913 • 10 "9 к3 і відповідає теоретичної оцінки з обмежує постійної С = 8,913 • 10" 9, де експериментальна залежність була аппроксимирована теоретичної залежністю методом найменших квадратів. З порівняння цієї кривої з кривими 2-4 видно, що реалізовані програми генерації простих чисел з числом розрядів, що перевищує 900 біт, працюють трохи швидше, ніж передбачає теоретичну оцінку.

    4

    0

    висновок

    Таким чином, в роботі представлені алгоритми генерації великих простих чисел на основі методів пробного поділу, Міллера - Рабина, малої теореми Ферма, Соловея - Штрассена, безпосередньо придатні для програмної реалізації в середовищі Borland С ++ 3.1. Виконано чисельні розрахунки швидкості генерації від числа розрядів. Визначено нижня межа числа розрядів, що дорівнює 900 біт, починаючи з якої розроблені програми працюють швидше, ніж передбачає теоретичну оцінку складності обчислень.

    література

    1. Вельшенбах М. Криптографія на Сі і С ++ в дії / М. Вельшенбах. - М.: Тріумф, 2004. - 464 с.

    2. Смарт Н. Криптографія / Н. Смарт. - М.: Техносфера, 2005. - 528 с.

    3. Фергюсон Н., Шнайер Б. Практична криптографія / Н. Фергюсон, Б. Шнайер. -М. : Вільямс, 2005. - 424 с.

    4. Василенко О.М. Теоретико-числові алгоритми в криптографії / О.М. Василенко. -М. : МЦНМО, 2003. - 328 с.

    5. Черьомушкін А.В. Лекції по арифметичним алгоритмам в криптографії / А.В. Черьомушкін. - М.: МЦНМО, 2002. - 104 с.

    Кукало Іван Анатолійович

    Студент гр. 1А5 ТУСУРа Ел. пошта: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Міклін Павло Олександрович

    Доцент кафедри радіоелектроніки та захисту інформації ТУСУРа Ел. пошта: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Литвинов Рудольф Вікторович

    Канд. фіз.-мат. наук, доцент кафедри радіоелектроніки та захисту

    інформації ТУСУРа

    Ел. пошта: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    I.A. Kukalo, P.A. Miklin, R.V. Litvinov

    Algorithms of generation of the pseudo prime numbers in «Borland C ++ 3.1»

    The experimental investigation of the performance of the generation algorithms of the prime numbers has been carried out. These algorithms are based on the methods of trial divisions, Miller-Rabin, Soloway - Strassen and minor Fermat's theorem, using the filter of division into small prime number. For each type of the method the dependences of the time generation on the byte length have been plotted on the assumption of averaging of the large ensemble of partial realizations.


    Завантажити оригінал статті:

    Завантажити