Случайный вопрос от SQuAD:

Когда было обнаружено, что простые числа можно применять для создания алгоритмов криптографии с открытым ключом?

Отвечать:

1970-е годы

Полученные предложения:

1. Тем не менее, это видение было разрушено в 1970 - й год, когда было публично объявлено , что простые числа могут быть использованы в качестве основы для создания ключевых алгоритмов шифрования с открытым ключом.
2. Простые числа используются в нескольких процедурах в информационных технологиях, таких как криптография с открытым ключом, которая использует такие свойства, как сложность разложения больших чисел на их простые множители.
3. Для проверки простоты больших чисел были разработаны алгоритмы, гораздо более эффективные, чем пробное деление.
4. Некоторые алгоритмы шифрования с открытым ключом, такие как RSA и обмен ключами Диффи-Хеллмана, основаны на больших простых числах (например, 512-битные простые числа часто используются для RSA, а 1024-битные простые числа типичны для Диффи-Хеллмана). .
5. Простые числа также используются для хэш-таблиц и генераторов псевдослучайных чисел.
6. Некоторые из этих простых чисел были найдены с помощью распределенных вычислений.
7. Долгое время теория чисел в целом и изучение простых чисел в частности рассматривались как канонический пример чистой математики без каких-либо приложений, выходящих за рамки личного интереса изучения темы, за исключением использования простых чисел. зубья шестерни для равномерного распределения износа.
8. Детерминированные алгоритмы позволяют точно определить, является ли данное число простым или нет.
9. Фраза «все возможные алгоритмы» включает не только алгоритмы, известные сегодня, но и любые алгоритмы, которые могут быть обнаружены в будущем.
10. Например, пробное деление является детерминированным алгоритмом, потому что при правильном выполнении он всегда будет определять простое число как простое, а составное число как составное.
11. Сформулированная как проблема решения, это проблема определения того, имеет ли вход коэффициент меньше k. Эффективный алгоритм целочисленной факторизации неизвестен, и этот факт лежит в основе нескольких современных криптографических систем, таких как алгоритм RSA.
12. Перед тем, как началось собственное исследование, явно посвященное сложности алгоритмических проблем, различные исследователи заложили многочисленные основы.
13. Этот локально-глобальный принцип еще раз подчеркивает важность простых чисел для теории чисел.
14. Вероятностные алгоритмы обычно работают быстрее, но не полностью доказывают, что число является простым.
15. Однако самый известный квантовый алгоритм для этой проблемы, алгоритм Шора, действительно работает за полиномиальное время.
16. Сито Эратосфена, приписываемое Эратосфену, представляет собой простой метод вычисления простых чисел, хотя большие простые числа, которые сегодня встречаются на компьютерах, не генерируются таким образом.
17. Проблема считается сложной по своей сути, если для ее решения требуются значительные ресурсы, независимо от используемого алгоритма.
18. Алгоритмы, использующие случайные биты, называются рандомизированными алгоритмами.
19. Считается, что если проблема может быть решена с помощью алгоритма, существует машина Тьюринга, которая решает эту проблему.
20. Однако числа Кармайкла значительно реже простых чисел, поэтому этот тест может быть полезен для практических целей.
21. Например, список простых чисел до 10 006 721 Деррика Нормана Лемера, переизданный в 1956 году, начинался с 1 в качестве первого простого числа.
22. В тезисе Кобхэма говорится, что проблема может быть решена с возможным количеством ресурсов, если она допускает алгоритм с полиномиальным временем.
23. Евклид также показал, как построить совершенное число из простого числа Мерсенна.
24. По состоянию на январь 2016 г. [обновление] наибольшее известное простое число состоит из 22 338 618 десятичных цифр.
25. Такие вопросы стимулировали развитие различных разделов теории чисел, в которых основное внимание уделялось аналитическим или алгебраическим аспектам чисел.