Главная | Обратная связь

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

Відповідальний

за випуск:__________________________________________.

Рецензенти:_______________________________________

__________________________________________________________.

 

Лабораторна робота №1

Тема: Бінарний метод піднесення до степеня

Мета: Навчитися реалізовувати та використовувати бінарний метод піднесення до степеня

 

Теоретичні відомості.

Однією з задач, що найчастіше зустрічаюся при реалізації різноманітних криптоалгоритмів, є задача піднесення деякого числа до певного степеня, тобто обчислення значення функції f(x)= x , зокрема піднесення до степеня за деяким модулем n - . Прямолінійний алгоритм (він буде експоненційним) потребує значних обчислювальних затрат. Проте відомо набагато ощадливіший алгоритм, котрий називається бінарний метод піднесення до степеня.

Нехай нам задано: . Потрібно знайти .

Подамо показник d в двійковій системі числення, тобто

, де .

Алгоритм буде складатись з l+1 команд. Спочатку покладаємо z_o=l. Тоді і-та команда задається так:

Результатом виконання останньої є значення .

Завдання.

1. Програмно реалізувати бінарний метод піднесення до степеня.

2. Обчислити значення

 

Лабораторна робота №2

Тема:Обчислення первісних коренів

Мета: Навчитися обчислювати первісні корені

 

Теоретичні відомості.

Нехай р - натуральне число. Ціле число g називається первісним коренем за модулем р, якщо лишок є твірним елементом групи Z_p *. Первісні корені існують для всіх простих модулів. Як легко зрозуміти, g є первісним коренем за простим модулем р, якщо послідовність g° modp =1, g¹ modp, g² modp,...,g^p-2 modp містить всі елементи множини Z_p*. Нехай задано розклад на прості множники числа .Тоді g є первісним коренем тоді і тільки тоді, коли для всіх виконується умова .

 

Завдання.

1. Програмно реалізувати процедуру знаходження первісного кореня за простим модулем.

2. Знайти всі первісні корені за модулем 11.

 

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

Тема: Визначення квадратичних лишків

Мета: Навчитися визначати квадратичні лишки

 

Теоретичні відомості.

Нехай n - натуральне число. Ціле х називається квадратичним лишком за модулем n, якщо НСД(х,п)=1 і для деякого у. В цьому разі у називається квадратичним коренем з х за модулем n. Якщо НСД(х,п)=1 і х не є квадратичним лишком за модулем n, то х називається квадратичним нелишком за цим модулем. Множину зведених квадратичних лишків позначають .

Важливою є лема:

Нехай р — непарне просте число. Тоді такі умови еквівалентні:

1) х є квадратичним лишком за модулем р.

2)

3) якщо - первісний корінь за модулем р, то для деякого парного k в виконується рівність .

 

Завдання.

1. Програмно реалізувати процедуру визначення квадратичних лишків.

2. Знайти всі квадратичні лишки та нелишки за модулем 13.