Лекція 5
7.2) Обчислимо , .
Значить, .
Значить, .
Отже, .
Шукані корені
,
або , .
Перевірка: .
Алгоритм Шенкса-Тонеллі (Shanks-Tonelli) добування квадратного кореня є більш ефективним, ніж апроксимаційний алгоритм, у випадку, коли , або . Збережемо позначення такі, як для попереднього алгоритму.
Содержание
- Лекція № 5 Тема: Розв’язування алгебраїчних конгруенцій
- 1. Розв’язування квадратних конгруенцій за простим модулем
- 7.2) Обчислити , .
- 7.2) Обчислимо , .
- Алгоритм Шенкса -Тонеллі
- 2. Алгебраїчні конгруенції -го степеня за простим модулем та способи їх розв'язування
- 1. Заміна коефіцієнтів абсолютно найменшими лишками за модулем .
- 2.Зниження степеня конгруенції.
- 3. Перехід до еквівалентної конгруенції, старший коефіцієнт якої дорівнює 1.
- 3. Число розв’язків конгруенції -го степеня за простим модулем
- 4. Алгебраїчні конгруенції -го степеня за складеним модулем та способи їх розв'язування
- 5. Алгоритм Берлекемпа розкладання многочлена на незвідні множники над скінченним полем
- Алгоритм Берлекемпа (Berlecamp’s Algorithm)