Алгоритм факторизации алгебраических групп

редактировать

Алгоритмы факторизации алгебраических групп - это алгоритмы разложения целого числа N на множители при работе в алгебраической группе определено по модулю N, чья групповая структура является прямой суммой «редуцированных групп», полученных путем выполнения уравнений, определяющих групповую арифметику по модулю неизвестных простых множителей p 1, p 2,... Согласно китайской теореме об остатках, арифметика по модулю N соответствует арифметике во всех редуцированных группах одновременно.

Цель состоит в том, чтобы найти элемент, который не является тождеством группы по модулю N, но является тождеством по модулю одного из факторов, поэтому требуется метод распознавания таких односторонних идентичностей. В общем, их находят, выполняя операции, которые перемещают элементы и оставляют идентичности в сокращенных группах неизменными. Как только алгоритм найдет одностороннюю идентичность, все будущие термины также будут односторонними идентичностями, поэтому периодической проверки будет достаточно.

Вычисление продолжается путем выбора произвольного элемента x группы по модулю N и вычисления его большого и гладкого кратного Ax; если порядок хотя бы одной, но не всех редуцированных групп является делителем A, это дает факторизацию. Это не обязательно должно быть разложение на простые множители, поскольку элемент может быть тождеством более чем в одной сокращенной группе.

Обычно A берется как произведение простых чисел ниже некоторого предела K, а Ax вычисляется путем последовательного умножения x на эти простые числа; после каждого умножения или каждых нескольких умножений выполняется проверка односторонней идентичности.

Двухэтапная процедура

Часто можно умножить групповой элемент на несколько небольших целых чисел быстрее, чем на их произведение, обычно с помощью методов, основанных на различиях; вычисляется разность между последовательными простыми числами и последовательно складывается по d i r {\ displaystyle d_ {i} r}d_i г . Это означает, что становится разумной двухэтапная процедура: сначала вычисляется Ax путем умножения x на все простые числа ниже предела B1, а затем проверяется p Ax для всех простых чисел от B1 до большего предела B2.

Методы, соответствующие конкретным алгебраическим группам

Если алгебраическая группа является мультипликативной группой mod N, односторонние тождества распознаются путем вычисления наибольших общих делителей с N, и результатом будет метод p - 1.

Если алгебраическая группа является мультипликативной группой квадратичного расширения N, результатом будет метод p + 1 ; при вычислении используются пары чисел по модулю N. Невозможно определить, Z / NZ [t] {\ displaystyle \ mathbb {Z} / N \ mathbb {Z} [{\ sqrt {t}}]}\ mathbb Z / N \ mathbb Z [\ sqrt t] на самом деле является квадратичным расширением N без знания факторизации. Для этого необходимо знать, является ли t квадратичным остатком по модулю N, и не существует известных способов сделать это без знания факторизации. Однако при условии, что N не имеет очень большого количества факторов, и в этом случае сначала следует использовать другой метод, выбор случайного t (или, скорее, выбор A с t = A - 4) довольно быстро случайно попадет в квадратичный невычет. Если t - квадратичный вычет, метод p + 1 вырождается в более медленную форму метода p - 1.

Если алгебраическая группа представляет собой эллиптическую кривую, односторонние тождества могут быть распознаны по ошибке инверсии в процедуре добавления точек эллиптической кривой, и результатом является метод эллиптической кривой ; Теорема Хассе утверждает, что количество точек на эллиптической кривой по модулю p всегда находится в пределах 2 p {\ displaystyle 2 {\ sqrt {p}}}2 {\ sqrt p} от p.

Все три вышеупомянутые алгебраические группы используются пакетом GMP-ECM, который включает эффективные реализации двухэтапной процедуры и реализацию алгоритма возведения в степень группы PRAC, который является более эффективным, чем стандартный подход бинарного возведения в степень.

Использование других алгебраических групп - расширений высшего порядка N или групп, соответствующих алгебраическим кривым высшего рода - иногда предлагается, но почти всегда непрактично. Эти методы заканчиваются ограничениями гладкости для чисел порядка p для некоторого d>1, которые с гораздо меньшей вероятностью будут гладкими, чем числа порядка p.

Последняя правка сделана 2021-06-10 22:35:10
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте