Рекорды факторизации целых чисел

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

Числа общего вида

Первой очень большой распределенной факторизацией была факторизация RSA-129. Это число было разложено между сентябрем 1993 года и апрелем 1994 года методом квадратичного решета. В распределенных вычислениях через Интернет участвовало около 600 добровольцев, а финальные вычисления проводились на суперкомпьютере MasPar.

Между январем и августом 1999 года с использованием общего метода решета числового поля было факторизовано RSA-155. Вычисления снова производились с привлечением большого количества людей, а финальные вычисления — на суперкомпьютере C916.

В апреле 2003 года Франке и другие объявили о факторизации RSA-160. При разложении использовалось около сотни CPU.

В декабре 2003 Франке, Клеинджанг факторизовали 174-значное число, используя ресурсы BSI и Боннского университета.

В мае 2005 176-значный сомножитель числа 11²⁸¹ + 1 был найден Аоки, Кида, Шимоямой и Уедой NTT и Риккёским университетом в Японии.

Числа специального вида

12¹⁵¹ − 1, число из 163 десятичных знаков (542 бита), было разложено между апрелем и июлем 1993 года.

См. также

• RSA-числа