Китайська теорема про остачі

Конгруенції з одним невідомим.

Доведення теореми Эйлера.

Теореми Ейлера і Ферма.

При первісні корені завжди існують.

Число називається первісним коренем (первісним елементом) за модулем, якщо його порядок по модулі дорівнює.

Відомо, що в кожному скінченному полі також існує первісний елемент (генератор поля). Степені первісного елемента представляють усі ненульові елементи поля.

Зокрема, якщо первісний елемент поля, те порівняння розв'язне для ненульових лишків за модулем.

Показник у цьому порівнянні називається дискретним логарифмом числа за основою. Дискретні логарифми часто називають індексами і позначають або.

Теорема Ейлера. Якщо, то.

З теореми Ейлера випливає мала теорема Ферма:, де - простої,.

Ці теореми інтенсивно використовуються в асиметричній криптографії і, крім того, дуже корисні для скорочення обчислень.

Як наслідок, з теореми Ейлера випливає, що елемент є первісним коренем за модулем тоді і тільки тоді, коли виконуються співвідношення:, де.

Зауважимо, що в кожному скінченному полі, при,, виконується співвідношення. Це зв'язано з тим, що число є порядком мультиплікативної групи поля.

Щоб врахувати значення, помножимо обидві частини зазначеного співвідношення на. Одержимо, що для будь-якого елемента кінцевого поля вірне співвідношення.

Нагадаємо, що розширення скінченного поля може бути представлене як кільце лишків многочленів за модулем незвідного многочлена, над простим полем:.

Для деяких незвідних многочленів послідовність пробігає всі можливі лишкі, тобто всі елементи поля. Такі многочлени називаються примітивними.

Нехай - всі різні числа, які взаємно прості з і не перевищують. Очевидно,.

Оскільки,, у послідовності будь-які два члени з різними індексами непорівнянні за модулем.

Тому послідовності і співпадають, з точністю до перестановки членів.

Отже, добуток всіх членів однієї послідовності і добуток всіх членів іншої послідовності порівнянні за модулем, звідки, після скорочення на, одержуємо.

Нехай числа попарно взаємно прості і. Тоді існує єдиний за модулем розв’язок системи порівнянь,.

При цьому,, де,.

Дійсно, у зазначеному вирзі для, один доданок порівнянний з за модулем, а всі інші порівнянні з нулем.

Коефіцієнти можна обчислити заздалегідь і розв’язувати кілька систем, підставляючи їхні праві частини в лінійну форму.

Китайська теорема про остачі показує, що розв’язок порівняння можна знайти, якщо знати розв’язки цього порівнянняза модулями, рівним степеням простих, що входять у канонічний розклад числа на співмножники.

Дата добавления: 2014-10-15