Факторная база

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

Использование в алгоритмах факторинга

Факторная база — это относительно небольшой набор различных простых чисел P , иногда вместе с -1. ^[1] Скажем, мы хотим факторизовать целое число n . Мы каким-то образом генерируем большое количество пар целых чисел ( x , y ), для которых $x\neq \pm y$ , $x^{2}\equiv y^{2}{\pmod {n}}$ , и $x^{2}{\pmod {n}}{\text{ and }}y^{2}{\pmod {n}}$ могут быть полностью факторизованы по выбранной факторной базе, то есть все их простые факторы находятся в P .

На практике несколько целых чисел x таких, что находятся $x^{2}{\pmod {n}}$ имеет все свои основные факторы в заранее выбранной факторной базе. Мы представляем каждого $x^{2}{\pmod {n}}$ выражение в виде вектора матрицы с целочисленными элементами , являющимися показателями факторов в базе факторов. Линейное сочетание строк соответствует умножению этих выражений. Отношение линейной зависимости по модулю 2 между строками приводит к желаемому сравнению $x^{2}\equiv y^{2}{\pmod {n}}$ . ^[2] По сути, это переформулирует проблему в систему линейных уравнений , которую можно решить, используя многочисленные методы, такие как метод исключения Гаусса ; на практике используются продвинутые методы, такие как блочный алгоритм Ланцоша , которые используют преимущества определенных свойств системы.

Это сравнение может породить тривиальное $\textstyle n=1\cdot n$ ; в этом случае мы пытаемся найти другое подходящее сравнение. Если повторные попытки факторизации окажутся неудачными, мы можем попробовать еще раз, используя другую факторную базу.

Алгоритмы

Факторные базы используются, например, в факторизации Диксона , квадратичном сите и сите числового поля . Разница между этими алгоритмами по существу заключается в методах, используемых для генерации ( x , y ) кандидатов. Факторные базы также используются в алгоритме исчисления индексов для вычисления дискретных логарифмов. ^[3]

Ссылки

^ Коблиц, Нил (1987), Курс теории чисел и криптографии , Springer-Verlag, стр. 133, ISBN 0-387-96576-9
^ Траппе, Уэйд; Вашингтон, Лоуренс К. (2006), Введение в криптографию с теорией кодирования (2-е изд.), Прентис-Холл, стр. 185, ISBN 978-0-13-186239-5
^ Стинсон, Дуглас Р. (1995), Криптография/Теория и практика , CRC Press, стр. 171, ISBN 0-8493-8521-0

[1] Коблиц, Нил (1987), Курс теории чисел и криптографии , Springer-Verlag, стр. 133, ISBN 0-387-96576-9

[2] Траппе, Уэйд; Вашингтон, Лоуренс К. (2006), Введение в криптографию с теорией кодирования (2-е изд.), Прентис-Холл, стр. 185, ISBN 978-0-13-186239-5

[3] Стинсон, Дуглас Р. (1995), Криптография/Теория и практика , CRC Press, стр. 171, ISBN 0-8493-8521-0

[1]

[2]

[3]