Войти
Целочисленная факторизация - это процесс определения того, какие простые числа делят данное положительное число целое число. Быстрое выполнение этого имеет приложения в криптографии. Сложность зависит как от размера и формы числа, так и от его простых множителей ; в настоящее время очень трудно разложить на множители большие полупростые (и, действительно, большинство чисел, у которых нет малых множителей).
Первой масштабной распределенной факторизацией была RSA-129, номер вызова, описанный в статье Scientific American 1977 года, которая впервые популяризировала криптосистему RSA. В период с сентября 1993 года по апрель 1994 года он был факторизован с использованием MPQS, при этом около 600 человек предоставили информацию через Интернет, а заключительные этапы расчета были выполнены на суперкомпьютере MasPar в Bell Labs.
В период с января по август 1999 г. RSA-155, номер вызова, подготовленный компанией RSA, был разложен на множители с использованием GNFS, и отношения снова были внесены большой группой, и заключительные этапы вычислений, выполненные чуть более чем за девять дней на суперкомпьютере Cray C916 в Академическом компьютерном центре SARA Amsterdam.
В январе 2002 г. Franke et al. объявила о факторизации 158-значного кофактора 2 + 1 за пару месяцев примерно на 25 ПК в Боннском университете, а заключительные этапы были выполнены с использованием кластера из шести компьютеров Pentium-III.
В апреле 2003 года та же группа произвела факторизацию RSA-160, используя около сотни процессоров в BSI, при этом заключительные этапы вычислений были выполнены с использованием 25 процессоров SGI Origin суперкомпьютер.
576-битный RSA-576 был факторизован Франке, Кляйнджунгом и участниками сотрудничества NFSNET в декабре 2003 года с использованием ресурсов BSI и Боннского университета. ; вскоре после этого Аоки, Кида, Симояма, Сонода и Уэда объявили, что они учли множитель 2 + 1 из 164 цифр.
176-значный кофактор 11 + 1 был разложен на множители Аоки, Кида, Симояма и Уэда в период с февраля по май 2005 г. с использованием машин в NTT и Университете Рикке в Япония.
663-битный RSA-200 номер вызова был учтен Franke, Kleinjung et al. с декабря 2003 г. по май 2005 г. с использованием кластера из 80 процессоров Opteron в BSI в Германии; объявление было сделано 9 мая 2005 г. Они позже (ноябрь 2005 г.) учли немного меньший номер вызова RSA-640.
12 декабря 2009 г. группа исследователей из CWI, EPFL, INRIA и NTT в дополнение к авторам предыдущая запись факторизовала RSA-768, 232-значное полупростое число. Они использовали эквивалент почти 2000 лет вычислений на одном ядре 2,2 ГГц AMD Opteron.
В ноябре 2019 года 795-битный RSA-240 был учтен Фабрис Будо, Пьерк Годри, Аврора Гильевич, Надя Хенингер, Эммануэль Томе и Поль Циммерманн.
В феврале 2020 года факторизация 829-битного RSA-250 была завершена.
12 - 1, из 542 бит (163 цифры), были учтены в период с апреля по июль 1993 года группой из CWI и штата Орегон. Университет.
2 + 1 из 774 битов (233 цифры) был разложен на множители с апреля по ноябрь 2000 года The Cabal, при этом шаг матрицы, выполненный на Cray за 250 часов, также использовался для RSA-155.
2 - 1 из 809 бит (244 цифры) было объявлено о факторизации в начале января 2003 года. Просеивание проводилось в CWI, в Научно-вычислительном институте и на факультете чистой математики Боннского университета с использованием частных ресурсы J. Franke, T. Kleinjung и семьи ly Ф. Бахра. Шаг линейной алгебры был выполнен П. Монтгомери в SARA в Амстердаме.
6 - 1 из 911 бит (275 цифр) было вычислено Аоки, Кидой, Симоямой и Уэдой в период с сентября 2005 г. по январь 2006 г. с использованием SNFS.
2 - 1 из 1039 бит (313 цифр) (хотя множитель в 23 бита уже был известен) был учтен в период с сентября 2006 г. по май 2007 г. группой, в которую входили К. Аоки, Дж. Франке, Т. Кляйнджунг, А. К. Ленстра и Д.А. Освик, используя компьютеры в NTT, EPFL и Боннском университете.
2-1, из 1061 бит (320 цифр) был факторизован в период с начала 2011 года по 4 августа 2012 года группой во главе с Грегом Чайлдерсом из CSU Fullerton, использовавшей проект nfs @ home BOINC в течение примерно 300 процессорных лет просеивания; линейная алгебра была запущена в кластере Trestles в SDSC и кластере Lonestar в TACC, и потребовалось дополнительно 35 процессорных лет.
Все не подвергавшиеся факторизации части чисел 2 - 1 с n от 1000 до 1200 были разложены на множители Подход с использованием нескольких сит, при котором большая часть этапа просеивания может выполняться одновременно для нескольких номеров группой, в которую входят Т. Кляйнджунг, Дж. Бос и А. К. Ленстра, начиная с 2010 г. Если быть точным, n = 1081 завершено 11 марта 2013 г.; n = 1111 на 13 июня 2013 г.; n = 1129 на 20 сентября 2013 г.; n = 1153 - 28 октября 2013 г.; n = 1159 на 9 февраля 2014 г.; 1177 29 мая 2014 г., n = 1193 22 августа 2014 г. и n = 1199 11 декабря 2014 г.; первое подробное объявление было сделано в конце августа 2014 года. Общие усилия по проекту составляют порядка 7500 процессорных лет на 2,2 ГГц Opteron, из которых примерно 5700 лет на просеивание и 1800 лет на линейную алгебру.
По состоянию на конец 2007 года, благодаря постоянному снижению цен на память, доступности многоядерных 64-разрядных компьютеров и доступности эффективный код просеивания (разработанный Торстеном Кляйнджунгом из Боннской группы) через ggnfs и надежное программное обеспечение с открытым исходным кодом, такое как msieve для этапов чистовой обработки, номера специальной формы до 750 бит и числа общей формы примерно до 520 бит может быть разложен за несколько месяцев на нескольких компьютерах одним человеком без какого-либо специального математического опыта. Эти пределы увеличиваются примерно до 950 и 600, если можно было обеспечить совместную работу нескольких десятков ПК для просеивания; в настоящее время объем памяти и мощность процессора одной машины для финального этапа являются равными препятствиями на пути прогресса.
В 2009 году Бенджамин Муди факторизовал 512-битный ключ RSA, используемый для подписи графического калькулятора TI-83, используя программное обеспечение, найденное в Интернете; в конечном итоге это привело к спору о подписании ключей Texas Instruments.
В сентябре 2013 года 696-битный RSA-210 был факторизован Райаном Проппером с использованием институциональных ресурсов; в период с марта 2013 г. по октябрь 2014 г. еще одно 210-значное число (117-й член в «домашней простой последовательности», начинающееся с 49) было введено пользователем, известным как WraithX, с затратами на обработку на машинах Amazon EC2 для просеивания на сумму 7600 долларов. и четыре месяца на двойном Xeon E5-2687W v1 для линейной алгебры.
Наибольшее число, учтенное алгоритмом Шора, составило 21 в 2012 году. 15 ранее были учтены несколькими лабораториями.
В апреле 2012 г. факторизация 
