В теории чисел , Алгоритм Диксон (также методы Диксона случайных квадратов [1] или алгоритм Диксона ) является универсальной целым числом факторизационного алгоритма ; это прототип метода факторной базы . В отличие от других методов факторной базы, его оценка времени выполнения сопровождается строгим доказательством, которое не основывается на предположениях о свойствах гладкости значений, принимаемых полиномом.
Алгоритм был разработан Джоном Д. Диксоном , математиком из Карлтонского университета , и был опубликован в 1981 г. [2]
Основная идея
Метод Диксона основан на нахождении сравнения квадратов по модулю целого числа N, которое предполагается факторизовать. Метод факторизации Ферма находит такое совпадение, выбирая случайные или псевдослучайные значения x и надеясь, что целое число x 2 mod N является полным квадратом (в целых числах):
Например, если N = 84923 (начиная с 292, первое число больше √ N и считая), 505 2 по модулю 84923 будет 256, квадрат 16. Итак ( 505-16 ) (505 + 16) = 0 мод 84923 . Вычисление наибольший общий делитель из 505 - 16 и Н с помощью алгоритма Евклида дает 163, который представляет собой фактор N .
На практике выбора случайных х значений будет принимать непрактично долгое время , чтобы найти конгруэнтность квадратов, так как существует только √ N квадратов меньше , чем N .
Метод Диксона заменяет условие «является квадратом целого числа» гораздо более слабым условием «имеет только малые простые множители»; например, есть 292 квадрата меньше 84923; 662 числа меньше 84923, простые делители которых равны только 2,3,5 или 7; и 4767, у которых все простые множители меньше 30 (такие числа называются B-гладкими относительно некоторой границы B. )
Если есть много цифр квадраты которого можно разложить на множители как для фиксированного набора малых простых чисел, линейная алгебра по модулю 2 на матрице даст подмножество квадраты которых в сумме дают произведение малых простых чисел на четную степень, то есть подмножество чьи квадраты умножаются на квадрат (надеюсь, другого) числа по модулю N.
Метод
Предположим, что составное число N разложено на множители. Связанный Б выбран, и коэффициент базовый идентифицируются (которая называется Р ), множество всех простых чисел меньше или равно B . Затем ищутся натуральные числа z такие, что z 2 mod N является B- гладким. Поэтому она может быть записана, подходящих для показателей я ,
Когда сформировано достаточное количество этих отношений (обычно достаточно, чтобы количество отношений было на несколько больше, чем размер P ), можно использовать методы линейной алгебры (например, метод исключения Гаусса ) для умножения этих различных соотношений. таким образом, чтобы показатели простых чисел в правой части были четными:
Это дает сравнение квадратов вида a 2 ≡ b 2 (mod N ), которое можно превратить в факторизацию N , N = gcd ( a + b , N ) × ( N / gcd ( a + b , N )). Эта факторизация может оказаться тривиальной (т. Е. N = N × 1 ), что может произойти, только если a ± b (mod N ), и в этом случае нужно сделать еще одну попытку с другой комбинацией отношений; но может быть достигнута нетривиальная пара множителей N , и алгоритм завершится.
Псевдокод
ввод: положительное целое числовыход: нетривиальный фактор Выберите границу Позволять все простые числа повторить для к делать Выберите такой, что является -гладкий Позволять такой, что конец для Найти непустой такой, что Позволять пока возвращаться
Пример
В этом примере будет предпринята попытка разложить на множители N = 84923, используя границу B = 7. Тогда факторная база будет P = {2, 3, 5, 7}. Можно выполнить поиск целых чисел междуи N , квадраты моды N является B -гладким . Предположим, что два из найденных чисел - 513 и 537:
Так
потом
Это,
Результирующая факторизация: 84923 = НОД (20712 - 16800, 84923) × НОД (20712 + 16800, 84923) = 163 × 521.
Оптимизация
Квадратичное решето является оптимизация метода Диксона. Он выбирает значения x, близкие к квадратному корню из N , так что x 2 по модулю N мало, что значительно увеличивает шанс получения гладкого числа.
Другие способы оптимизации метода Диксона включают использование более совершенного алгоритма для решения матричного уравнения, используя в своих интересах разреженность матрицы: число z не может иметь больше, чемфакторов, поэтому в каждой строке матрицы почти все нули. На практике часто используется блочный алгоритм Ланцоша . Кроме того, необходимо тщательно выбирать размер факторной базы: если она слишком мала, будет трудно найти числа, которые полностью разлагаются на нее, а если она слишком велика, придется собрать больше соотношений.
Более сложный анализ, использующий приближение того, что все простые множители числа меньше, чем с вероятностью около (приближение к функции Дикмана – де Брейна ), указывает на то, что выбор слишком маленькой факторной базы намного хуже, чем слишком большой, и что идеальный размер факторной базы - это некоторая степень.
Оптимальная сложность метода Диксона составляет
в нотации большого O , или
в L-обозначении .
Рекомендации
- ^ Кляйнджунг, Торстен; и другие. (2010). «Факторизация 768-битного модуля RSA». Достижения в криптологии - CRYPTO 2010 . Конспект лекций по информатике. 6223 . С. 333–350. DOI : 10.1007 / 978-3-642-14623-7_18 . ISBN 978-3-642-14622-0.
- ^ Диксон, JD (1981). «Асимптотически быстрая факторизация целых чисел» . Математика. Комп. 36 (153): 255–260. DOI : 10.1090 / S0025-5718-1981-0595059-1 . JSTOR 2007743 .