Математика · объяснение и практика
Обратный элемент по модулю: условие существования и проверка
Находим обратный множитель по модулю, проверяем условие взаимной простоты и отличаем обратный остаток от обычной дроби.

В теме Теория чисел: углубление · Учебная карта
Главная мысль
Обратный к a по модулю m ≥ 2 — такой целый остаток u, что au ≡ 1 по модулю m. Он существует тогда и только тогда, когда НОД(a,m) = 1. Это не обычное действительное число 1/a, а класс целых чисел.
Как выглядит обратимость в конечной системе остатков
Для модуля семь число пять является обратным к тройке: произведение пятнадцать оставляет остаток один. Можно использовать и −2, поскольку оно сравнимо с пятью. Эти разные целые числа задают один класс обратного элемента. Обычно выбирают представителя от нуля до m−1, чтобы проверка и дальнейшие вычисления были короче.
Если a имеет общий делитель d > 1 с m, каждое произведение au и каждое кратное m делятся на d. Их разность не может равняться единице. Поэтому обратного элемента нет. Например, у шести по модулю пятнадцать нельзя найти целый множитель с произведением, оставляющим остаток один, хотя обычная дробь 1/6 существует.
Алгоритм Евклида даёт нужный множитель
Найдём обратный к семи по модулю двадцать шесть. Деления дают 26 = 3·7+5, 7 = 5+2, 5 = 2·2+1. Обратные подстановки приводят к 1 = 3·26−11·7. Поэтому −11 является обратным представителем; после добавления двадцати шести получаем удобный остаток пятнадцать.
Проверка не требует повторять весь алгоритм: 7·15 = 105 = 4·26+1. Единичный остаток подтверждает результат. В более длинном расчёте полезно сохранить это короткое произведение как контроль. Само совпадение НОД с единицей обещает существование, но не заменяет проверку найденного коэффициента, в котором могла возникнуть арифметическая ошибка.
Пример
Найдите обратный к пяти по модулю двенадцать.
Произведение 5·5 = 25 = 2·12+1. Значит, число пять обратимо и является собственным обратным представителем. Это допустимо: обратный элемент не обязан отличаться от исходного.
Как применять и проверять смысл деления
Если нужно решить ax ≡ b по модулю m и обратный u существует, умножаем на u: x ≡ ub. Так деление на a заменяется умножением на целый обратный остаток. Например, наличие обычного деления b/a не гарантирует, что эта рациональная дробь является допустимым ответом в задаче о целых остатках.
Обратный класс единственен: если au и av оба сравнимы с единицей, после корректного сокращения обратимого a получаем u ≡ v. При этом сам список целых представителей бесконечен — к найденному можно прибавлять любое кратное модуля. Различение класса и представителя помогает не считать пять и минус два разными обратными элементами по модулю семь.
От чтения к действию
А теперь — вы
Частые вопросы
Может число быть обратным самому себе?
Да. Например, 5·5 оставляет остаток один по модулю двенадцать. Условие касается произведения, а не различия двух чисел.
Зачем нужен НОД перед поиском?
Он показывает, существует ли обратный элемент вообще. При общем делителе больше единицы поиск единичного остатка не даст результата.
Углублённый разбор
Пакет обратных элементов с одним обращением
Несколько обратных элементов можно получить одним дорогим обращением. Префиксные произведения и обратный проход заменяют остальные обращения умножениями, если каждый исходный элемент обратим.
Перед началом: Модульная обратная; Коммутативное умножение.
Произведение связывает все обратные
Работаем по модулю m≥2. Даны a₁,…,aₙ, каждый взаимно прост с m. Построим префиксы P₀=1 и Pᵢ=Pᵢ₋₁aᵢ по модулю m. Полное произведение обратимо, поскольку произведение обратимых классов обратимо. Найдём единственную дорогую обратную величину u=Pₙ⁻¹.
Теперь uPₙ₋₁=aₙ⁻¹. Ведь произведение этого выражения на aₙ равно uPₙ=1. После выдачи ответа заменим u на uaₙ: это уже Pₙ₋₁⁻¹. Так обратный проход поддерживает тот же смысл накопителя и позволяет получить следующий обратный элемент без нового запуска расширенного Евклида.
Инвариант определяет порядок обновлений
Перед обработкой позиции i накопитель должен равняться Pᵢ⁻¹. Сначала запишем bᵢ=uPᵢ₋₁, затем обновим u←uaᵢ. Если переставить эти действия, в ответ попадёт уже другой префикс. Исходный aᵢ понадобится после выдачи bᵢ, поэтому при записи результата на месте нужно сохранить старое значение.
Построение префиксов требует n−1 существенных умножений, обратный проход — ещё 2(n−1), если крайние тривиальные операции опущены. Итого одно обращение и 3(n−1) умножений. Память под префиксы линейна, хотя возможны иные схемы хранения. Выгода зависит от относительной цены обращения и умножения, а не от одного числа операций.
Составной модуль проверяет условие особенно наглядно
Если хотя бы один aᵢ не является единицей кольца, полное произведение не обратимо. Нулевое значение в поле тоже нарушает условие. Нельзя молча заменить его обратную на 0 и объявить весь список математически обращённым. Некоторые библиотеки пропускают нули по отдельному договору, но это другая спецификация результата.
При составном m обратимость общего произведения равносильна обратимости каждого множителя. Проверка НОД(Pₙ,m)=1 поэтому может сертифицировать весь пакет, хотя не локализует неудачный элемент. В конце полезно независимо умножить каждую исходную пару aᵢbᵢ: проверка одного общего произведения не обнаружит перестановку индивидуальных ответов.
Три ответа из одного обращения
Условие. Найдите обратные к 2,3,5 по модулю 17, применяя один обратный элемент полного произведения.
- Префиксы равны P₁=2,P₂=6,P₃=30≡13. Обратный к 13 равен 4, поскольку 13·4=52≡1.
- Для последнего элемента b₃=4·6≡7. Обновляем накопитель u=4·5≡3; теперь он обратен P₂.
- Для второго элемента b₂=3·2=6. Обновляем u=3·3=9, что является обратным к P₁.
- Для первого элемента b₁=9. Получаем упорядоченный список(9,6,7), сопоставленный исходным(2,3,5).
Ответ. Обратные равны 9,6,7 соответственно.
Проверка. Три независимые подстановки дают 2·9≡1,3·6≡1,5·7≡1 по модулю 17. Перебор классов 0,…,16 находит для каждого элемента ровно этот один обратный.
Где легко ошибиться. Сначала выдавайте текущую обратную, затем меняйте накопитель. При записи на месте не теряйте исходный множитель, необходимый для обновления.
Проверьте понимание
Вопросы к этой главе
Можно применять при непростом модуле?
Да, если каждый элемент взаимно прост с модулем. Алгоритм использует группу единиц коммутативного кольца, а не требует поля всех классов.
Как поступать при необратимом произведении?
Нужно сообщить нарушение условия и при необходимости найти неединичные входы отдельными НОД. Одно неудачное обращение не даёт корректных индивидуальных обратных для остальных автоматически.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Victor Shoup: §4.3, упражнение 4.16
Вебом прочитано упражнение о k обратимых классах с одним обращением и менее 3k умножениями. Конкретный алгоритм префиксов, обратный инвариант и пример главы подготовлены самостоятельно.
Удвоение точности модульной обратной по основанию два
При обращении нечётного числа по модулю степени двойки точность можно удваивать. Одно полиномиальное обновление возводит остаточную ошибку в квадрат и сохраняет уже найденные младшие биты.
Перед началом: Обратимый класс; Степени двойки.
Квадрат ошибки объясняет весь шаг
Пусть ax≡1 по модулю 2ᵏ, k≥1. Запишем e=1−ax; число e делится на 2ᵏ. Возьмём новое x′=x(2−ax). Прямое раскрытие даёт 1−ax′=(1−ax)²=e². Следовательно, новая ошибка делится на 2²ᵏ. Это алгебраическое тождество над целыми, поэтому округление действительных чисел здесь отсутствует.
Для вычисления достаточно сохранять x′по модулю 2²ᵏ. Если целевая точность меньше 2k, сразу берут остаток по целевому модулю. Новое значение совпадает со старым по модулю 2ᵏ, потому что x′−x=x(1−ax) кратно 2ᵏ. Уже подтверждённые младшие биты не меняются.
Начальный бит задаётся условием нечётности
Любое нечётное a обратно самому классу 1 по модулю 2, поэтому начинают с x=1,k=1. Для чётного a обратной по степени двойки нет: произведение с любым целым остаётся чётным. Нельзя запустить ту же формулу с произвольным начальным x и ожидать появления обратимости из итераций.
После каждого шага k заменяют на min(2k,w), где 2ʷ — целевой модуль. Число шагов логарифмично по числу требуемых битов. Однако стоимость самих умножений растёт с точностью. Поэтому логарифмическое число итераций не означает логарифмическое число битовых операций; выгодно ограничивать промежуточную разрядность нужным текущим модулем.
Модульная проверка остаётся обязательной
Можно получить отрицательное промежуточное значение: это обычный представитель класса, а не сбой. Для вывода берут канонический остаток от 0 до 2ʷ−1. В машинной реализации нужны определённые правила переполнения и беззнакового умножения; математическая формула сама по себе не оправдывает неопределённое поведение языка.
После завершения независимо проверяют ax mod2ʷ=1. Дополнительно полезно проверить сохранение предыдущего класса и делимость ошибки на растущую степень двойки. Эти проверки различают ошибку выбора модуля, преждевременную остановку и обычную смену представителя одного класса.
От одного бита к восьми
Условие. Найдите обратный к 13 по модулю 256, удваивая точность из начального x=1 по модулю 2.
- Переходим к модулю 4: x′=1·(2−13)=−11≡1. Подтверждены два младших бита.
- Переходим к модулю 16: из x=1 получаем−11≡5. Проверка 13·5=65≡1 по модулю 16.
- Переходим к модулю 256: x′=5(2−65)=−315≡197. Теперь подтверждены все восемь битов.
- Остаточная ошибка для найденного представителя равна 1−13·197=−2560, кратна 256. Значение 197 сохраняет предыдущий класс 5 по модулю 16.
Ответ. 13⁻¹≡197 по модулю 256.
Проверка. Прямое произведение 13·197=2561=10·256+1 подтверждает ответ. Перебор 256 классов исключает остальные кандидаты и подтверждает единственность обратного.
Где легко ошибиться. Удваивается показатель точности k, а не сам обратный элемент. Формула требует уже верного начального сравнения; чётный множитель невозможно исправить таким подъёмом.
Проверьте понимание
Вопросы к этой главе
Почему это похоже на Ньютон, но без производных?
Полиномиальная формула получается из исправления мультипликативной ошибки и обладает квадратичным её уменьшением в модульном смысле. Доказательство здесь полностью заменяется точным тождеством.
Нужна степень двойки в числе целевых битов?
Нет. Последний шаг можно обрезать до любого w. Если очередная формула гарантирует больше битов, взятие остатка по меньшему целевому модулю сохраняет необходимое сравнение.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Jean-Guillaume Dumas: On Newton-Raphson iteration for multiplicative inverses modulo prime powers
Первичная статья: прочитаны §3.2,Algorithm2 и условия взаимной простоты; проверена формула U(2−aU). Рассматриваемый нечётный множитель, промежуточные классы и тест ошибки созданы отдельно.
Большие и малые шаги в дискретном логарифме
Возведение в степень по модулю быстро движется от показателя к остатку; обратная задача может требовать поиска. Метод больших и малых шагов разбивает диапазон показателей на два коротких списка и ищет совпадение вместо линейного перебора всех степеней.
Перед началом: Обратимый остаток; Порядок элемента конечной группы.
Два разряда показателя образуют встречу
Пусть a и b обратимы по модулю m. Ищем минимальный x≥0 с aˣ≡b. Если решение есть, наименьший показатель меньше порядка a, а порядок не превосходит φ(m)≤m−1. Возьмём h=ceil√m и представим возможный x как jh+i с 0≤i<h. Тогда aⁱ≡b(aʰ)⁻ʲ. Слева малые степени основания, справа последовательные большие шаги цели.
Таблица малых шагов хранит остаток и наименьший i, если остаток повторяется. Большие шаги вычисляют умножением на один обратный остаток (aʰ)⁻¹. Совпадение даёт кандидата jh+i, который проверяют исходным возведением в степень. Среди допустимых кандидатов выбирают минимальный. Нельзя оставлять произвольный последний индекс повторившейся малой степени, иначе можно потерять минимальность.
Отрицательный ответ требует покрытого диапазона
Достаточное число больших шагов должно покрыть все показатели, где может лежать минимальное решение. В лаборатории h²≥m, поэтому h больших шагов вместе с h малыми покрывают [0,m). Кандидаты вне этого диапазона игнорируются. Если совпадений в нём нет, b не принадлежит подгруппе, порождённой a. Такой вывод не требует, чтобы вся группа обратимых остатков была циклической.
Обратимость является существенным условием именно этой версии. При НОД(a,m)>1 нельзя вычислять нужный обратный большой шаг, хотя исходное степенное сравнение иногда имеет решения. Инструмент честно отклоняет такой ввод, а не объявляет уравнение неразрешимым. Для b=1 минимальный неотрицательный ответ равен 0, даже если источник с положительным соглашением называл бы период.
Сложность оценивается по размеру диапазона, а не записи
Алгоритм требует порядка √m групповых операций и памяти для малых шагов. Это ускорение по сравнению с линейным обходом, но не полиномиальное время по числу битов модуля:√m экспоненциально относительно log m. Маленькая лабораторная граница m≤100000 нужна для предсказуемого учебного расчёта. Строка формулы пользователя никогда не выполняется; принимаются только ограниченные целые остатки и модуль.
Поиск показателя со встречей в третьем блоке
Условие. Решите 2ˣ≡5 по модулю 13, найдя минимальный x≥0 методом больших и малых шагов.
- Оба остатка обратимы. Берём h=4. Малые шаги i=0,1,2,3 дают остатки 1,2,4,8.
- Величина 2⁴ равна 3 по модулю 13, обратный к ней остаток 9. Большие шаги b·9ʲ начинаются как 5,6,2,5.
- При j=2 остаток 2 совпал с малым шагом i=1. Получаем x=2·4+1=9; ранее в блоках j=0 и j=1 совпадений нет.
- Проверка 2⁹=512≡5 подтверждает ответ. Прямой список степеней до показателя 8 равен 1,2,4,8,3,6,12,11,9 и не содержит 5.
Ответ. Минимальный неотрицательный показатель x=9.
Проверка. Линейный перечень предыдущих степеней независимо проверяет минимальность, а итоговая модульная степень — само сравнение. Для всего алгоритма отрицательный ответ обеспечивается полным покрытием диапазона показателей.
Где легко ошибиться. Не называйте первым найденным совпадением минимальный показатель без учёта порядка больших шагов и повторов таблицы. Надёжная реализация сохраняет минимальный малый индекс и сравнивает допустимые кандидаты.
Дискретный логарифм: большие и малые шаги
Найдите наименьшее x≥0 с aˣ≡b (mod m). 2≤m≤100000; 0≤a,b<m и оба числа взаимно просты с m. Модуль не обязан быть простым. Полный поиск ограничен порядком конечной группы; отсутствие решения устанавливается для этой модели точно.
Проверьте понимание
Вопросы к этой главе
Что получится при a=1 и b≠1?
Решения нет: все степени 1 дают только 1. Таблица повторов это корректно обрабатывает. При a=b=1 ответ 0, потому что ищется минимальный неотрицательный показатель.
Обязан ли модуль быть простым?
Нет. Достаточно, чтобы a и b были обратимы, а конечный диапазон покрывал возможный порядок. Для составного модуля цель может быть единицей группы, но лежать вне подгруппы основания; тогда отрицательный ответ содержателен.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Andrew Sutherland: MIT18.783, Lecture9, §9.4
Прочитан Baby-steps giant-steps: покрытие показателей rs>N, таблица столкновений и проверка принадлежности подгруппе. Здесь мультипликативные остатки и минимальный неотрицательный логарифм: identity соответствует0, в отличие от положительного соглашения конспекта. HAC chap3 сначала timeout, затем ошибочное перенаправление на chap11; оно не использовано.
Умножение Монтгомери без деления на рабочий модуль
При длинной последовательности модульных умножений деление на произвольный модуль можно заменить специальным представлением остатков. Редукция Монтгомери использует обратный коэффициент по степени двойки. Полученное число остаётся в масштабированных координатах, поэтому входное преобразование и окончательное декодирование являются частью метода.
Перед началом: Обратный элемент по модулю; Целочисленные остатки и двоичный сдвиг.
Представление хранит дополнительный множитель
Выберем нечётный модуль m и R=2ʷ>m. Тогда НОД(m,R)=1. Обычный остаток a представляется числом ā=aR mod m в диапазоне от нуля до m−1. Нужно построить операцию, которая из ā и b̄ получает abR mod m, сохраняя тот же масштаб.
Для этого требуется убрать из произведения один множитель R. Определим REDC(T) как канонический остаток TR⁻¹ mod m. Тогда REDC(āb̄)=abR mod m. Применение REDC к одному представленному числу декодирует его в обычный остаток. Обычное произведение представленных чисел без этой редукции имело бы лишний масштаб R².
Обратный коэффициент создаёт точную делимость на R
Предварительно вычислим m′=−m⁻¹ mod R. Для 0≤T<mR положим q=Tm′ mod R и t=(T+qm)/R. Числитель делится на R, потому что T+qm≡T(1+m′m)≡0 mod R. После деления t≡TR⁻¹ mod m, поскольку добавление qm не меняет класс по m.
Кроме того, 0≤q<R и T<mR дают 0≤t<2m. Поэтому достаточно единственной коррекции: при t≥m вычесть m. Остаток по R и деление на R выполняются выделением младших битов и сдвигом; предварительное обращение остаётся отдельным этапом. Утверждение об одной коррекции зависит от указанной границы T.
Границы входа и смысл выхода проверяются отдельно
Если оба представленных множителя меньше m, их произведение меньше m²<mR, поэтому условие редукции автоматически выполнено. Для произвольного большого T оно может нарушаться: тогда одна финальная коррекция уже не доказана. Также при чётном m нельзя выбрать обратный по степени двойки R.
Метод выгоден при повторном использовании модуля, когда предварительные коэффициенты и входное преобразование окупаются. Он является арифметическим алгоритмом; сама эта формула не утверждает защиту конкретной реализации от побочных каналов. В учебном примере задача — точность остатков, корректная граница и сохранение представления.
Коррекция действительно нужна
Условие. Вычислите 4·8 mod 13 методом Монтгомери при R=16. Покажите представление входов, REDC произведения, обязательное вычитание и декодирование.
- Обратный к 13 по модулю 16 равен 5, поэтому m′=−5 mod 16=11. Представления входов: ā=4·16 mod 13=12 и b̄=8·16 mod 13=11.
- Их произведение T=132 меньше mR=208. Получаем q=132·11 mod 16=12, так что T+qm=132+156=288 точно делится на 16.
- Предварительный t=288/16=18 не находится в каноническом диапазоне. Одно вычитание 13 даёт 5 — представление произведения в координатах Монтгомери.
- Для декодирования применим REDC(5): q=55 mod 16=7, t=(5+7·13)/16=6. Это обычный остаток произведения.
- Проверка вне алгоритма: 4·8=32, 32 mod 13=6. Обратное масштабирование также согласовано: 6·16 mod 13=5.
Ответ. Представленное произведение равно 5, после декодирования обычный результат равен 6. Промежуточное 18 требует финального вычитания модуля.
Проверка. Все деления на 16 точные. Прямое произведение 32 и обратное кодирование результата независимо проверяют обе стадии и исключают смешение представленного и обычного остатка.
Где легко ошибиться. Не выдавайте āb̄R⁻¹ mod m за обычный ab mod m. После одного REDC двух представленных входов масштаб R ещё остаётся и требует декодирования.
Проверьте понимание
Вопросы к этой главе
Почему модуль должен быть нечётным при двоичном R?
Только тогда он взаимно прост со степенью двойки и имеет обратный элемент по R. Без m′ нельзя построить гарантированно делящийся числитель.
Можно ли пропустить вычитание, если сравниваются только классы?
Для класса 18 и 5 эквивалентны по 13. Но контракт канонического представления требует число меньше m; без коррекции следующий этап может нарушить доказанные границы входа.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Handbook of Applied Cryptography, §14.3: Montgomery reduction
Прочитаны факт 14.29, граница из замечания 14.33 и смысл представления xR mod m. Двухстадийный пример с обязательной коррекцией выполнен самостоятельно; машинная многословная реализация и её безопасность не заявляются проверенными.
Сертификат первообразного корня по простому модулю
Генератор мультипликативной группы простого поля можно не только испытывать степенями, но и собирать из элементов взаимно простых порядков. Произведение таких элементов объединяет независимые циклические части. Короткий сертификат затем подтверждает, что построенный элемент перебирает все ненулевые остатки.
Перед началом: Порядок элемента конечной группы; Взаимно простые числа и простые делители порядка.
Простой модуль фиксирует группу и её размер
Пусть p уже доказанно простое. Ненулевые остатки образуют коммутативную группу размера p−1, и эта группа циклическая. Первообразным корнем называют элемент порядка p−1. Это задача о генераторе уже заданного поля, а не доказательство простоты неизвестного модуля.
Если N=p−1 полностью разложено на простые множители, для кандидата g достаточно проверить g^(N/q)≠1 для каждого различного простого q|N. Порядок g делит N. Если он меньше N, то N/order(g) имеет простой делитель q и порядок делит N/q, что противоречит одной из проверок. Многократные степени одного простого не требуют отдельных одинаковых тестов.
Взаимно простые циклы можно соединить конструктивно
Пусть u и v имеют порядки r и s, НОД(r,s)=1. Они коммутируют. Если (uv)ᵏ=1, то uᵏ=v⁻ᵏ находится одновременно в подгруппах порядков r и s. Их пересечение тривиально, поскольку порядок общего элемента делит оба взаимно простых числа. Поэтому uᵏ=vᵏ=1, откуда r|k и s|k.
Следовательно, порядок uv равен rs. Этот аргумент даёт способ собрать генератор из компонентов простых степеней, вместо повторного поиска полного порядка одним неделимым кандидатом. В некоммутативной группе шаг (uv)ᵏ=uᵏvᵏ вообще неверен; здесь законность обеспечена умножением остатков поля.
Сертификат проверяет результат сборки независимо
После построения g полезно выполнить короткие тесты по простым делителям N ещё раз. Они не требуют доверять тому, как найдены компоненты u,v. Для малого p можно дополнительно перечислить все степени: отсутствие повторов до N и возврат к единице ровно на N дают наглядный независимый контроль.
Полная факторизация N является частью входных доказательных данных. Один успешный тест Ферма gᴺ=1 не доказывает генераторность: он выполняется для любого ненулевого элемента простого поля. У компонента порядка три тоже есть возврат на N, но он посещает лишь три остатка и не генерирует всю группу.
Сборка генератора из циклов длины тридцать два и три
Условие. По простому модулю p=97 возьмите u=28 и v=35. Докажите их порядки 32 и 3, постройте g=uv mod 97 и независимо подтвердите его генераторность.
- Вычисление даёт u¹⁶=96=−1 mod 97 и u³²=1. Поскольку 32 — степень двойки, отсутствие возврата на 16 исключает любой меньший делитель; порядок u равен 32.
- Для v имеем v≠1, v²=61 и v³=1 mod 97. Поэтому порядок v равен трём.
- Числа 32 и 3 взаимно просты, а остатки коммутируют. Значит, произведение g=28·35 mod 97=10 имеет порядок 96.
- Независимый сертификат использует 96=2⁵·3. Получаем 10⁴⁸=96≠1 и 10³²=61≠1, а 10⁹⁶=1. Два теста исключают все собственные делители 96.
- Перечисление 10ᵏ mod 97 для k от 0 до 95 даёт 96 различных ненулевых остатков. Следовательно, степени построенного элемента действительно покрывают всю группу.
Ответ. g=10 является первообразным корнем по модулю 97. Он собран из компонентов порядков 32 и 3 и подтверждён отдельным полнопорядковым сертификатом.
Проверка. Проверены порядки обоих компонентов, два сертификатных показателя и полный ограниченный список степеней. Эти проверки связывают конструкцию генератора с фактическим покрытием всех ненулевых остатков.
Где легко ошибиться. Не доказывайте полный порядок одним равенством g^(p−1)=1. Оно проверяет членство в группе, но не отличает её генератор от элемента малой подгруппы.
Проверьте понимание
Вопросы к этой главе
Почему достаточно показателей N/2 и N/3?
Два и три — все различные простые делители N=96. Любой собственный делитель N содержится хотя бы в одном из N/2 или N/3, поэтому иной меньший порядок был бы замечен.
Можно ли соединить тем же правилом элементы порядков четыре и шесть?
Общий вывод о порядке 24 не следует: порядки не взаимно просты. Пересечение циклических подгрупп может быть нетривиальным, и произведение способно иметь меньший порядок.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Handbook of Applied Cryptography, §2.4: generators
Прочитаны определение 2.131 и факт 2.132 о генераторах и проверках по простым делителям порядка. Конструктивная сборка двух взаимно простых циклов и пример p=97 доказаны отдельно; это не повтор сертификата простоты модуля.
Сложение точек конечной эллиптической кривой и вертикальная ветвь
Обратный остаток позволяет делить наклоны прямых в конечном поле, но сложение точек кривой не сводится к покоординатному сложению. Выведем секущую и касательную, отдельно обработаем вертикальную прямую и проверим, что результат снова принадлежит исходной кривой.
Перед началом: Обратный остаток по простому модулю; Подстановка координат в уравнение кривой.
Уравнение задаёт множество точек, но не обычную векторную сумму
Короткая форма Вейерштрасса над простым полем характеристики не 2 и не 3; малые учебные числа.
Рассматриваем E: y²=x³+ax+b над Fp, где p≥5 просто и 4a³+27b²≠0 по модулю p. Последнее условие исключает особую кубику, для которой нельзя без изменений использовать утверждение об эллиптической группе. Все конечные координаты являются остатками; рисунок вещественной кривой помогает запомнить конструкцию, но не заменяет конечнополевую арифметику.
К конечным решениям добавляется одна точка O на бесконечности. Она служит нейтральным элементом. Противоположная точка к (x,y) равна (x,−y), причём знак меняется по модулю p. Пара (0,0) не является универсальным нулём операции: она может даже не лежать на выбранной кривой.
Третье пересечение даёт формулу результата
Пусть P=(x₁,y₁), Q=(x₂,y₂) имеют разные x. Наклон m=(y₂−y₁)/(x₂−x₁) означает умножение числителя на обратный остаток знаменателя. Подстановка прямой в уравнение кубики даёт три корня по x. Два уже известны, а сравнение коэффициента при x² даёт x₃=m²−x₁−x₂. Отражение третьего пересечения задаёт y₃=m(x₁−x₃)−y₁.
При P=Q секущую заменяет касательная: m=(3x₁²+a)/(2y₁), если y₁≠0. После вычисления наклона работают те же формулы координат. Конечное поле гарантирует обратимость каждого ненулевого знаменателя, но не разрешает деление на ноль. Поэтому порядок проверки ветвей является частью математического алгоритма.
Вертикальная ветвь завершает операцию
Если x₁=x₂, у двух точек на этой кривой y₂=±y₁. При противоположных y сумма равна O. В частности, точка с y=0 совпадает со своей противоположной и при удвоении даёт O. Это корректный результат, а не ошибка входных данных или попытка вычислить бесконечный остаток.
До сложения нужно проверить принадлежность обеих точек кривой и невырожденность самой модели. После обычной ветви полезна обратная подстановка результата в y²−x³−ax−b. Она выявляет ошибки знака отражения. Эта проверка подтверждает замкнутость конкретного расчёта, но сама не доказывает ассоциативность всей операции. Общая теорема о группе требует отдельного обоснования; малые поля инструмента не оценивают безопасность криптосистем.
Секущая, касательная и противоположная точка
Условие. Над F23 задана кривая y²=x³+x+1 и точки P=(0,1), Q=(1,7). Найдите P+Q, 2P и P+(−P).
- Невырожденность: 4+27=31≡8≠0. Для P обе стороны равны 1, для Q имеем 7²=49≡3 и 1+1+1=3.
- Для секущей m=(7−1)/(1−0)=6. Получаем x₃=36−1=35≡12 и y₃=6(0−12)−1=−73≡19. Поэтому P+Q=(12,19).
- Для удвоения числитель 3·0²+1=1, знаменатель 2. Обратный к 2 равен 12, так что m=12. Координаты 2P: x=144≡6, y=12(−6)−1≡19.
- Противоположная к P точка равна (0,22). Их общая прямая вертикальна, поэтому P+(−P)=O; делить на нулевую разность x здесь не надо.
Ответ. P+Q=(12,19), 2P=(6,19), P+(−P)=O.
Проверка. Для двух конечных результатов y²≡16. При x=12 правая часть 1741≡16, при x=6 правая часть 223≡16. Независимый перебор пересечений секущей y=6x+1 даёт третью точку(12,4); её отражение имеет y=19.
Где легко ошибиться. Не заменяйте вертикальную ветвь ошибкой «обратного элемента нет». В группе точек она имеет определённый ответ O; ошибкой было бы применять обычную дробную формулу к этой ветви.
Сложение точек кривой над конечным полем
Кривая y²=x³+ax+b над простым полем5≤p≤101;4a³+27b² не равно0 modp. a,b и координаты — остатки0,…,p−1. Точка записывается как x y либо O для бесконечности. Малые учебные поля не оценивают криптографическую надёжность.
Проверьте понимание
Вопросы к этой главе
Почему нельзя просто сложить координаты P и Q?
Покоординатная сумма вообще не обязана удовлетворять кубическому уравнению. Групповая операция определена через пересечение и отражение; именно её формулы сохраняют множество точек.
Что будет при удвоении конечной точки с y=0?
Это точка порядка два: она противоположна самой себе, поэтому сумма равна O. Касательная вертикальна, и формулу с делением на 2y использовать не следует.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- MIT18.783 — Elliptic curves as abelian groups, Lecture2, §2.2
Секущая, касательная, нейтральная точка и вертикальная ветвь группового закона. Модель над F23, её координаты и независимая проверка пересечений рассчитаны отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как НОД определяет число решений линейного сравнения
Проверяем существование целых решений линейного сравнения через НОД, считаем классы по исходному модулю и восстанавливаем их после сокращения.
Открыть темуКогда в сравнении по модулю можно сократить множитель
Сокращаем множитель в сравнении по модулю с проверкой НОД и понимаем, почему обычное деление обеих сторон может потерять классы решений.
Открыть тему