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

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

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

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

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

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

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

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

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

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

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

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

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