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

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

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

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

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

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

Алгоритмы [ править ]

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

Ссылки [ править ]