Лабораторна робота №3
Відповідальний за випуск:__________________________________________. Рецензенти:_______________________________________ __________________________________________________________.
Лабораторна робота №1 Тема: Бінарний метод піднесення до степеня Мета: Навчитися реалізовувати та використовувати бінарний метод піднесення до степеня
Теоретичні відомості. Однією з задач, що найчастіше зустрічаюся при реалізації різноманітних криптоалгоритмів, є задача піднесення деякого числа до певного степеня, тобто обчислення значення функції f(x)= x , зокрема піднесення до степеня за деяким модулем n - . Прямолінійний алгоритм (він буде експоненційним) потребує значних обчислювальних затрат. Проте відомо набагато ощадливіший алгоритм, котрий називається бінарний метод піднесення до степеня. Нехай нам задано: . Потрібно знайти . Подамо показник d в двійковій системі числення, тобто , де . Алгоритм буде складатись з l+1 команд. Спочатку покладаємо zo=l. Тоді і-та команда задається так:
Результатом виконання останньої є значення . Завдання. 1. Програмно реалізувати бінарний метод піднесення до степеня. 2. Обчислити значення
Лабораторна робота №2 Тема:Обчислення первісних коренів Мета: Навчитися обчислювати первісні корені
Теоретичні відомості. Нехай р - натуральне число. Ціле число g називається первісним коренем за модулем р, якщо лишок є твірним елементом групи Zp *. Первісні корені існують для всіх простих модулів. Як легко зрозуміти, g є первісним коренем за простим модулем р, якщо послідовність g° modp =1, g1 modp, g2 modp,...,gp-2 modp містить всі елементи множини Zp*. Нехай задано розклад на прості множники числа .Тоді g є первісним коренем тоді і тільки тоді, коли для всіх виконується умова .
Завдання. 1. Програмно реалізувати процедуру знаходження первісного кореня за простим модулем. 2. Знайти всі первісні корені за модулем 11.
Лабораторна робота №3 Тема: Визначення квадратичних лишків Мета: Навчитися визначати квадратичні лишки
Теоретичні відомості. Нехай n - натуральне число. Ціле х називається квадратичним лишком за модулем n, якщо НСД(х,п)=1 і для деякого у. В цьому разі у називається квадратичним коренем з х за модулем n. Якщо НСД(х,п)=1 і х не є квадратичним лишком за модулем n, то х називається квадратичним нелишком за цим модулем. Множину зведених квадратичних лишків позначають . Важливою є лема: Нехай р — непарне просте число. Тоді такі умови еквівалентні: 1) х є квадратичним лишком за модулем р. 2) 3) якщо - первісний корінь за модулем р, то для деякого парного k в виконується рівність .
Завдання. 1. Програмно реалізувати процедуру визначення квадратичних лишків. 2. Знайти всі квадратичні лишки та нелишки за модулем 13.
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|