Общий метод решета числового поля (GNFS англ. general number field sieve) — метод факторизации целых чисел. Метод является наиболее эффективным алгоритмом факторизации целых чисел ^[1]. Эвристическая оценка сложности факторизации числа n (содержащего log₂ n бит) выражается формулой

^[2]

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

Общий и специальный методы решета числового поля являются улучшением метода квадратичного решета.

Основные принципы

Описание работы метода даже в первом приближении сложно. Поэтому остановимся на описании принципов лежащих в его основе

• Метод факторизации Ферма для факторизации натуральных нечетных чисел n, состоящий в поиске таких целых чисел x и y, что , что ведет к разложению .
• Нахождение подмножества множества целых чисел, произведение которых — квадрат^[3]
• Факторная база: набор , где p_i — простые числа такие, что для некоторого B.
• Просеивание^[3]

Основная идея состоит в том, чтобы вместо перебора чисел и проверки, делятся ли их квадраты по модулю n на простые числа из базы, следует перебирать по очереди простые числа из базы и сразу для всех чисел вида проверять, делятся ли они на очередное p и его степени.

Метод основан на решете Эратосфена (откуда и получил своё название). Решетом служат простые числа факторной базы и дополнительно их небольшие степени, и при просеивании мы числа не вычёркиваем, а делим на эти простые. Те числа, что перейдут в 1, будут B-гладкими.

Рекордные достижения

Известные разложения наибольших чисел были получены в 1999 году. Это было сначала 140-значное RSA-число^[4], и затем 155-значное^[5], на которое потребовалось более 8000 mips лет.

Программные реализации

Проект под названием NFSNET работал с 2002^[6] до по крайней мере 2007 года. Он использовал вычислительные мощности добровольцев через Интернет.^[7]

До 2007 года наиболее успешной реализацией считалось программное обеспечение разработанное и распространяемое Центром математики и информатики в Нидерландах, который был доступен только под относительно закрытой лицензией. В 2007 году Джэйсон Пападопулус разработал более быструю открытую реализацию как часть msieve^[8]. Обе реализации пригодны для работы в кластере.

Примечания