с = 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:
Do'stlaringiz bilan baham: |