Непростые простые числа
Автор статьи предлагает заглянуть в то, что представляют собой множества простых чисел, если взглянуть на них геометрическим образом. Это не профессиональная работа, а простое, любительское исследование некоторых любопытных закономерностей. Поэтому, в статье не будет сложной математики, и мы не будем забираться глубоко в ее дебри.
Вероятно, читателю известны многие проблемы, связанные с простыми числами. Их расположение в множестве натуральных чисел неочевидно. Большие простые числа трудно находить, нужно много усилий, чтобы проверить большое число на простоту. На этой трудности основаны многие современные методы криптографии. Мы можем легко перемножить да многозначных простых числа, но зная результат найти исходные множители – очень сложная задача.
Есть множество способов оптимизации, которые намного быстрее простого перебора, однако даже если оптимизация ускорит поиск в 10 раз, достаточно увеличить число на 2-3 десятичных знака (например, в 100 раз), чтобы замедлить поиск в 10^100 раз.
Это и значит, что сложность алгоритма является экспоненциальной, и поэтому какой бы быстрый ни был суперкомпьютер, мы можем подобрать длину числа еще больше, чтобы таких суперкомпьютеров потребовалось миллиард. Правда, стоит уточнить еще раз: находить простые числа для перемножения при этом становится так же все труднее и труднее.
К слову, математики не нашли ни доказательства, ни опровержения того, что нельзя найти алгоритм факторизации, сложность которого не была бы экспоненциально зависящей от длины числа. А доказав или опровергнув это, можно, заодно, решить математическую проблему, известную как гипотеза Римана. За ее доказательство математический институт Клея обещает миллион долларов.
Читать полностью »
