4.2. Рекомендації до опрацьовування тем 4-7 розділу 2 Теоретико-числові обчислювальні алгоритми

В цьому розділі розглядаються алгоритми теорії чисел, що мають безпосереднє відношення до практичної криптографії.

В темі 4. Розв’язування алгебраїчних конгруенцій розглядаються способи розв’язування алгебраїчних конгруенцій -го степеня за простим та за складеним модулем.

Детально розглядається задача пошуку розв’язання квадратної двочленної конгруенції за простим непарним модулем у випадках , . Для розв’язання цієї задачі застосовується апроксимаційний (наближувальний) алгоритм. Але для цих випадків більш ефективним, ніж апроксимаційний алгоритм, є алгоритм добування квадратного кореня Шенкса-Тонеллі (Shanks-Tonelli), який і розглядається детально.

Основну увагу при вивченні цієї теми треба приділити відпрацюванню способів розв’язування, а також методам спрощення алгебраїчних конгруенцій -го степеня.

Також в цій темі розглядається алгоритм Берлекемпа розкладання многочлена на незвідні множники над скінченним полем, ідея якого ґрунтується на китайській теоремі про остачі для многочленів.

Рекомендована навчальна література: [1], [5], [8], [11], [18],[21].

Діапазон чисел, які використовуються в реальних задачах криптографії, доходить до декількох сотень і навіть тисячі десяткових цифр. Такий діапазон чисел не відповідає базовим типам даних сучасних комп'ютерів. Число, яке складається з декілька сотень (і навіть тисяч) десяткових знаків, не можна записати як єдиний об'єкт ні в один базовий пристрій комп'ютера. Тому комп'ютерне представлення таких чисел і операції над ними доводиться реалізовувати самостійно у вигляді деяких спеціальних програм.

В темі 5 Арифметичні алгоритми багатократної точності формулюються основні алгоритми для виконання арифметичних операцій з великими цілими невід’ємними числами (або, інакше, чисел з довільною кількістю розрядів).

Рекомендована навчальна література: [1], [11].

В темі 6 Розв’язування систем лінійних алгебраїчних рівнянь над скінченними полями розглядаються алгоритми розв’язування системи лінійних алгебраїчних рівнянь над кільцем цілих чисел. За суттю ці алгоритми є узагальненнями алгоритму Евкліда.

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

Рекомендована навчальна література: [1], [11].

В темі 7 Алгоритми на еліптичних кривих розглядаються деякі основні властивості еліптичних кривих і їх алгоритмічні застосування в теорії чисел.

Задача обчислення порядку групи точок на еліптичній кривій над скінченним простим полем має важливі застосування як в криптографії, так і в алгоритмах перевірки простоти чисел. Безпека криптосистем, побудованих на еліптичних кривих, заснована на складності обчислення дискретного логарифма в групі точок на еліптичних кривих. Складність логарифмування в групі точок на еліптичній кривій оцінюється квадратним коренем з найбільшого простого дільника порядку цієї групи. Тому в питаннях безпеки криптосистем на еліптичних кривих важливо знати порядок групи і навіть його розкладання на множники.

Також в цій темі розглядається задача знаходження точки еліптичної кривої над полем .

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

Рекомендована навчальна література: [1], [11], [20].