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

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

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

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2015

Тип роботи:

Інші

Предмет:

Інші

Завантажити

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

Алгоритмічні основи криптології І Рівень 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).

Інші Інші

2015

Коментарі

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

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

поділитись