Оглавление
- 1 Номера RSA
- 1.1 История и цель RSA-факторинга
- 1.2 Публикация и призы
- 1.3 Текущее состояние
- 1.4 Методы и результаты
- 1.5 Примеры факторизации
- 1.6 История RSA-129
- 1.7 История RSA-130
- 1.8 История RSA-140
- 1.9 История RSA-150
- 1.10 История RSA-155
- 1.11 История RSA-160
- 1.12 История RSA-170
- 1.13 История RSA-576
- 1.14 История RSA-180
- 1.15 История RSA-190
- 1.16 История RSA-640
- 1.17 История RSA-200
- 1.18 История RSA-210
- 1.19 История RSA-704
- 1.20 История RSA-220
- 1.21 История RSA-230
- 1.22 История RSA-232
- 1.23 История RSA-768
- 1.24 История RSA-240
- 1.25 История RSA-250
- 1.26 Неучтенные числа
- 1.27 Неучтенные числа RSA
- 1.28 Призы за факторизацию
- 1.29 Дополнительная информация
- 1.30 Полный текст статьи:
- 2 Номера RSA — Arc.Ask3.Ru
Номера RSA
-
История и цель RSA-факторинга
- RSA-факторинг был создан RSA Laboratories в 1991 году для поощрения исследований в области вычислительной теории чисел.
- Задача состояла в нахождении простых множителей больших чисел.
- Соревнование было прекращено в 2007 году.
-
Публикация и призы
- RSA Laboratories опубликовала ряд полупростых чисел от 100 до 617 десятичных разрядов.
- Для учета некоторых чисел были предложены денежные призы до 200 000 долларов США.
- Наименьший номер RSA был рассчитан за несколько дней.
-
Текущее состояние
- По состоянию на февраль 2020 года, были учтены наименьшие 23 из 54 чисел.
- Несмотря на завершение конкурса, люди продолжают искать способы разложения на множители.
-
Методы и результаты
- Первые числа RSA были помечены по количеству десятичных разрядов, позже использовались двоичные цифры.
- Наименьший номер RSA был рассчитан за несколько дней, большинство цифр до сих пор не учтены.
- Факторизация чисел заняла значительное время и ресурсы, включая использование параллельных компьютеров.
-
Примеры факторизации
- RSA-100 был разложен на множители за несколько дней с использованием многочленного алгоритма квадратичного сита.
- RSA-110 был разложен менее чем за четыре часа на разогнанном процессоре Intel Core2 Quad q9300.
- RSA-120 был разложен менее чем за три месяца фактического компьютерного времени.
-
История RSA-129
- Разработан в 1994 году командой под руководством Дерека Аткинса и других
- Использовано около 1600 компьютеров и 600 добровольцев
- Факторизация найдена с использованием алгоритма множественного полиномиального квадратичного сита
- Сообщение расшифровано: «Волшебные слова — Брезгливый оссификатор»
-
История RSA-130
- Разработан в 1996 году командой под руководством Арьена К. Ленстра
- Факторизация найдена с использованием алгоритма просеивания числового поля
-
История RSA-140
- Разработан в 1999 году командой под руководством Хермана те Риле
- Факторизация найдена с использованием алгоритма Number Field Sieve
-
История RSA-150
- Снят с рассмотрения службой безопасности RSA
- Разложен на два 75-значных простых числа в 2004 году
-
История RSA-155
- Факторизация найдена с использованием алгоритма general number field sieve
-
История RSA-160
- Разработан в 2003 году командой из Боннского университета и Федерального управления информационной безопасности Германии
- Факторизация найдена с использованием общего алгоритма просеивания числовых полей
-
История RSA-170
- Разработан в 2009 году D. Боненбергером и М. Кроне
- Факторизация завершена С. A. Даниловым и я. A. Поповян
-
История RSA-576
- Разработан в 2003 году Дж. Франке и Т. Клейнджунг
- Компания RSA Security предложила денежный приз в размере 10 000 долларов
-
История RSA-180
- Разработан в 2010 году S. A. Данилов и я. A. Поповян
- Факторизация найдена с использованием реализации алгоритма general number field sieve
-
История RSA-190
- Разработан в 2010 году I. A. Поповян и А. Тимофеев
-
История RSA-640
- Разработан в 2005 году Ф. Бар, М. Бем, Дж. Франке и Т. Kleinjung
- Факторизация найдена с использованием GNFS
- Вычисления заняли пять месяцев на 80 процессорах AMD Opteron
-
История RSA-200
- Процессорное время составило 75 лет работы одного компьютера на базе Opteron
-
История RSA-210
- Разработан Райаном Проппером в 2013 году
-
История RSA-704
- Разработан Ши Баем, Эммануэлем Томе и Полом Циммерманом в 2012 году
- Факторизация объявлена 2 июля 2012 года
-
История RSA-220
- Разработан S. Бай, П. Годри, А. Круппа, Э. Томе и П. Циммерман в 2016 году
- Факторизация объявлена 13 мая 2016 года
-
История RSA-230
- Разработан Сэмюэлем С. Всего на 15 августа 2018 года
-
История RSA-232
- Разработан N. L. Замарашкин, Д. A. Желтков и С. A. Матвеев в 2020 году
- Факторизация объявлена 17 февраля 2020 года
-
История RSA-768
- Разработан Торстеном Кляйнджунгом и другими в 2009 году
- Факторизация заняла почти 2000 лет на одноядерном компьютере на базе AMD Opteron
-
История RSA-240
- Разработан Фабрисом Будо и другими в 2019 году
- Факторизация заняла около 900 ядер-лет на процессоре Intel Xeon Gold 6130
-
История RSA-250
- Разработан Фабрисом Будо и другими в 2020 году
- Факторизация заняла около 2700 процессорных лет на процессоре Intel Xeon Gold 6130
-
Неучтенные числа
- RSA-260, RSA-270, RSA-896, RSA-280, RSA-290, RSA-300, RSA-309, RSA-1024, RSA-310, RSA-320, RSA-330, RSA-340
-
Неучтенные числа RSA
- RSA-340 содержит 340 десятичных разрядов (1128 бит)
- RSA-350 содержит 350 десятичных разрядов (1161 бит)
- RSA-360 содержит 360 десятичных разрядов (1194 бит)
- RSA-370 содержит 370 десятичных разрядов (1227 бит)
- RSA-380 содержит 380 десятичных разрядов (1261 бит)
- RSA-390 содержит 390 десятичных разрядов (1294 бит)
- RSA-400 содержит 400 десятичных разрядов (1327 бит)
- RSA-410 содержит 410 десятичных разрядов (1360 бит)
- RSA-420 содержит 420 десятичных разрядов (1393 бит)
- RSA-430 содержит 430 десятичных разрядов (1427 бит)
- RSA-440 содержит 440 десятичных разрядов (1460 бит)
- RSA-450 содержит 450 десятичных разрядов (1493 бит)
- RSA-460 содержит 460 десятичных разрядов (1526 бит)
- RSA-1536 содержит 463 десятичных разряда (1536 бит)
- RSA-470 содержит 470 десятичных разрядов (1559 бит)
- RSA-480 содержит 480 десятичных разрядов (1593 бит)
- RSA-490 содержит 490 десятичных разрядов (1626 бит)
- RSA-500 содержит 500 десятичных разрядов (1659 бит)
- RSA-617 содержит 617 десятичных разрядов (2048 бит)
- RSA-2048 содержит 617 десятичных разрядов (2048 бит)
-
Призы за факторизацию
- За успешную факторизацию RSA-1536 предлагалось 150 000 долларов
- За успешную факторизацию RSA-2048 предлагалось 200 000 долларов
-
Дополнительная информация
- Записи о разложении на множители целых чисел
- Вызов по факторингу RSA
- Задача с секретным ключом RSA
- Записи
- Рекомендации
- Администратор конкурсной комиссии RSA по факторингу
- RSA Laboratories, номера RSA Challenge
- Лаборатории RSA, статистика факторинга GNFS для RSA-100, 110, …, 150
- Внешние ссылки
- Стивен Леви, остряк из Wired News