Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Числа общего вида [ править ]

Первой масштабной распределенной факторизацией была RSA-129 , номер вызова, описанный в статье Scientific American 1977 года, которая впервые популяризировала криптосистему RSA. Он был разложен на множители в период с сентября 1993 года по апрель 1994 года с использованием MPQS , при этом около 600 человек предоставили информацию через Интернет, а последние этапы расчета были выполнены на суперкомпьютере MasPar в Bell Labs.

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

В январе 2002 г. Franke et al. объявила о факторизации 158-значного кофактора 2 953 +1 за пару месяцев примерно на 25 ПК в Боннском университете , а заключительные этапы были выполнены с использованием кластера из шести компьютеров Pentium-III.

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

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

176-значный кофактор 11 281 +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 лет вычислений на одноядерном процессоре AMD Opteron 2,2 ГГц .

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

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

Номера особой формы [ править ]

12 151  - 1, из 542 бит (163 цифры), было вычислено в период с апреля по июль 1993 года группой из CWI и Университета штата Орегон . [7]

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

В  начале января 2003 г. было объявлено о факторизации 2 809 - 1 из 809 бит (244 цифры). Просеивание проводилось в CWI, в Научно-вычислительном институте и на факультете чистой математики Боннского университета с использованием частных ресурсов Дж. Франке, Т. Кляйнджунг и семья Ф. Бахра. Шаг по линейной алгебре был выполнен П. Монтгомери в SARA в Амстердаме. [9]

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

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

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

Все нефакторные части чисел 2 n  - 1 с n от 1000 до 1200 были разложены на множители с помощью метода множественных сит, при котором большая часть этапа просеивания могла выполняться одновременно для нескольких чисел, группой, включающей T. Kleinjung, J Бос и А.К. Ленстра , начиная с 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, используемый для подписи графического калькулятора TI-83, используя программное обеспечение, найденное в Интернете; это в конечном итоге привело к ключевому спору о подписании Texas Instruments .

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

Записи об усилиях квантовых компьютеров [ править ]

Наибольшее число, надежно разложенное алгоритмом Шора, - 21, которое было разложено на множители в 2012 году. [23] 15 ранее были разложены в нескольких лабораториях.

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

См. Также [ править ]

  • Наибольшее известное простое число

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

  1. ^ К. Аоки; Ю. Кида; Т. Симояма; Х. Уэда. «Факторизация 176-значного числа» . Проверено 23 мая 2007 .
  2. ^ Ф. Бахр; М. Бем; Дж. Франке; T. Kleinjung. «RSA200» . Проверено 23 мая 2007 .
  3. ^ Т. Кляйнджунг; К. Аоки; Дж. Франке; АК Ленстра; Э. Томе; JW Bos; П. Годри; А. Крупа; П.Л. Монтгомери; Д.А. Освик; Х. те Риле; А. Тимофеев; П. Циммерманн. «Факторизация 768-битного модуля RSA» (PDF) . Проверено 11 апреля 2013 .
  4. ^ https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-De December / 001139.html
  5. ^ F. Boudot и др., «Сравнение сложности факторизации и дискретного логарифма: 240-значный эксперимент», 10 июня 2020 г.
  6. ^ https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;dc42ccd1.2002
  7. ^ PL Монтгомери. "Факторизация поля сита рекордов" . Проверено 23 ноября 2007 .
  8. ^ «Кабала». «233-значная факторизация SNFS» . Архивировано из оригинала на 2007-11-28 . Проверено 23 ноября 2007 .
  9. ^ J. Franke. «М809» . Архивировано из оригинала на 2007-08-23 . Проверено 23 ноября 2007 .
  10. ^ К. Аоки; Ю. Кида; Т. Симояма; Х. Уэда. «SNFS274» . Проверено 23 мая 2007 .
  11. ^ К. Аоки; Дж. Франке; Т. Кляйнджунг; АК Ленстра; Д.А. Освик. «Факторизация 1039-го числа Мерсенна» . Проверено 23 мая 2007 .
  12. ^ Kazumaro Aoki; Йенс Франке; Торстен Кляйнджунг; Арьен Ленстра; Даг Арне Освик. «Факторизация сита специального номера килобита» . Проверено 19 декабря 2007 .
  13. ^ Грег Чайлдерс. «Факторизация 1061-битного числа ситом специального числового поля» .
  14. ^ Thorsten Kleinjung; Йоппе В Бос; Арьен К. Ленстра. "Фабрика факторизации Мерсенна" . Проверено 18 января 2015 .
  15. ^ «Набор GGNFS - Просмотр файлов на SourceForge.net» . sourceforge.net .
  16. ^ "Архивная копия" . Архивировано из оригинала на 2007-12-13 . Проверено 23 ноября 2007 .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. ^ Мартин-Лопес, Энрике; Энрике Мартин-Лопес; Энтони Лэйнг; Томас Лоусон; Роберто Альварес; Сяо-Ци Чжоу; Джереми Л. О'Брайен (12 октября 2012 г.). «Экспериментальная реализация алгоритма квантового факторизации Шора с использованием рециклинга кубитов». Природа Фотоника . 6 (11): 773. arXiv : 1111.4147 . Bibcode : 2012NaPho ... 6..773M . DOI : 10.1038 / nphoton.2012.259 .
  24. ^ «143 - это наибольшее число, которое еще не учтено квантовым алгоритмом» .
  25. ^ «Новое наибольшее число, учтенное на квантовом устройстве, - 56 153» .
  26. ^ «Математический трюк, который помог побить рекорд самого большого числа, когда-либо факторизованного A ...» 2 декабря 2014 г.
  27. ^ Дриди, Рауф; Альгаси, Хедаят (21 февраля 2017 г.). «Факторизация простых чисел с использованием квантового отжига и вычислительной алгебраической геометрии» . Научные отчеты . 7 : 43048. arXiv : 1604.05796 . Bibcode : 2017NatSR ... 743048D . DOI : 10.1038 / srep43048 . PMC 5318873 . PMID 28220854 .  
  28. ^ Ли, Чжаокай; Даттани, Найк; Чен, Си; Лю, Сяомэй; Ван, Хэнъянь; Танберн, Ричард; Чен, Хунвэй; Пэн, Синьхуа; Ду Цзянфэн (25 июня 2017 г.). «Высокоточные адиабатические квантовые вычисления с использованием внутреннего гамильтониана спиновой системы: приложение к экспериментальной факторизации 291311». arXiv : 1706.08061 [ квант-ф ].
  29. ^ Крейн, Лия. «Квантовый компьютер устанавливает новый рекорд в поиске множителей простых чисел» . Новый ученый . Проверено 2 октября 2020 .