Записи целочисленной факторизации
Факторизация целых чисел — это процесс определения того, какие простые числа делят данное положительное целое число . Быстрое выполнение этой задачи имеет применение в криптографии . Трудность зависит как от размера и формы числа, так и от его простых делителей ; в настоящее время очень сложно факторизовать большие полупростые числа (да и большинство чисел, у которых нет малых делителей).
Числа общего вида [ править ]
Первой огромной распределенной факторизацией была RSA-129 , 129-значное числовое число, описанное в статье 1977 года в журнале Scientific American, которая впервые популяризировала криптосистему RSA. Он был факторизован в период с сентября 1993 по апрель 1994 года с использованием MPQS , при этом отношения предоставили около 600 человек через Интернет, а заключительные этапы вычислений выполнялись на суперкомпьютере MasPar в Bell Labs.
В период с января по август 1999 года RSA-155 , 155-значное числовое число, подготовленное компанией RSA, было факторизовано с использованием GNFS , причем отношения снова были предоставлены большой группой, а заключительные этапы расчета были выполнены чуть более чем за девять дней на Суперкомпьютер Cray C916 в Академическом компьютерном центре SARA Amsterdam.
В январе 2002 г. Франке и др. объявил о факторизации 158-значного кофактора 2 953 + 1, используя пару месяцев примерно на 25 ПК в Боннском университете , причем заключительные этапы выполняются с использованием кластера из шести ПК Pentium-III.
В апреле 2003 года та же команда рассчитала 160-значный RSA-160, используя около сотни процессоров в BSI , причем заключительные этапы вычислений выполнялись с использованием 25 процессоров суперкомпьютера SGI Origin .
576-битный (174-значный) RSA-576 был факторизован Франке, Кляйнджунгом и членами сотрудничества NFSNET в декабре 2003 года с использованием ресурсов BSI и Боннского университета; вскоре после этого Аоки, Кида, Симояма, Сонода и Уэда объявили, что они рассчитали 164-значный кофактор 2. 1826 + 1.
176-значный кофактор 11 281 + 1 был факторизован Аоки, Кидой, Симоямой и Уэдой в период с февраля по май 2005 года с использованием машин в NTT и Университете Риккё в Японии. [1]
663-битный (200-значный) номер запроса RSA-200 был факторизован Франке, Кляйнджунгом и др. с декабря 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-битный (240-значный) RSA-240 был факторизован Фабрисом Будо, Пьерриком Годри, Авророй Гильевич, Надей Хенингер, Эммануэлем Томе и Полем Циммерманном. [4] [5]
факторизация 829-битного (250-значного) RSA-250 . В феврале 2020 года была завершена [6]
Числа специального вида [ править ]
12 151 − 1 из 542 битов (163 цифры) был факторизован в период с апреля по июль 1993 года командой CWI и Университета штата Орегон . [7]
2 773 + 1 из 774 бит (233 цифры) был факторизован в период с апреля по ноябрь 2000 года компанией The Cabal, при этом шаг матрицы был выполнен за 250 часов на Cray, который также использовался для RSA-155. [8]
2 809 − 1, из 809 бит (244 цифры), о факторизации было объявлено в начале января 2003 года. Рассеивание было выполнено в 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 н − 1 с n между 1000 и 1200 были факторизованы с помощью подхода с несколькими числами сита, в котором большая часть этапа просеивания могла быть выполнена одновременно для нескольких чисел, группой, в которую входили Т. Кляйнджунг, Дж. Бос и А. К. Ленстра , начиная с 2010. [14] Если быть точным, n = 1081 (326 цифр) было завершено 11 марта 2013 г.; n = 1111 (335 цифр) на 13 июня 2013 г.; n = 1129 (340 цифр) на 20 сентября 2013 г.; n = 1153 (348 цифр) на 28 октября 2013 г.; n =1159 (349 цифр) на 9 февраля 2014 г.; n = 1177 (355 цифр) 29 мая 2014 г., n = 1193 (360 цифр) 22 августа 2014 г. и n = 1199 (361 цифра) 11 декабря 2014 г.; первое подробное объявление было сделано в конце августа 2014 года. Общие затраты на проект составляют порядка 7500 лет ЦП на Opteron с частотой 2,2 ГГц, из них примерно 5700 лет потрачено на просеивание и 1800 лет на линейную алгебру.
отдельных лиц Сравнение с усилиями
По состоянию на конец 2007 года, благодаря постоянному снижению цен на память, доступности многоядерных 64-битных компьютеров и доступности эффективного кода просеивания (разработанного Торстеном Кляйнъунгом из Боннской группы) через ggnfs [15] и надежное программное обеспечение с открытым исходным кодом, такое как msieve [16] на завершающих этапах числа специального вида длиной до 750 бит (226 цифр) и числа общего вида длиной примерно до 520 бит (157 цифр) могут быть рассчитаны за несколько месяцев на нескольких компьютерах одним человеком без каких-либо специальный математический опыт. [17] Эти границы увеличиваются примерно до 950 бит (286 цифр). [18] и 600 бит (181 цифра) [19] если бы можно было обеспечить совместную работу нескольких десятков компьютеров для рассева; в настоящее время объем памяти и мощность процессора одной машины на завершающем этапе являются равными препятствиями для прогресса.
В 2009 году Бенджамин Муди использовал 512-битный (155-значный) ключ RSA, используемый для подписи графического калькулятора TI-83, используя программное обеспечение, найденное в Интернете; в конечном итоге это привело к ключевому спору о подписании контракта Texas Instruments .
В сентябре 2013 года 696-битный (210-значный) RSA-210 был факторизован Райаном Проппером. [20] использование институциональных ресурсов; в период с марта 2013 г. по октябрь 2014 г. еще одно 210-значное число (117-й член в домашней простой последовательности, начинающийся с 49) было заполнено пользователем, известным как WraithX, [21] использование времени обработки на машинах Amazon EC2 стоимостью 7600 долларов США [22] для просеивания и четыре месяца на двойном Xeon E5-2687W v1 для линейной алгебры.
компьютеров квантовых Рекорды усилий
Наибольшее число, достоверно учтенное [ нужны разъяснения ] по алгоритму Шора равно 21, которое было учтено в 2012 году. [23] 15 ранее были учтены несколькими лабораториями.
о факторизации 143 = 13 × 11 с помощью адиабатического квантового компьютера ЯМР при комнатной температуре (300 К). В апреле 2012 года группа под руководством Синьхуа Пэн сообщила [24] В ноябре 2014 года было обнаружено, что в эксперименте 2012 года на самом деле были учтены гораздо большие числа, даже не зная об этом. [ нужны разъяснения ] [25] [26] В апреле 2016 года 18-битное число 200 099 было факторизовано с помощью квантового отжига на квантовом процессоре D-Wave 2X . [27] Вскоре после этого число 291 311 было факторизовано с помощью ЯМР при температуре выше комнатной. [28] В конце 2019 года вычислительная компания Zapata заявила, что факторизовала 1 099 551 473 989, [29] и в 2021 году выпустил статью, описывающую это вычисление. [30] В 2024 году был предложен новый подход к внедрению задач факторинга простых чисел в квантовые отжигатели, который привел к (i) внедрению задач факторинга простых чисел 21 × 12 в архитектуру D-Wave Pegasus; (ii) факторизация 8 219 999 с использованием квантового отжига без использования гибридных методов. [31]
Однако заявления о факторинге с помощью квантовых компьютеров подверглись критике за то, что они сильно зависят от классических вычислений для уменьшения количества необходимых кубитов. [32] [33] Например, факторизация 1 099 551 473 989 опиралась на классическую предварительную обработку, чтобы свести проблему к трехкубитной квантовой схеме. [30] Более того, три числа, факторизованные в этой статье (200 099, 291 311 и 1 099 551 473 989), могут быть легко факторизованы с использованием метода факторизации Ферма , требующего всего 3, 1 и 1 итерации цикла соответственно.
См. также [ править ]
Ссылки [ править ]
- ^ К. Аоки; Ю. Кида; Т. Симояма; Х. Уэда. «Факторизация 176-значного числа» . Проверено 23 мая 2007 г.
- ^ Ф. Бар; М. Бём; Дж. Франке; Т. Кляйнъюнг. «РСА200» . Проверено 23 мая 2007 г.
- ^ Т. Кляйнджунг; К. Аоки; Дж. Франке; АК Ленстра; Э. Томе; JW Голос; П. Годри; А. Круппа; PL Монтгомери; Д.А. Освик; Х. Риель; А. Тимофеев; П. Циммерманн. «Факторизация 768-битного модуля RSA» (PDF) . Проверено 11 апреля 2013 г.
- ^ «[Cado-NFS-обсудить] 795-битный факторинг и дискретные логарифмы» . Архивировано из оригинала 2 декабря 2019 г. Проверено 3 декабря 2019 г.
- ^ Ф. Будо и др., «Сравнение сложности факторизации и дискретного логарифма: эксперимент с 240 цифрами», 10 июня 2020 г.
- ^ "LISTSERV - Архив NMBRTHRY - LISTSERV.NODAK.EDU" .
- ^ ПЛ Монтгомери. «Факторизация ситового поля рекордного числа» . Проверено 23 ноября 2007 г.
- ^ Кабал. «233-значная факторизация SNFS» . Архивировано из оригинала 28 ноября 2007 г. Проверено 23 ноября 2007 г.
- ^ Дж. Франке. «М809» . Архивировано из оригинала 23 августа 2007 г. Проверено 23 ноября 2007 г.
- ^ К. Аоки; Ю. Кида; Т. Симояма; Х. Уэда. «СНФС274» . Проверено 23 мая 2007 г.
- ^ К. Аоки; Дж. Франке; Т. Кляйнджунг; АК Ленстра; Д. А. Освик. «Факторизация 1039-го числа Мерсенна» . Проверено 23 мая 2007 г.
- ^ Кадзумаро Аоки; Йенс Франке; Торстен Кляйнюнг; Арьен Ленстра; Даг Арне Освик. «Сетчатая факторизация килобитного поля специального числа» . Проверено 19 декабря 2007 г.
- ^ Грег Чайлдерс (2012). «Факторизация 1061-битного числа с помощью сита специального числового поля» . Архив электронной печати по криптологии .
- ^ Торстен Кляйнюнг; Жоппе В. Бос; Арьен К. Ленстра. «Фабрика факторизации Мерсенна» . Проверено 18 января 2015 г.
- ^ «Пакет GGNFS – просмотр файлов на SourceForge.net» . sourceforge.net .
- ^ «Архивная копия» . Архивировано из оригинала 13 декабря 2007 г. Проверено 23 ноября 2007 г.
{{cite web}}
: CS1 maint: архивная копия в заголовке ( ссылка ) - ^ «mersenneforum.org – Посмотреть отдельное сообщение – Таблица 2LM» . www.mersenneforum.org .
- ^ «mersenneforum.org – Посмотреть одно сообщение – Вычисление, достойное этого названия» . www.mersenneforum.org .
- ^ «mersenneforum.org – Посмотреть отдельное сообщение – 5^421-1 просеивание (оговорки закрыты)» . www.mersenneforum.org .
- ^ «Учет RSA-210 – mersenneforum.org» . mersenneforum.org .
- ^ «mersenneforum.org – Посмотреть отдельное сообщение – HP49(119)…» www.mersenneforum.org .
- ^ «Архивная копия» . Архивировано из оригинала 16 апреля 2021 г. Проверено 04 марта 2020 г.
{{cite web}}
: CS1 maint: архивная копия в заголовке ( ссылка ) - ^ Мартин-Лопес, Энрике; Энрике Мартин-Лопес; Энтони Лэнг; Томас Лоусон; Роберто Альварес; Сяо-Ци Чжоу; Джереми Л. О'Брайен (12 октября 2012 г.). «Экспериментальная реализация алгоритма квантового факторинга Шора с использованием переработки кубитов». Природная фотоника . 6 (11): 773–776. arXiv : 1111.4147 . Бибкод : 2012NaPho...6..773M . дои : 10.1038/nphoton.2012.259 . S2CID 46546101 .
- ^ «143 — это самое большое число, которое еще не было учтено квантовым алгоритмом» .
- ^ «Новое наибольшее число, учтенное в квантовом устройстве, составляет 56 153» .
- ^ «Математический трюк, который помог побить рекорд самого большого числа, когда-либо разложенного на множители…» 2 декабря 2014 г.
- ^ Дриди, Рауф; Альгасси, Хедаят (21 февраля 2017 г.). «Первичная факторизация с использованием квантового отжига и вычислительной алгебраической геометрии» . Научные отчеты . 7 : 43048. arXiv : 1604.05796 . Бибкод : 2017НатСР...743048Д . дои : 10.1038/srep43048 . ПМЦ 5318873 . ПМИД 28220854 .
- ^ Ли, Чжаокай; Даттани, Найк; Чен, Си; Лю, Сяомэй; Ван, Хэнъянь; Танберн, Ричард; Чен, Хунвэй; Пэн, Синьхуа; Ду, Цзянфэн (25 июня 2017 г.). «Высокоточные адиабатические квантовые вычисления с использованием внутреннего гамильтониана спиновой системы: применение к экспериментальной факторизации 291311». arXiv : 1706.08061 [ квант-ph ].
- ^ Крейн, Лия. «Квантовый компьютер устанавливает новый рекорд по нахождению множителей простых чисел» . Новый учёный . Проверено 2 октября 2020 г.
- ↑ Перейти обратно: Перейти обратно: а б Карамлу, Амир; Саймон, Уильям (28 октября 2021 г.). «Анализ производительности вариационного квантового факторинга на сверхпроводящем квантовом процессоре» . npj Квантовая информация . 7 : 156. arXiv : 2012.07825 . Бибкод : 2021npjQI...7..156K . дои : 10.1038/s41534-021-00478-z . S2CID 229156747 .
- ^ Дин, Цзинвэнь; Спаллитта, Джузеппе; Себастьяни, Роберто (12 февраля 2024 г.). «Эффективная факторизация простых чисел посредством квантового отжига посредством модульного локально структурированного встраивания» . Научные отчеты . 14 : 3518. arXiv : 2310.17574 . дои : 10.1038/s41598-024-53708-7 .
- ^ Гидни, Крейг. «Факторизация самого большого числа за всю историю с помощью квантового компьютера» . Блог . Проверено 18 июля 2022 г.
- ^ Смолин, Джон А. (2013). «Чрезмерное упрощение квантового факторинга». Природа . 499 (7457): 163–165. arXiv : 1301.7007 . Бибкод : 2013Natur.499..163S . дои : 10.1038/nature12290 . ПМИД 23846653 . S2CID 118613892 .