Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Питання
Предмет:
Алгоритмічні основи криптології
Частина тексту файла (без зображень, графіків і формул):
Алгоритмічні основи криптології
1 рівень
Означення найбільшого спільного дільника.
Число d Z, що ділиться одночасно на числа а, b, c, ... , k Z, називається спільним дільником цих чисел. Найбільше d з такою властивістю називається найбільшим спільним дільником. Позначення: d = (a, b, c, ..., k). Перелічимо, подекуди доводячи, основні властивості найбільшого спільного дільника.
Які числа називаються взаємно простими.
Цілі числа a і b називаються взаємно простими, якщо НСД( a , b ) = 1.
Означення ланцюгового дробу.
Ланцюговий (чи неперервним ) дробом називається вираз виду:
EMBED Equation.3
Домовимося називати числа q 1 , q 2 ,..., q n ,... - неповними частками і вважаємо, що q 1 Z, а q 2 ,..., q n ,... N . Числа
1 = q 1 , 2 = q 1 +EMBED Equation.3, 3 = q 1 +EMBED Equation.3, і т.д.
називаються прямуючими дробами ланцюгового дробу .
Алгоритм Евкліда.
Алгоритм, що дозволяє за заданими натуральними числами a і b знаходити їхній найбільший спільний дільник, вважається придумав самий впливовий математик усіх часів і народів - Евклід, він викладений у IX книзі його знаменитих "Початків".
Означення простого числа.
Число р N , р 1, називається простим, якщо р має лише два додатних дільники: 1 і р.
Коли алгоритм Евкліда працює найдовше?
Теорема (Ламе, 1845 р.). Нехай n N , і нехай a>b>0 такі, що алгоритму Евкліда для обробки а і b необхідно виконати точно n кроків (розподілів із залишком), причому а - найменше з такою властивістю. Тоді а=n +2 , b =n +1 , де k - k- те число Фібоначчі.
Ну от, використовуючи теорему Ламе, ми провели деякий аналіз швидкодії алгоритму Евкліда і довідалися найгірший випадок для нього - два послідовних числа Фібоначчі.
Означення числа порівняльного за модулем.
Нехай а, b Z , m N. Число а порівняльне з b за модулем m, якщо а і b при діленні на m мають однакові залишки: a b(mod m) .
Означення числа порівняльного за модулем.
Нехай а, b Z , m N. Число а порівняльне з b за модулем m, якщо а і b при діленні на m мають однакові залишки: a b(mod m) .
Означення повної системи лишків.
Сукупність лишків, узятих по одному з кожного класу еквівалентності m, називається повною системою лишків за модулем m (у повній системі лишків усього m чисел). Безпосередньо самі залишки ділення на m називаються найменшими невід’ємними лишками і утворюють повну систему лишків за модулем m.
Означення зведеної системи лишків.
Зведеною системою лишків за модулем m називається сукупність усіх лишків з повної системи, взаємно простих з модулем m.
Що означає розв’язати порівняння?
Розв’язати порівняння – означає знайти всі ті х, що задовольняють даному порівнянню, при цьому весь клас чисел за mod m вважається одним розв’язком.
Скільки розв’язків має порівняння за простим модулем p?
Довільне нетривіальне порівняння за mod p рівносильне порівнянню степеня не вищого за p-1 і має не більше p-1 розв’язків.
Які порівняння називаються рівносильними?
Порівняння називаються рівносильними, якщо вони мають однакові розв’язки – повна аналогія з поняттям рівносильності рівнянь.
Наведіть функцію знаходження кількості дільників даного числа.
Наведіть функцію знаходження суми дільників даного числа.
Означення алгоритму.
Слово "алгоритм" є російською транскрипцією латинізованого імені видатного арабського математика ал-Хорезми Абу Абдули Мухаммеда ібн ал-Маджусі (787 - 850) і означає в сучасному смислі деякі правила, список інструкцій чи команд, виконуючи які, хтось досягне необхідного результату.
Чи можна розкласти довільне ціле число відмінне від -1, 0, 1 за допомогою добутку простих чисел?
Усяке ціле число, відмінне від -1, 0 і 1, єдиним чином (з точністю до порядку співмножників) розкладається за допомогою добутку простих чисел.
2 рівень
Типи задач в теорії алгоритмів. Наведіть характеристики.
Діофантові рівняння. Частковий та повний розв’язок.
Звичайно, довільне рівняння (але, як правило, усе-таки з цілими коефіцієнтами) одержує титул "діофантове", якщо хочуть підкреслити, що його потрібно вирішити в цілих числах, тобто знайти всього його розв’язки, що є цілими
Нехай потрібно розв’язати лінійне діофантове рівняння:
ax + by = c ,
де a , b , c Z ; a і b - не нулі.
Спробуємо помислити, дивлячись на це рівняння.
Нехай ( a , b ) = d . Тоді a = a 1 d ; b = b 1 d і рівняння виглядає так:
a 1 d· x + b 1 d· y = c , тобто d· ( a 1 x + b 1 y ) = c .
Тепер зрозуміло, що в такого рівняння є розв’язок (пари цілих чисел x і y ) тільки тоді, коли d | c . Оскільки дуже хочеться розв’язувати це рівняння далі, то нехай d | c . Поділимо обидві частини рівняння на d, і далі будемо вважати, що ( a , b ) = 1.
Розглянемо кілька випадків.
Випадок 1. Нехай c = 0, рівняння має вид ax + by = 0 - " однорідне лінійне діофантове рівняння". Знаходимо, що
x = b / a * y
Оскільки x має бути цілим числом, то y = at , де t - довільне ціле число (параметр). Значить x = - bt і розв’язками однорідного діофантового рівняння ax + by = 0 є усі пари виду {- bt , at }, де t = 0; ±1; ±2;... Множина усіх таких пар називається загальним розв’язком лінійного однорідного діофантового рівняння, будь-яка ж конкретна пара з цієї множини називається частковим розв’язком.
Випадок 2. Нехай тепер c 0. Цей випадок закривається наступною теоремою.
Теорема. Нехай ( a , b ) = 1, { x 0 , y 0 } - частковий розв’язок діофантового рівняння ax + by = c . Тоді його загальний розв’язок задається формулами:
EMBED Equation.2
Таким чином, в теорії лінійних діофантових рівнянь загальний розв’язок неоднорідного рівняння є сумою загального розв’язку відповідного однорідного рівняння і якогось (кожного) часткового розв’язку неоднорідного рівняння.
Доказ. Те, що праві частини зазначених у формулюванні теореми рівностей дійсно є розв’язками, перевіряється їх безпосередньою підстановкою у вихідне рівняння. Покажемо, що будь-який розв’язок рівняння ax + by = c має саме такий вид, який зазначений у формулюванні теореми. Нехай { x * , y *} - який-небудь розв’язок рівняння ax + by = c . Тоді ax * + by * = c , але і ax 0 + by 0 = c . Віднімемо від першої рівності другу й одержимо:
a ( x *- x 0 ) + b ( y *- y 0 ) = 0
- однорідне рівняння. Далі, дивлячись на випадок 1, пишемо відразу загальний розв’язок: x *- x 0 = - bt , y *- y 0 = at , звідки одержуємо:
EMBED Equation.2
Як же шукати саме частковий розв’язок { x 0 , y 0 }. Ми домовилися, що ( a , b ) = 1. Це означає, що знайдуться такі u і v з Z , що au + bv = 1 (пункт 4), причому ці u і v знаходимо за допомогою алгоритму Евкліда. Помножимо тепер рівність au + bv = 1 на c і одержимо: a ( uc ) + b ( vc ) = c , тобто x 0 = uc , y 0 = vc .
Обчислення прямуючих дробів.
Проспостерігаємо за поведінкою прямуючих дробів
1 = q 1 , 2 = q 1 + EMBED Equation.3, 3 = q 1 + EMBED Equation.3, ...
ланцюгового дробу
EMBED Equation.3
з метою навчитися швидко їх обчислювати без перетворення багатоповерхових виразів.
Прямуючий дріб s , s > 1, одержуємо із дробу s -1 заміною в записі виразу s -1 букви q s -1 виразом q s -1 + 1/ q s . Ми вже знаємо з пункту 7, що якщо "багатоповерховий" прямуючий дріб спростити (порахувати), то вийде деяке раціональне число P/Q - "одноповерховий" дріб. Домовимося завжди буквою Ps позначати чисельник придатної дробу s (чисельник його раціонального значення, тобто "одноповерхового" дробу), а буквою Q s - знаменник.
Приймемо для зручності P 0 = 1, Q 0 = 0. (Це просто угода, на нуль ділити не потрібно.) Маємо:
EMBED Equation.3
EMBED Equation.3, тобто P 1 = q 1 , Q 1 = 1,
EMBED Equation.3,
EMBED Equation.3 і т.д.
Видно, що виходять рекурентні співвідношення:
P s = q s P s -1 + P s -2 - чисельники
Q s = q s Q s -1 + Q s -2 - знаменники
Ці співвідношення разом з початковими умовами P 0 = 1, Q 0 = 0, P 1 = q 1 , Q 1 = 1 значно прискорюють процес обчислення прямуючих дробів. Самі співвідношення дуже легко довести, якщо скористатися принципом математичної індукції.
Теорема Ейлера. Застосування.
Теорема (Ейлер). Нехай m>1, (a,m)=1, (m) – функція Ейлера. Тоді:
a(m) 1(mod m).
Доказ. Нехай х набуває значення із зведеної системи лишків за mod m:
x=r1,r2,...,rc
де c=(m) їх кількість, r1,r2,..., rc - найменші невід’ємні лишки за mod m. Отже, найменші невід’ємні лишки, що відповідають числам ax є відповідно:
1 , 2 ,..., c
– теж набувають значень із зведеної системи лишків, але в іншому порядку (див. Лему 2 з пункту 17). Значить:
a r1 (mod m)
a r2 (mod m)
...
a rc (mod m)
Перемножимо ці с порівнянь. Вийде:
ac r1 r2 ...rc j 1 j 2 ... j c (mod m)
Оскільки r1 r2 ...rc = 1 2 ... c 0 і взаємно просте з модулем m, то, поділивши останнє порівняння на r1 r2 ...rc, одержимо a(m) 1(mod m).
Друга теорема цього пункту - теорема Ферма – є безпосереднім наслідком теореми Ейлера.
Приклад 1. Дев'ятий ступінь однозначного числа закінчується на 7. Знайти це число.
Розв’язування. a9 7(mod 10) – дано. Крім того, (7, 10)=1 і ( a , 10)=1. За теоремою Ейлера, a(10) 1(mod 10). Отже, a4 1(mod 10) і, після піднесення до квадрату, a8 1(mod 10). Поділимо почленно a9 7(mod 10) на a8 1(mod 10) і одержимо a7(mod 10). Це означає, що a=7.
Теорема Ферма. Застосування.
Теорема (Ферма). Нехай р – просте число, р не ділить a. Тоді:
ap-1 1(mod p) .
Доказ 1. Нехай в умові теореми Ейлера m=p, тоді (m)=p-1 (див. пункт 14 ). Одержуємо ap-1 1(mod p).
Необхідно відзначити важливість умови взаємної простоти модуля і числа a у формулюваннях теорем Ейлера і Ферма. Простий приклад: порівняння 62 1(mod 3) очевидно не виконується. Однак можна легко підправити формулювання теореми Ферма, щоб зняти обмеження взаємної простоти.
Наслідок 1. Без всяких обмежень на a Z,
ap a(mod p) .
Доказ. Помножимо обидві частини порівняння ap-1 1(mod p) на a. Зрозуміло, що вийде порівняння, справедливе і при a, кратному р.
Звичайно, доказ 1 теореми Ферма вийшов настільки коротким завдяки проведеній могутній попередній підготовці (доведена теорема Ейлера і вивчені властивості функції (m)). Наведемо ще один варіант доказу теореми Ферма.
Доказ 2. Оскільки р - просте число, то всі біноміальні коефіцієнти (крім C0p і Cpp) діляться на р, тому що чисельник виписаного виразу містить р, а знаменник не містить цього множника. Якщо згадати біном Ньютона, то стає зрозуміло, що різниця (A+B)p-Ap -Bp= =Cp1Ap-1B1+Cp2Ap-2B2+...+Cpp-2A2Bp-2+Cpp-1A1Bp-1, де А і В – довільні цілі числа, завжди ділиться на р. Послідовним застосуванням цього спостереження одержуємо, що (A+B+C)p--Ap-Bp-Cp={[(A+B)+C]p-(A+B)p-Cp}+(A+B)p -Ap -Bp завжди ділиться на р; (A+B+C+D)p-Ap–Bp -Cp-Dp завжди ділиться на р; і взагалі, (A+B+C+...+K)p -Ap-Bp-Cp-...-Kp завжди ділиться на р. Нехай A=B=C=...=K=1 і візьмемо кількість цих чисел рівним a. Вийде, що ap-a ділиться на р, а це і є теорема Ферма в більш загальному формулюванні.
Наслідок 2. (a+b)p ap +bp (mod p).
Наведемо кілька прикладів застосування теорем Ферма і Ейлера. Зазначимо, що ефективність застосування теорем Ферма і Ейлера ґрунтується на тому, що порівняння, що даються цими теоремами, зручно підносити до степеня, оскільки справа у них стоїть одиниця, що на піднесення до степеня не реагує.
Приклад 3. Знайти залишок ділення 7402 на 101.
Рішення. Число 101 – просте, (7, 101)=1, отже, за теоремою Ферма: 71001(mod 101). Піднесемо це порівняння до четвертої степені: 74001(mod 101), домножимо його на очевидне порівняння 7249(mod 101), одержимо: 740249(mod 101). Виходить, що залишок ділення 7402 на 101 дорівнює 49.
Розв’язування порівнянь першого степеня вигляду axb(mod m) для взаємно простих a і m.
Нехай а і m взаємно прості. Тоді нескоротний дріб m/a розкладається в ланцюговий дріб:
EMBED Equation.3
Цей ланцюговий дріб, зрозуміло, скінченний, тому що m/a - раціональне число. Розглянемо два останні прямуючі дроби:
EMBED Equation.3INCLUDEPICTURE "../../../pict/19-002.gif" \* MERGEFORMAT \d \z"; EMBED Equation.3
Згадуємо (пункт 9) властивість чисельників і знаменників прямуючих дробів: mn-1-an-1=
=(-1)n. Далі (доданок mn-1, кратний m, можна викинути з лівої частини порівняння):
-an-1 (-1)n (mod m) тобто
an-1 (-1)n-1 (mod m) тобто
a[(-1)n-1 Pn-1 b] b(mod m)
і єдиним розв’язком вихідного порівняння є:
x (-1)n-1 Pn-1 b(mod m)
Китайська теорема про лишки.
Лема 1 (Китайська теорема про лишки). Нехай дана найпростіша система порівнянь першого степеня:
EMBED Equation.3 (*)INCLUDEPICTURE "../../../pict/19-009.gif" \* MERGEFORMAT \d \z"
де m1,m2,...,mk попарно взаємно прості. Нехай, m1 m2 ...mk =Ms ms; Ms Ms1(mod ms) (Очевидно, що таке число Msзавжди можна підібрати хоча б за допомогою алгоритму Евкліда, оскільки (ms, Ms )=1); x0 =M1 M1b1+M2 M2b2 +...+Mk Mkbk. Тоді система (*) рівносильна одному порівнянню
x x0 (mod m1 m2 ...mk ),
а саме набір розв’язків (*) збігається з набором розв’язків порівняння xx0(mod m1m2 ...mk).
Доказ. Маємо: ms ділить Mj, при sj. Отже, x0 Ms Msbs (mod ms), звідки x0bs(mod ms). Це означає, що система (*) рівносильна системі
EMBED Equation.3INCLUDEPICTURE "../../../pict/19-010.gif" \* MERGEFORMAT \d \z"
яка, у свою чергу, рівносильна одному порівнянню xx0 (mod m1 m2 ...mk ).
Зведення розв’язування порівняння високого степеня до розв’язування порівняння меншого степеня.
Зведемо розв’язування порівняння f(x)0(mod pa) до розв’язування порівняння g(x)0(mod p).
Процес зведення.
Очевидно, що з виконання порівняння f(x)0(mod pa) випливає те, що х підходить у порівняння f(x)0(mod p). Нехай xx1(mod p) – який-небудь розв’язок порівняння f(x)0(mod p). Це означає, що
x = x1 + p t1, де t1 Z.
Підставимо це х у порівняння f(x)0(mod p2). Одержимо порівняння
f(x1+pt1)0(mod p2),
яке теж, мабуть, виконується.
Розкладемо далі ліву частину отриманого порівняння за формулою Тейлора за степенями (х - х1):
EMBED Equation.3INCLUDEPICTURE "../../../pict/21-004.gif" \* MERGEFORMAT \d \z"
Оскільки x=x1+pt1, то
EMBED Equation.3INCLUDEPICTURE "../../../pict/21-005.gif" \* MERGEFORMAT \d \z".
Зауважимо, що число f(k)(x1)/ k! завжди ціле, бо f(x1+pt1) – многочлен з цілими коефіцієнтами. Тепер у порівнянні
f(x1+pt1)0(mod p2)
можна зліва відкинути члени, кратні р2:
EMBED Equation.3INCLUDEPICTURE "../../../pict/21-006.gif" \* MERGEFORMAT \d \z".
Розділимо останнє порівняння і його модуль на р:
EMBED Equation.3INCLUDEPICTURE "../../../pict/21-007.gif" \* MERGEFORMAT \d \z".
Зауважимо знову, що f(x1)/ p – ціле число, тому що f(x1)0(mod p). Далі обмежимося випадком, коли значення похідної f(x1) не ділиться на р. У цьому випадку існує єдиний розв’язок порівняння першого степеня
EMBED Equation.3 INCLUDEPICTURE "../../../pict/21-007.gif" \* MERGEFORMAT \d \z"відносно t1: t1t1(mod p).
Це означає, що t1=t1+pt2, де t2 Z, і
EMBED Equation.3INCLUDEPICTURE "../../../pict/21-008.gif" \* MERGEFORMAT \d \z".
Підставимо це x=x2 +p2t2 у порівняння f(x)0(mod p3) (але тепер це порівняння за mod p3), розкладемо його ліву частину за формулою Тейлора за степенями (х-х2) і відкинемо члени, кратні p3:
f(x2)+(f(x2)/1!)p2t2 0(mod p3).
Поділимо це порівняння і його модуль на р2:
f(x2)/p2+f(x2)t20(mod p).
Знову ж f(x2)/p2 – ціле число, адже число t1таке, що f(x1+pt1)0(mod p2). Крім того, x2x1(mod p), значить f(x2)f(x1)(mod p), тобто f(x2), як і f(x1), не ділиться на р. Маємо єдиний розв’язок порівняння першого степеня f(x2)/p2+f(x2)t2)0(mod p) відносно t2:
t2t2(mod p).
Це означає, що t2= t2+pt3, де t3Z, і
EMBED Equation.3INCLUDEPICTURE "../../../pict/21-009.gif" \* MERGEFORMAT \d \z"
і процес продовжується далі, аналогічно попереднім крокам, до досягнення степеня pa, у якому стоїть просте число р у модулі вихідного порівняння f(x)0(mod pa).
Отже:
Всякий розв’язок xx1(mod p) порівняння f(x)0(mod p), за умови p/f(x1), дає один розв’язок порівняння f(x)0(mod pa) виду xxa+pata, тобто xxa(mod pa).
3 рівень
Знайти максимальну та мінімальну складність обчислення функції F(x)=x6-x4+x2.
E = x6 – x4 + x2
Максимальна складність:
Z1 = x x;
Z2 = Z1 x;
Z3 = Z2 x;
Z4 = Z3 x;
Z5 = Z4 x;
Z6 = Z5 – Z3;
Z7 = Z6 + Z1 Складність = 7
Мінімальна складність:
Z1 = x x;
Z2 = Z1 – 1;
Z3 = Z1 Z2;
Z4 = Z3 + 1;
Z5 = Z4 Z1 Складність=5
Написати програму мовою Сі, що реалізує функцію піднесення до степеня f(x)=xd бінарним методом.
Програма:
#include <stdio.h>
#include <math.h>
#include <conio.h>
void main(void)
{
unsigned long x, d, m=1, z=1;
clrscr();
printf("Vvedit chyslo x:");
scanf("%ld", &x);
printf("Vvedit stepin d:");
scanf("%ld", &d);
while (m<=d) m <<= 1;
m >>= 1;
while (m>1)
{
if ((d & m) == 0)
z=z*z;
else
z=pow(z*x, 2);
m >>= 1;
}
if ((d & 1) != 0) z*=x;
printf("\nx^d = %ld", z);
getch();
}
Написати програму мовою Сі, що будує таблицю простих чисел за допомогою решета Ератосфена.
Програма:
#include<stdio.h>
#include<conio.h>
#define n 10
void main(void)
{
int i, j, a[n];
clrscr();
for(i=2;i<n;i++) a[i]=1;
for(i=2;i<n;i++)
{
if (a[i]==1)
{
for(j=i;j*i<n;j++) a[i*j]=0;
}
}
printf("1\n");
for(i=2;i<n;i++)
{
if (a[i]==1) printf("%d\n",i);
if (i%23==0) getch();
}
getch();
}
Розкласти в ланцюговий дріб число =5391/3976. Обчислити перші п’ять прямуючих дробів.
EMBED Equation.3
За алгоритмом Евкліда:
5391 = 39761 + 1415 (q1 = 1)
3976 = 14152 + 1146 (q2 = 2)
1415 = 11461 + 269 (q3 = 1)
1146 = 2694 + 70 (q4 = 4)
269 = 703 + 59 (q5 = 3)
70 = 591 + 11 (q6 = 1)
59 = 115 + 4 (q7 = 1)
5 = 41 + 1 (q8 = 1)
4 = 14
EMBED Equation.3
Прямуючі дроби обчислюємо за формулою:
EMBED Equation.3
де Ps = qs Ps – 1 + Ps – 2
Qs = qs Qs – 1 + Qs –2
Крім того, використовуємо умову:
P0 = Q0 = 1
Перші п’ять прямуючих дробів:
0 =
1 = 1/1 = 1
2 = 3/2 = 1,5
3 = 4/3 = 1,33
4 = 19/14 = 1,357
5 = 61/45 = 1,355
EMBED Equation.3
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора