Тема базові математичні основи криптографічних засобів захисту інформації



Download 157,5 Kb.
bet3/4
Sana25.04.2022
Hajmi157,5 Kb.
#581295
1   2   3   4
Bog'liq
ТЕМА 1

с = gcd (a, b).
Позначення gcd для найбільшого загального дільника походить від англійських слів greatest common divisor і є загальноприйнятним.
Приклад. gcd (10,15) = 5; gcd (8,28) = 4.
Для знаходження найбільшого спільного дільника використовують так званий алгоритм Евкліда.
Алгоритм Евкліда на псевдокоді виглядає так:
ВХІД: Позитивні цілі числа а, b , а > b.
ВИХІД: Найбільший спільний дільник gcd (a, b).
WHILE b  0 DO
r  a mod b
a  b
b  r
RETURN a
Тоді, для визначення взаємної простоти пари чисел можна скористатися тим, що числа a, b є взаємно простими, якщо gcd (a, b) = 1.
Завдання 5. Створіть програму gcd (a, b), яка знаходить і повертає НСД чисел а і b за алгоритмом Евкліда. Програму оформіть як функцію Python. Перевірка а > b на вході обовʼязкова, але сама функція повинна бути нечутливою до порядку аргументів при її виклику.
2.3. Зворотні числа по заданому модулю. Розширений (узагальнений) алгоритм Евкліда. Функція Ейлера.
Якщо цілі числа А та N взаємно прості, то тоді і тільки тоді (!) існує число А', таке, що (А*А') mod N = 1. Число А' називають зворотним до А по модулю N і використовують позначення А-1 (mod N). Обчислити А-1 можна, наприклад, скориставшись так званим розширеним (узагальненим) алгоритмом Евкліда.
Але в окремому випадку, тобто для реалізації алгоритмів компʼютерної криптографії, в яких необхідно знаходити зворотні числа по заданому модулю, значно простіше спиратися на властивості функції Ейлера.
Функція Ейлера  (N) визначена на множині натуральних чисел. Нехай дано ціле число N  1. Значення функції Ейлера  (N) дорівнює кількості чисел в ряду 1,2,3,...,N - 1, взаємно простих з N.
Мають місце такі властивості функції Ейлера:
1) якщо N – просте число, то
 (N) = N – 1;

2) якщо N і М – прості числа, такі, що N М, N < М, то


 (N*М) = (N – 1)*( М – 1).
Через функцію Ейлера  (N) зворотне число А-1 по заданому модулю N обчислюється дуже просто:
А-1 = А (N) – 1 mod N.
Завдання 6. Напишіть функцію Python euler (N), яка повертає значення кількості чисел в ряду 1,2,3,...,N - 1, взаємно простих з N, для довільних натуральних (не тільки простих) чисел N.
Завдання 7. Напишіть функцію Python inverse (А, N), яка повертає значення зворотного числа А-1 , використовуючи формулу А-1 = А (N) – 1 mod N. Перед обчисленням функція inverse (А, N), повинна перевірити взаємну простоту А та N. Для цього можна скористатися функцією gcd ( ) із Завдання 2.2.
2.4. Дискретний логарифм. Первісні корені.
Формально дискретний логарифм можна визначити наступним чином.
Спочатку визначимо первісний корінь простого числа N (інакше – породжуючий елемент або генератор скінченної циклічної групи порядка N) як таке число , ступені якого породжують усі цілі числа від 1 до N – 1.
Це означає, що якщо є первісним коренем простого числа N, то усі числа
1 mod N,  2 mod N, ... ,  (N-1) mod N
будуть різними і представлятимуть усі цілі числа від 1 до N – 1 в деякій перестановці.
Для будь-якого цілого числа b і будь-якого первісного кореня простого числа N однозначно визначається показник ступеня i, при якому
b =  i mod N , де 0 < i < (N – 1).
Цей показник ступеня i називається дискретним логарифмом, або індексом b за основою по модулю N, що може записуватися також у формі ind ,N (b).
Приклади.
Якщо N = 7, то при цьому первісними корінями будуть такі:
3, 5.
А якщо N = 23, то при цьому первісними корінями будуть такі:
5, 7, 10, 11, 14, 15
Переконаймося, що число 3 є первісним коренем за модулем N = 7. Для цього достатньо кожне число від 1 до 6 представити як певну ступінь 3 за модулем N = 7:
30 = 1 (mod 7)
31 = 3 (mod 7)
32 = 2 (mod 7)
33 = 6 (mod 7)
34 = 4 (mоd 7)
З5 = 5 (mod 7)
Отримані числа 1, 3, 2, 6, 4, 5 являють собою перестановку чисел натурального ряду 1, 2, 3, 4, 5, 6.
Для довідки наведемо таблицю перших первісних коренів простих чисел N < 1000, узяту за адресою www.intuit.ru/studies/courses/553/409/lecture/17867:


Download 157,5 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish