Сравнения и модульная арифметика

Модульная арифметика изучает целые числа с точностью до делимости на фиксированный модуль, превращая целые числа в конечное кольцо Z/nZ и предоставляя теории чисел ее наиболее гибкий вычислительный инструмент.

Definition

Два целых числа сравнимы по модулю n, если их разность делится на n. Модульная арифметика — это арифметика результирующих классов вычетов, которые образуют коммутативное кольцо Z/nZ.

Scope

Эта тема охватывает отношение сравнения и классы вычетов, арифметику в Z/nZ, линейные и полиномиальные сравнения, китайскую теорему об остатках, малую теорему Ферма и теорему Эйлера, структуру группы единиц, первообразные корни и порядок элементов. Это язык, на котором выражается большая часть элементарной и вычислительной теории чисел.

Core questions

• Когда линейное сравнение ax сравнимо с b mod n имеет решения и сколько их?
• Как китайская теорема об остатках разлагает Z/nZ в произведение по модулям, являющимся степенями простых чисел?
• Почему верны малая теорема Ферма и теорема Эйлера, и что они говорят о порядке единиц?
• Для каких модулей существует первообразный корень, делающий группу единиц циклической?

Key theories

Китайская теорема об остатках

Если модули попарно взаимно просты, система одновременных сравнений имеет единственное решение по модулю произведения; эквивалентно, Z/nZ изоморфно произведению Z по его простым сомножителям в степенях.

Малая теорема Ферма и теорема Эйлера

Для a, взаимно простого с n, a в степени функции Эйлера от n сравнимо с единицей по модулю n; случай простого числа (Ферма) лежит в основе тестов на простоту, а общий случай лежит в основе RSA.

Первообразные корни и структура группы

Мультипликативная группа единиц по модулю n является циклической тогда и только тогда, когда n равно единице, двум, четырем, нечетной степени простого числа или удвоенной степени нечетного простого числа; генератор является первообразным корнем, дающим дискретный логарифм.

Clinical relevance

Модульная арифметика является вычислительным ядром криптографии (RSA, Диффи-Хеллман, схемы на эллиптических кривых), контрольных сумм и обнаружения ошибок (ISBN, хеш-функции), а также генерации псевдослучайных чисел, что делает ее наиболее широко используемой частью теории чисел.

History

Хотя частные случаи встречаются в древнекитайской и индийской математике (задача об остатках, названная в честь первой), систематическая теория сравнений была введена Гауссом в «Арифметических исследованиях» (1801), где он установил обозначения и доказал центральные структурные результаты.

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

Что означает обозначение a сравнимо с b mod n?

Это означает, что n делит разность a минус b, или, эквивалентно, a и b дают одинаковый остаток при делении на n.

Почему RSA основан на теореме Эйлера?

Шифрование и дешифрование RSA — это модульные возведения в степень, композиция которых возвращает исходное сообщение именно потому, что теорема Эйлера гарантирует, что соответствующий показатель степени действует как тождество по модулю ключа.