2.2 Алгоритмы решения задач

Как пример рассмотрим систему:

Для решения системы выпишем отдельно решения первого, второго и третьего уравнений (достаточно выписать решения не превосходящие 2 × 3 × 7 = 42):

Очевидно, что множество решений системы будет пересечение представленных выше множеств. По утверждению теоремы решение существует и единственно с точностью до операции взятия по модулю 42. В нашем случае   или 

Для того, чтобы продемонстрировать другой путь, переформулируем задачу. Найдем тройку чисел (u, v, w) таких, что:

Подставив x из первого уравнения во второе, получим, тогда, или, или ; подставив затем x из первого уравнения в третье с учетом выражения для    получим    или, тогда  ; тогда.

Алгоритм на основе китайской теоремы об остатках сводится к поиску решений по формуле, данной в теорем.

1. Вычисляем.

2. Для всех   находим.

3. Находим   (например, используя  расширенный алгоритм Евклида).

4. Вычисляем искомое значение по формуле.

Алгоритм Гарнера. Рассмотрим набор модулей, удовлетворяющих условию теоремы. Другой теоремой из теории чисел утверждается, что любое число   однозначно представимо в виде^[10]

.

Вычислив по порядку все коэффициенты   для   мы сможем подставить их в формулу и найти искомое решение:

Обозначим через   и рассмотрим выражение для   по модулю, где, получим:

;

;

;

;

и так далее.

Формулировка для колец. Пусть   — коммутативные кольца с единицей,   — сюръективные гомоморфизмы, обладающие свойством   для всех. Тогда гомоморфизм, заданный формулой, является сюръективным. Более того,   определяет изоморфизм

.

Если положить   и определить гомоморфизмы следующим образом, то мы получим арифметическую версию теоремы.

Также часто встречается эквивалентная формулировка для колец, где   имеют форму   для некоторого набора идеалов, гомоморфизмы  являются естественными проекциями на   и требуется, чтобы   для любых. Другими словами, если идеалы  попарно взаимно просты (то есть сумма двух различных идеалов равна самому кольцу), то их произведение совпадает с их пересечением, и факторкольцо по этому произведению изоморфно произведению факторов: .

ЗАКЛЮЧЕНИЕ

В данной работе достаточно полно изложены основные моменты теории, они иллюстрируются примерами, которые позволяют глубже понять рассматриваемые вопросы.

В работе были приведены несколько показательных примеров, проявляющейся при решении специфических школьных «олимпиадных» задач с помощью теорем сравнений.

Основные свойства сравнений:

1. Рефлексивность.

2. Симметричность.

3. Транзитивность.

4. Сравнения по одному и тому же модулю можно почленно складывать, вычитать и перемножать.

5. Части сравнения можно делить на их общий делитель, взаимно простой с модулем.

6. Части сравнения и модуль можно делить (умножать)на одно и то же число.

7. Если числа сравнимы по данному модулю, то они сравнимы по модулю-делителю данного модуля.

8. Если числа сравнимы по нескольким модулям, то они сравнимы по модулю-НОК данныхмодулей.

С помощью «языка сравнений» можно не только давать более короткие решения задач, но столь же кратко излагать теоретические факты и их доказательства.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие. — М.: МФТИ, 2011. — 262 с. 

2. Н. Смарт Криптография. — 2005. — 528 с.

3. Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — 190 с.

4. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — 2011. — 202 с.

5. Переславцев О. Н. Распараллеливание алгоритмов с применением китайской теоремы об остатках. — Вестник ТГУ, 2009. — ≠ 4.

6. Фергюсон, Нильс, Шнаер, Брюс Практическая криптография. — М.: Вильямс, 2004. — 432 с.

7. Ян Сонг Й Криптоанализ RSA. — 2011. — 312 с.

8. Шенец Н. Н. Модульное разделение секрета и системы электронного голосования. — Вестник БГУ, 2011. — ≠ 1.

9. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с.

10. Бухштаб А.А. Теория чисел. - М.: Просвещение, 1960. - 376 с.

11. Алгебра и теория чисел: Уч. пособие. под ред. Н.Я. Виленкина. - М.: Просвещение, 1984. - 192 с. (гл. 3).

12. Вахитова Е.В. Теория сравнений и ее приложения. - Стерлитамак: Изд-во СГПИ, 2000. - 414 с.

13. Фаддеев Д.К., Соминский И.С. Сборник задач по высшей алгебре. - М.: Наука, 1984. - 288 с.

14. Лельчук М.П., Полевченко И.И., Радьков А.М., Чеботаревский Б.Д. Практические занятия по алгебре и теории чисел. - Минск: Высш. Школа, 1986. - 302 с.

15. Шнеперман Л.Б. Сборник задач по алгебре и теории чисел. - Мн.: Высш. шк., - 1982. - 223 с.

16. Михелович Ш.Х. Теория чисел. М.: Высшая Школа, 1967. - 335 с.

17. Александров В.А., Горшенин С.М. Задачник-практикум по теории чисел. М.: Просвещение 1960. - 48 с.

27