Алгоритмічні основи криптології. Інші з Інші. Робота № 300174

Перехід до торгівельного партнера Binance

Алгоритмічні основи криптології

Інформація про навчальний заклад

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2024

Тип роботи:

Інші

Предмет:

Інші

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Алгоритмічні основи криптології І Рівень 1. Означення найбільшого спільного дільника. Визначення. Число d Z, що ділиться одночасно на числа а, b, c, ... , k Z, називається спільним дільником цих чисел. Найбільше d з такою властивістю називається найбільшим спільним дільником. Позначення: d = (a, b, c, ..., k). Перелічимо, подекуди доводячи, основні властивості найбільшого спільного дільника. Теорема (Властивість 1) . Якщо (a, b) = d, то знайдуться такі цілі числа u і v, що d=au+bv. Доказ . Розглянемо множину P = { au + bv u,v Z }. Очевидно, що P Z , причому P – ідеал у Z. Очевидно, що a, b, 0 P. Нехай x, y P і y 0. Тоді залишок ділення x на y належить P. Дійсно: x = yq + r, 0 r < y, r = x – yq = (au1 + bv1) – (au2+bv2) q=a ( u1 – u2 q)+ b (v1–v2q) P. Нехай d P - найменше додатне число з P (задумайтеся, чому таке існує!). Тоді а ділиться на d. Справді, a=dq+r1, 0 r1< d, a P, d P, значить r1P, отже r1=0. Аналогічно одержуємо, що b ділиться на d, отже d - спільний дільник a і b. Оскільки d P, то d = au0+ bv0. Якщо тепер d1 - спільний дільник a і b, то d1 | (au0+bv0), тобто d1| d. Значить d d1 і d - найбільший спільний дільник. Властивість 2 . Для будь-яких цілих чисел а і k справедливо: ( а , kа ) = а ; (1, а ) = 1. Властивість 3 . Якщо a = bq + c , то сукупність спільних дільників a і b збігається із сукупністю спільних дільників b і c , зокрема, ( a , b ) = ( b , c ). Доказ. Нехай d | a , d | b , тоді d | c . Нехай d | c , d | b , тоді d | a . Проілюструємо цей доказ на давньогрецький лад. Подивіться на рис. 2: Рис. 2 Якщо d ціле число разів укладається в а і в b , то, очевидно, що d мусить ціле число разів укластися й у с. Властивість 4 . Нехай a , b і m - довільні цілі числа. Тоді ( am , bm ) = m ( a , b ). Доказ. Якщо d - найбільший спільний дільник чисел а і b , то dm | am і dm | bm , тобто dm - дільник am і bm . Покажемо, що dm - найбільший спільний дільник цих чисел. Оскільки d - найбільший спільний дільник чисел а і b , то, відповідно до властивості 1, для деяких цілих чисел u і v виконується рівність d = au + bv. Помноживши цю рівність на m, одержимо: dm = amu + bmv . Видно, що якщо деяке число s ділиться одночасно на am і bm , то s має ділитися і на dm , тобто s dm , отже, dm - найбільший спільний дільник. Властивість 5 . Нехай s - дільник а і b . Тоді: (a/s,b/s)=(a,b)/s Доказ . (a,b)=(a/s*s,b/s*s)=s(a/s,b/s) Властивість 6 . Очевидно тепер, що (a/(a,b),b/(a,b))=1 Властивість 7 . Якщо ( a , b ) = 1, то ( ac , b ) = ( c , b ). Доказ . Нехай ( c, b ) = d . Маємо: d | b , d | c , отже d | ac , тобто d - дільник ас і b . Нехай тепер ( ac , b ) = s . Маємо: s | b , s | ac , s - дільник b , тобто або s = 1, або s не ділиться на а . Це означає, що s | c , значить s | d . Отже, d і s поділяються один на одного, тобто d = s. 2. Які числа називаються взаємно простими. Цілі числа a і b називаються взаємно простими, якщо ( a , b ) = 1. Згадуючи властивість 1 з попереднього пункту, легко помітити, що два числа a і b є взаємно простими тоді і тільки тоді, коли знайдуться цілі числа u і v такі, що au + bv = 1. 3. Означення ланцюгового дробу. Ланцюговий (чи неперервним ) дробом називається вираз виду: 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, і т.д. називаються прямуючими дробами ланцюгового дробу . Ланцюговий дріб може бути кінцевим (має скінченне число дробових ліній і неповних часток), так і нескінченним вниз і вправо. У першому випадку дріб є деяким раціональним числом, у другому - поки незрозуміло чим дріб взагалі є, але зрозуміло, що всі його прямуючі дроби - раціональні числа. Домовимося називати значенням (чи величиною) нескінченного ланцюгового дробу границю нескінченної послідовності його прямуючих дробів: EMBED Equation.3 (поки без усякого доказу існування цієї границі). Алгоритм Евкліда. . Алгоритм Евкліда. Слово "алгоритм" є російською транскрипцією латинізованого імені видатного арабського математика ал-Хорезми Абу Абдули Мухаммеда ібн ал-Маджусі (787 - 850) і означає в сучасному смислі деякі правила, список інструкцій чи команд, виконуючи які, хтось досягне необхідного результату. Алгоритм, що дозволяє за заданими натуральними числами a і b знаходити їхній найбільший спільний дільник, вважається придумав самий впливовий математик усіх часів і народів - Евклід, він викладений у IX книзі його знаменитих "Початків". Відступ "Панегірик Евкліду" Про життя Евкліда ми не маємо ніяких достовірних зведень, можливо, що він не був реальною історичною особистістю, а був колективним псевдонімом деякої групи Олександрійських математиків, типу Ніколя Бурбаки. Якщо він жив, то він жив за часів Птолемея Першого (306 - 283), якому, відповідно до переказу, він сказав "До геометрії немає царської дороги". Але Птолемеї свідомо культивували науку і культуру в Олександрії, тому не звертали уваги на такі слова своїх учених. Найбільш знаменитий твір Евкліда - тринадцять книг його "Начал", але є ще й інші дрібні опуси. Ми не знаємо, яка частина цих праць належить самому Евкліду і які частини складають компіляції, але в цих працях виявляється разюча проникливість і далекоглядність. Це перші математичні праці, що дійшли до нас від древніх греків цілком. В історії Західного світу "Начала", після Біблії, - книга, що найбільше число раз видана і найбільш вивчена. Велика частина нашої шкільної геометрії запозичена буквально з перших шести книг "Начал", традиція Евкліда дотепер тяжіє над нашим елементарним навчанням. Для професійного математика ці книги усе ще мають непереборне зачарування, а їх логічна дедуктивна побудова вплинула на сам спосіб наукового мислення більше, ніж інший здобуток. Панегірик кінчений. Нехай дані два числа a і b ; a 0, b 0, вважаємо, що a > b . Символом := у записі алгоритму позначаємо присвоювання. Алгоритм: 1. Ввести a і b . 2. Якщо b = 0 , то Відповідь: а . Кінець . 3. Замінити r := "залишок від ділення а на b ", а := b , b := r . 4. Йти на 2. рис.3. Як і чому виконання цього коротенького набору інструкцій приводить до знаходження найбільшого спільного дільника ми з'ясуємо трохи пізніше, зараз же хочеться сказати кілька слів про сам алгоритм. Покрокове виконання алгоритму Евкліда переконують у його простоті без строкатості. Проілюструємо роботу алгоритму на грецький лад мал. 3: У сучасному буквеному записі, що кочує з одного підручника в іншій, алгоритм Евкліда виглядає так: a > b; a, b Z . Маємо: b > r 1 > r 2 >... > r n > 0, отже процес обірветься максимум через b кроків. Дуже цікавий і практично важливе питання в тому, коли алгоритм Евкліда працює особливо довго, а коли швидко, ми розглянемо трохи пізніше. Покажемо зараз, що r n = ( a , b ). Переглянемо послідовно рівності зверху вниз: усякий дільник а і b ділиться на r1 , r2 ,..., rn . Якщо ж переглядати цей ланцюжок рівностей від останнього до першого, то видно, що rn | rn -1 , rn | rn -2 , і т.д., тобто rn ділиться на а і b . Тому rn - найбільший спільний дільник чисел а і b . З його розгляду алгоритму Евкліда зрозуміло, що сукупність дільників а і b збігається із сукупністю дільників ( a , b ). Ще він дає практичний спосіб одержання чисел u і v з Z (чи, якщо завгодно, з теореми пункту 2) таких, що r n = au + bv = ( a, b ). Дійсно, з ланцюжка рівностей маємо: r n = r n -2 - r n -1 q n = r n -2 - ( r n -3 - r n -2 q n -1 ) q n = ... (йдемо по ланцюжку рівностей знизу нагору, виражаючи з кожної наступної рівності залишок і підставляючи його у вираз, що одержаний вже до цього моменту) ... = au + bv = ( a , b ). Приклад. Нехай а = 525, b = 231. Віддамо ці числа на розтерзання алгоритму Евкліда: (нижче приводиться запис ділення куточком, і кожен раз те, що було в куточку, а саме дільник, дописується до залишку ділення з лівої сторони, а залишок, як новий дільник, береться в куточок) Запис того самого у вигляді ланцюжка рівностей: 525 = 231 · 2 + 63 231 = 63 · 3 + 42 63 = 42 · 1 + 21 42 = 21 · 2 Таким чином, (525, 231) = 21. Лінійне представлення найбільшого спільного дільника: 21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 = 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) = 525 · 4 - 231 · 9, і наші горезвісні u і v з Z рівні, відповідно, 4 і - 9. Означення простого числа. Число р N , р 1, називається простим, якщо р має лише два додатних дільники: 1 і р. Інші натуральні числа (крім 1) прийнято називати складеними. Число 1 має особливий статус за домовленістю, – воно ні просте, ні складене. Коли алгоритм Евкліда працює найдовше? Означення числа порівняльного за модулем Визначення. Нехай а, b Z , m N. Число а порівняльне з b за модулем m, якщо а і b при діленні на m мають однакові залишки: a b(mod m) . Означення повної системи лишків. Визначення. Будь-яке число з класу еквівалентності m називається лишком за модулем m. Сукупність лишків, узятих по одному з кожного класу еквівалентності m, називається повною системою лишків за модулем m (у повній системі лишків усього m чисел). Безпосередньо самі залишки ділення на m називаються найменшими невід’ємними лишками і утворюють повну систему лишків за модулем m. Означення зведеної системи лишків Визначення. Зведеною системою лишків за модулем m називається сукупність усіх лишків з повної системи, взаємно простих з модулем m. Зведену систему звичайно вибирають з найменших невід’ємних лишків. Зрозуміло, що зведена система лишків за модулем m містить (m) лишків, де (m) – функція Ейлера – кількість чисел, менших за m і взаємно простих з m. Що означає розв’язати порівняння. Розв’язати порівняння – означає знайти всі ті х, що задовольняють даному порівнянню, при цьому весь клас чисел за mod m вважається одним розв’язком. Скільки розв’язків має порівняння за простим модулем p. Якщо порівняння axn+a1 xn-1+…+an0(mod p) степеня n за простим модулем р має більше n різних розв’язків, то всі коефіцієнти a,a1 ,…,an кратні р. Доказ. Нехай порівняння axn +a1 xn-1+…+an0(mod p), має n+1 розв’язок і x1 ,x2 ,…,xn,xn+1–найменші невід’ємні лишки цих розв’язків Які порівняння називаються рівносильними? Порівняння називаються рівносильними, якщо вони мають однакові розв’язки. Наведіть функцію знаходження кількості дільників даного числа. Нехай ( а) = а 0 1 - тотожна одиниця (свідомо мультиплікативна функція). Тоді, якщо EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-004.gif", та тотожність леми 1 пункту 13 набуває вигляду: EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-001.gif", - це не що інше, як кількість дільників числа a . Наведіть функцію знаходження суми дільників даного числа. Нехай ( a ) = a 1 a - тотожна мультиплікативна функція. Тоді, якщо EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-004.gif", то тотожність леми 1 пункту 13 набуває вигляду: EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-002.gif" сума всіх дільників числа a . Означення алгоритму. Означає в сучасному смислі деякі правила, список інструкцій чи команд, виконуючи які, хтось досягне необхідного результату. Чи можна розкласти довільне ціле число відмінне від -1, 0, 1 за допомогою добутку простих чисел? ІІ рівень Типи задач в теорії алгоритмів. Наведіть характеристики. Задача обчислення функції EMBED Equation.3 полягає у знаходженні для вказаного слова EMBED Equation.3 значення функції EMBED Equation.3 . Ми будемо описувати задачі обчислення наступним чином: Задано: EMBED Equation.3 . Обчислити: EMBED Equation.3 . Втім, коли нам не буде настільки важливо, в якому алфавіті і як саме кодуються аргументи та значення функції, ми допускатимемо і менш формальні описи задач на кшталт Задано: EMBED Equation.3 . Обчислити: EMBED Equation.3 . Іноді задачу у вищеозначеному сенсі ми будемо називати масовою. Конкретне задане EMBED Equation.3 називатимемо індивідуальною задачею. Значення EMBED Equation.3 будемо називати розв'язком індивідуальної задачі EMBED Equation.3 . Масову задачу можна вважати нескінченним набором індивідуальних задач. Нехай EMBED Equation.3 — множина слів у алфавіті А*. Часто L називають мовою. Задача розпізнавання мови L полягає у визначенні, належить задане слово EMBED Equation.3 цій мові, чи ні: Задано: EMBED Equation.3 . Розпізнати: EMBED Equation.3 ? Наприклад, Задано: EMBED Equation.3 . Розпізнати: чи є EMBED Equation.3 повним квадратом ? Індивідуальною задачею є будь-яке задання слова w. Розв'язком індивідуальної задачі є відповідь "так" чи "ні", яку прийнято кодувати символами 1 та 0 відповідно. Ще один різновид задачі, який нам буде траплятися, називається задачею пошуку елемента із заданою властивістю. Нехай алфавіт А не містить символу # і EMBED Equation.3 {#})*. Для кожного заданого EMBED Equation.3 задача полягає або у знаходженні хоча б одного EMBED Equation.3 такого, що EMBED Equation.3 # EMBED Equation.3 , або у констатації, що елемента EMBED Equation.3 з такою властивістю немає: Задано: EMBED Equation.3 . Знайти: EMBED Equation.3 таке, що EMBED Equation.3 # EMBED Equation.3 . Індивідуальною задачею є довільно задане слово EMBED Equation.3 , а її розв'язком е або відповідне EMBED Equation.3 , або відповідь "не існує", яку зручно кодувати символом #. Наприклад, Задано: EMBED Equation.3 . Знайти: EMBED Equation.3 таке, що EMBED Equation.3 . Ми ввели три типи задач — обчислення, розпізнавання та пошуку. Насправді, в обчислювальному відношенні всі вони рівносильні між собою — кожну задачу одного типу можна переформулювати як задачу будь-якого з двох інших типів. Так, задача розпізнавання мови EMBED Equation.3 є ні чим іншим, як задачею обчислення її характеристичної функції EMBED Equation.3 , що набуває значення 1 на аргументах з EMBED Equation.3 і лише на них. Задачу обчислення функції EMBED Equation.3 легко подати як задачу пошуку, взявши EMBED Equation.3 # EMBED Equation.3 , де EMBED Equation.3 — множина слів у алфавіті EMBED Equation.3 # EMBED Equation.3 . Нарешті, кожну задачу пошуку можна звести до деякої задачі розпізнавання . Діофантові рівняння. Частковий та повний розв’язок. 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 Таким чином, в теорії лінійних діофантових рівнянь загальний розв’язок неоднорідного рівняння є сумою загального розв’язку відповідного однорідного рівняння і якогось (кожного) часткового розв’язку неоднорідного рівняння. Як же шукати саме частковий розв’язок { 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 значно прискорюють процес обчислення прямуючих дробів. Самі співвідношення дуже легко довести, якщо скористатися принципом математичної індукції. Приклад. Згадаємо розклад в ланцюговий дріб числа 105/38 і обчислимо прямуючі дроби. Маємо: EMBED Equation.3 Обчислення чисельників і знаменників прямуючих дробів зводимо в таблицю: Другий рядок цієї таблиці - неповні частки - заповнюється відразу після роботи алгоритму Евкліда, числа P0 = 1, Q0 = 0, P1 = q1 , Q1 = 1 проставляються в таблицю автоматично. Два останні рядки заповнюються зліва направо з використанням рекурентних співвідношень. Наприклад, число 11 = P3 у третьому рядку виникло так: трійка, що стоїть над ним, помножилася на трійку, що стоїть перед ним, і до результату додалася двійка спереду, отже P3=q3P2+P1=33+2. Після того, як у таблиці вже є число 11, наступна клітинка в цьому рядку заповнюється числом 4 · 11 + 3 = 47, і т.д. Погодьтеся, що цей процес набагато швидший за розкручування багатоповерхових дробів. Відповідь: 0 = ; 1 = 2; 2 = 3; 3 = EMBED Equation.3=2,75, EMBED Equation.3 EMBED Equation.3 - на п'ятому кроці (починаючи з нуля) прямуючі дроби підійшли до самого числа, стрибаючи довкола нього, причому дроби з парними номерами більші за початкове число, а з непарними - менші, і послідовність прямуючих дробів дуже швидко сходиться до самого числа. Це, звичайно, не випадково, але про ці властивості трохи нижче. Порахуємо прямуючі дроби розкладу 2 у ланцюговий дріб з прикладу 1 попереднього пункту. Складемо таблицю: Уже на шостому кроці одержали дріб 99/70 = 1,41428..., тобто досягнена дуже висока точність. Знадобилося для цього лише кілька хвилин, що показує ефективність ланцюгових дробів. Теорема Ейлера. Застосування???. Нехай 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). Теорема Ферма. Застосування. Нехай р – просте число, р не ділить 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). Наведемо кілька прикладів застосування теорем Ферма і Ейлера. Зазначимо, що ефективність застосування теорем Ферма і Ейлера ґрунтується на тому, що порівняння, що даються цими теоремами, зручно підносити до степеня, оскільки справа у них стоїть одиниця, що на піднесення до степеня не реагує. Приклад 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) і одержимо a7(mod 10). Це означає, що a=7. Розв’язування порівнянь першого степеня вигляду axb(mod m) для взаємно простих a і m. Випадок 1. Нехай а і m взаємно прості. Тоді нескоротний дріб m/a розкладається в ланцюговий дріб: EMBED Equation.3 Цей ланцюговий дріб, зрозуміло, скінченний, тому що m/a - раціональне число. Розглянемо два останні прямуючі дроби: EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-002.gif"; 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) Випадок 2. Нехай (a,m)=d. У цьому випадку, для можливості розв'язку порівняння axb(mod m) необхідно, щоб d ділило b, інакше порівняння узагалі виконуватися не може. Дійсно, axb(mod m) буває тоді, і тільки тоді, коли ax-b ділиться на m без остачі, тобто ax-b=t · m, t Z, звідки b=ax-t m , а права частина останньої рівності кратна d. Нехай b=db1, a=da1, m=dm1. Тоді обидві частини порівняння xa1 db1 d(mod m1 d) і його модуль поділимо на d : xa1 b1 (mod m1), де вже а1 і m1 взаємно прості. Згідно випадку 1 цього пункту, таке порівняння має єдиний розв’язок x0 : x x0 (mod m1 ) (*) За вихідним модулем m, числа (*) утворять стільки розв’язків вихідного порівняння, скільки чисел виду (*) міститься в повній системі лишків: 0,1,2,..., m-2, m-1. Очевидно, що з чисел x=x0+tm в повну систему найменших невід’ємних лишків попадають лише x0, x0+m1, x0+2m1, ..., x0+(d-1)m1, тобто усього d чисел. Значить у вихідного порівняння є d розв’язків. Китайська теорема про лишки. (Китайська теорема про лишки). Нехай дана найпростіша система порівнянь першого степеня: EMBED Equation.3 (*)INCLUDEPICTURE \d \z "../pict/19-009.gif" де m1,m2,...,mk попарно взаємно прості. Нехай, m1 m2 ...mk =Ms ms; Ms Ms1(mod ms) (Очевидно, що таке число Msзавжди можна підібрати хоча б за допомогою алгоритму Евкліда, оскільки (ms, Ms )=1); x0 =M1 M1b1+M2 M2b2 +...+Mk Mkbk. Тоді система (*) рівносильна одному порівнянню x x0 (mod m1 m2 ...mk ), а саме набір розв’язків (*) збігається з набором розв’язків порівняння xx0(mod m1m2 ...mk). Доказ. Маємо: ms ділить Mj, при sj. Отже, x0 Ms Msbs (mod ms), звідки x0bs(mod ms). Це означає, що система (*) рівносильна системі EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-010.gif" яка, у свою чергу, рівносильна одному порівнянню xx0 (mod m1 m2 ...mk ). Зведення розв’язування порівняння високого степеня до розв’язування порівняння меншого степеня. Лема 1. Довільне порівняння f(x) 0(mod p), де р - просте число, рівносильне деякому порівнянню степеня не вищого за p-1. Доказ. Розділимо f(x) на многочлен xp-x ("многочлен ділення круга") із залишком: f(x)=(xp-x)Q(x)+R(x), де, як відомо, степінь залишку R(x) не перевищує р-1. Але за теоремою Ферма, xp-x0(mod p). Це означає, що f(x)R(x)(mod p), а вихідне порівняння рівносильне порівнянню R(x)0(mod p).

Інші Інші

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись