Записи целочисленной факторизации - Integer factorization records

Целочисленная факторизация это процесс определения простые числа разделить данный положительный целое число. Быстрое выполнение этой задачи имеет приложения в криптография. Сложность зависит как от размера и формы номера, так и от его главные факторы; в настоящее время очень сложно разложить на множители большие полупростые (и, действительно, большинство чисел, которые не имеют малых множителей).

Номера общего вида

Первая огромная распределенная факторизация была 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-значного кофактора 2953+1, потратив пару месяцев примерно на 25 ПК на Боннский университет, причем заключительные этапы выполняются с использованием кластера из шести компьютеров Pentium-III.

В апреле 2003 года та же команда учла RSA-160 используя около сотни процессоров на BSI, при этом заключительные этапы расчета выполняются с использованием 25 процессоров SGI Источник суперкомпьютер.

576-битный RSA-576 было учтено Франке, Кляйнджунгом и членами NFSNET сотрудничество в декабре 2003 г. с использованием ресурсов BSI и Боннского университета; вскоре после этого Аоки, Кида, Симояма, Сонода и Уэда объявили, что они разложили на множители 164-значный кофактор 21826+1.

176-значный сомножитель 11281+1 было учтено Аоки, Кидой, Симоямой и Уэдой в период с февраля по май 2005 г. с использованием машин в NTT и Университет Риккё в Японии.[1]

663-битный RSA-200 номер провокации был учтен Franke, Kleinjung et al. с декабря 2003 г. по май 2005 г. с использованием кластера из 80 процессоров Opteron в BSI в Германии; Объявление было сделано 9 мая 2005 г.[2] Позже (ноябрь 2005 г.) они учли немного меньший RSA-640 номер вызова.

12 декабря 2009 г. команда исследователей из CWI, то EPFL, INRIA и NTT в дополнение к авторам предыдущего рекорда RSA-768, 232-значное полупростое число.[3] Они использовали эквивалент почти 2000 лет вычислений на одном ядре 2,2 ГГц. AMD Opteron.

В ноябре 2019 года 795-битный RSA-240 Факторами выступили Фабрис Будо, Пьер Годри, Аурора Гильевич, Надя Хенингер, Эммануэль Томе и Поль Циммерманн.[4][5]

В феврале 2020 года факторизация 829-битного РСА-250 было выполнено.[6]

Номера особой формы

12151 - 1 из 542 бит (163 цифры) был разложен на множители в период с апреля по июль 1993 г. CWI и Государственный университет Орегона.[7]

2773 + 1 из 774 бит (233 цифры) был разложен на множители с апреля по ноябрь 2000 года The Cabal, при этом шаг матрицы, выполненный на Cray за 250 часов, также использовался для RSA-155.[8]

2809 Факторизация - 1 из 809 бит (244 цифры) была объявлена ​​в начале января 2003 года. Просеивание проводилось в CWI, в Научно-вычислительном институте и на факультете чистой математики Боннского университета с использованием частных ресурсов J. Franke, T. Kleinjung и семья F. Bahr. Шаг по линейной алгебре был сделан П. Монтгомери в SARA в Амстердаме.[9]

6353 - 1 из 911 битов (275 цифр) был разложен на множители Аоки, Кида, Симояма и Уэда в период с сентября 2005 г. по январь 2006 г. с использованием SNFS.[10]

21039 - 1 из 1039 бит (313 цифр) (хотя коэффициент 23 бита уже был известен) был разложен на множители в период с сентября 2006 г. по май 2007 г. группой, в которую входили К. Аоки, Дж. Франке, Т. Кляйнджунг, А. К. Ленстра и Д. А. Освик, используя компьютеры в NTT, EPFL и Боннский университет.[11][12]

21061 - 1 из 1061 бит (320 цифр) был факторизован в период с начала 2011 года по 4 августа 2012 года группой, возглавляемой Грегом Чайлдерсом из CSU Fullerton, с использованием nfs @ home BOINC проект около 300 процессорных лет просеивания; линейная алгебра была запущена в кластере Trestles в SDSC и кластере Lonestar в TACC и потребовала дополнительных 35 процессорных лет.[13]

Все непакторные части чисел 2п - 1 с n от 1000 до 1200 были разложены на многовариантный метод сита, при котором большая часть этапа просеивания могла выполняться одновременно для нескольких чисел, группой, включающей Т. Кляйнджунг, Дж. Бос и А. К. Ленстра, начиная с 2010 г.[14] Если быть точным, 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[15] и надежного программного обеспечения с открытым исходным кодом, такого как msieve[16] для этапов чистовой обработки числа особой формы до 750 бит и числа общей формы до примерно 520 бит могут быть разложены за несколько месяцев на нескольких ПК одним человеком без какого-либо специального математического опыта.[17] Эти границы увеличиваются примерно до 950[18] и 600[19] если бы можно было обеспечить совместную работу нескольких десятков ПК для просеивания; в настоящее время объем памяти и мощность процессора одной машины для финального этапа являются равными препятствиями на пути прогресса.

В 2009 году Бенджамин Муди учел 512-битный ключ RSA, используемый для подписи ТИ-83 графический калькулятор с использованием программного обеспечения, найденного в Интернете; это в конечном итоге привело к Споры по поводу подписи Texas Instruments.

В сентябре 2013 года 696-битный RSA-210 Факторизовал Райан Проппер[20] использование институциональных ресурсов; в период с марта 2013 г. по октябрь 2014 г. еще одно 210-значное число (117-й член в «домашней простой последовательности», начинающееся с 49) было введено пользователем, известным как WraithX,[21] время обработки на машинах Amazon EC2 составляет 7600 долларов.[22] для просеивания и четыре месяца на двойном Xeon E5-2687W v1 для линейной алгебры.

Рекорды по усилиям квантовых компьютеров

Наибольшее число, учтенное Алгоритм Шора было 35 лет, используя IBM Q System One квантовый компьютер в 2019 году.[23] Ранее это был 21 год в 2012 году.[24] 15 ранее были проанализированы несколькими лабораториями.

В апреле 2012 г. факторизация методом ЯМР при комнатной температуре (300 К) адиабатический квантовый компьютер Об этом сообщила группа под руководством Синьхуа Пэна.[25] В ноябре 2014 года его обнаружил Найк Даттани и Натан Брайанс, что в эксперименте 2012 года фактически были учтены гораздо большие числа, не зная об этом.[26][27] В апреле 2016 года 18-битное число 200 099 было факторизовано с использованием квантовый отжиг на D-волна 2X квантовый процессор.[28] Вскоре после этого 291 311 был разложен с использованием ЯМР при температуре выше комнатной.[29] В конце 2019 года отраслевое сотрудничество обнаружило, что 1 099 551 473 989 равно 1 048 589, умноженному на 1048 601. [30]

Смотрите также

Рекомендации

  1. ^ К. Аоки; Ю. Кида; Т. Симояма; Х. Уэда. «Факторизация 176-значного числа». Получено 2007-05-23.
  2. ^ Ф. Бахр; М. Бем; Дж. Франке; T. Kleinjung. «RSA200». Получено 2007-05-23.
  3. ^ Т. Кляйнджунг; К. Аоки; Дж. Франке; А. К. Ленстра; Э. Томе; J. W. Bos; П. Годри; А. Круппа; П. Л. Монтгомери; Д. А. Освик; Х. те Риле; А. Тимофеев; П. Циммерманн. «Факторизация 768-битного модуля RSA» (PDF). Получено 2013-04-11.
  4. ^ https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-De December/001139.html
  5. ^ Ф. Будо и др., «Сравнение сложности факторизации и дискретного логарифма: 240-значный эксперимент», 10 июня 2020 г.
  6. ^ https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;dc42ccd1.2002
  7. ^ П. Л. Монтгомери. "Факторизация поля сита рекордов". Получено 2007-11-23.
  8. ^ «Кабала». «233-значная факторизация SNFS». Архивировано из оригинал на 2007-11-28. Получено 2007-11-23.
  9. ^ J. Franke. «М809». Архивировано из оригинал на 2007-08-23. Получено 2007-11-23.
  10. ^ К. Аоки; Ю. Кида; Т. Симояма; Х. Уэда. "SNFS274". Получено 2007-05-23.
  11. ^ К. Аоки; Дж. Франке; Т. Кляйнджунг; А. К. Ленстра; Освик Д.А. "Факторизация 1039-го числа Мерсенна". Получено 2007-05-23.
  12. ^ Казумаро Аоки; Йенс Франке; Торстен Кляйнджунг; Арьен Ленстра; Даг Арне Освик. "Факторизация поля сита специального числа килобита". Получено 2007-12-19.
  13. ^ Грег Чайлдерс. «Факторизация 1061-битного числа ситом специального числового поля».
  14. ^ Торстен Кляйнджунг; Йоппе В Бос; Арьен К. Ленстра. «Фабрика факторизации Мерсенна». Получено 2015-01-18.
  15. ^ «Пакет GGNFS - Просмотр файлов на SourceForge.net». sourceforge.net.
  16. ^ «Архивная копия». Архивировано из оригинал на 2007-12-13. Получено 2007-11-23.CS1 maint: заархивированная копия как заголовок (связь)
  17. ^ "mersenneforum.org - Просмотреть отдельное сообщение - Таблица 2LM". www.mersenneforum.org.
  18. ^ "mersenneforum.org - Просмотреть отдельное сообщение - Вычисление, достойное своего названия". www.mersenneforum.org.
  19. ^ "mersenneforum.org - Просмотреть отдельное сообщение - 5 ^ 421-1 просеивание (резервирование закрыто)". www.mersenneforum.org.
  20. ^ "Фактор RSA-210 - mersenneforum.org". mersenneforum.org.
  21. ^ "mersenneforum.org - Просмотреть отдельное сообщение - HP49 (119) ..." www.mersenneforum.org.
  22. ^ https://mersenneforum.org/showpost.php?p=389078&postcount=105
  23. ^ Амико, Мирко; Saleem, Zain H .; Кумф, Мьюир (2019-07-08). "Экспериментальное исследование алгоритма факторинга Шора на IBM Q". Физический обзор A. 100 (1): 012305. Дои:10.1103 / PhysRevA.100.012305. ISSN  2469-9926.
  24. ^ Мартин-Лопес, Энрике; Энрике Мартин-Лопес; Энтони Лэйнг; Томас Лоусон; Роберто Альварес; Сяо-Ци Чжоу; Джереми Л. О'Брайен (12 октября 2012 г.). «Экспериментальная реализация квантового алгоритма факторизации Шора с использованием рециклинга кубитов». Природа Фотоника. 6 (11): 773. arXiv:1111.4147. Bibcode:2012НаФо ... 6..773M. Дои:10.1038 / nphoton.2012.259.
  25. ^ «143 - это наибольшее число, которое квантовый алгоритм еще не учел».
  26. ^ «Новое наибольшее число, учтенное на квантовом устройстве, - 56 153».
  27. ^ «Математический трюк, который помог побить рекорд самого большого числа, когда-либо разложенного на ...» 2 декабря 2014 г.
  28. ^ Дриди, Рауф; Альгаси, Хедаят (21 февраля 2017 г.). «Факторизация простых чисел с использованием квантового отжига и вычислительной алгебраической геометрии». Научные отчеты. 7: 43048. arXiv:1604.05796. Bibcode:2017НатСР ... 743048D. Дои:10.1038 / srep43048. ЧВК  5318873. PMID  28220854.
  29. ^ Ли, Чжаокай; Даттани, Найк; Чен, Си; Лю, Сяомэй; Ван, Хэнъянь; Танберн, Ричард; Чен, Хунвэй; Пэн, Синьхуа; Ду Цзянфэн (25 июня 2017 г.). «Высокоточные адиабатические квантовые вычисления с использованием внутреннего гамильтониана спиновой системы: приложение к экспериментальной факторизации 291311». arXiv:1706.08061.
  30. ^ Крейн, Лия. «Квантовый компьютер устанавливает новый рекорд в нахождении множителей простых чисел». Новый ученый. Получено 2020-10-02.