Практичне заняття № 4 Тема: Розв’язування алгебраїчних конгруенцій

Мета заняття: Засвоїти алгоритм Шенкса-Тонеллі розв’язування квадратних конгруенцій за простим модулем; методи розв’язування алгебраїчних конгруенції -го степеня за простим модулем, за складеним модулем, розкладання многочлена на незвідні множники над скінченним полем за алгоритмом Берлекемпа.

Короткі теоретичні відомості

1. Розв’язування квадратних конгруенцій за простим модулем

Розглянемо квадратну двочленну конгруенцію за простим непарним модулем :

, (1)

Число називається квадратичним лишком за модулем , якщо конгруенція (1) має розв’язки. Число називається квадратичним нелишком за модулем , якщо конгруенція (1) розв’язків не має.

За критерієм Ейлера для визначення квадратичних лишків і нелишків., якщо , то конгруенція (1) має розв’язки тоді і тільки тоді, коли , тобто

(2)

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

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

Відомі окремі випадки:

1. Якщо , то .

2. Якщо , то у випадку , а у випадку .

У випадках , для розв’язування (1) застосовується апроксимаційний (наближувальний) алгоритм.

Алгоритм Шенкса-Тонеллі (Shanks-Tonelli) добування квадратного кореня є більш ефективним, ніж апроксимаційний алгоритм, у випадку, коли , або .

Алгоритм Шенкса -Тонеллі

1. Обчислити значення символу Лежандра . Якщо , – квадратичний лишок, якщо , – квадратичний нелишок

2. Записати число у вигляді добутку парного і непарного чисел: , .

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

4. Покласти .

5. Обчислити , .

6. Обчислити порядок , який є дільником , тобто (порядком називається число таке, що ).

7. Обчислити степінь , в який треба підносити : .

8. Обчислити , ,

Якщо при деякому порядок виявиться рівним 1, то – шуканий корінь.

2. Алгебраїчні конгруенції -го степеня за простим модулем

Нехай задано конгруенцію

, (3)

або скорочено

,

де – просте число, , , , , .

Перед розв’язуванням таких конгруенцій, їх спрощують у наступні способи:

1. Заміна коефіцієнтів абсолютно найменшими лишками за модулем .

Якщо , , де – абсолютно найменший або найменший невід'ємний лишок за модулем . Тоді .

2.Зниження степеня конгруенції.

Якщо , то не може набувати значень, кратних , тобто , значить . За теоремою Ферма . Якщо таке, що , то, поділивши з остачею на , маємо: , де , . Тоді

.

Замінивши в конгруенції (3) доданки на конгруентні їм , приходимо до конгруенції степеня меншого за , яка еквівалентна конгруенції (3).

3. Перехід до еквівалентної конгруенції, старший коефіцієнт якої дорівнює 1.

Якщо , то знаходимо ціле число таке, що . Помноживши обидві частини конгруенції (3) на , отримуємо еквівалентну конгруенцію, в якій .

При розв’язуванні конгруенцій (3) застосовуються теореми:

Теорема 1 (Безу-Горнера). Для будь-якого многочлена , , і числа , такого, що , справедливо:

де , , , , .

Теорема 2 (про число розв’язків конгруенції -го степеня за простим модулем) Конгруенція -го степеня за простим модулем із старшим коефіцієнтом, що не ділиться на , може мати не більше ніж коренів.

Наслідок 1. Якщо деякі числа становлять розв'язок конгруенції -го степеня, то ця конгруенція еквівалентна конгруенції

.

Для отримання розв’язків конгруенції (3) після спрощення застосовують спосіб підбору абсолютно найменших лишків за даним простим модулем. Для цього записують повну систему абсолютно найменших лишків за даним простим модулем і підставляють числа цієї системи в дану конгруенцію. Лишки, що задовольняють конгруенцію, є представниками класів, які є розв’язками даної конгруенції.