[Из песочницы] О взаимосвязи простых и иррациональных чисел15.10.2018 19:49

После некоторых моих исследований простых чисел, я обнаружил интересную связь с иррациональными числами. Эта связь дает ответ на вопрос, почему простые числа расположены столь «хаотично» и почему они так сложно устроены. Под катом объяснение этой связи и вариант улучшенного алгоритма RSA.

Введение

Рассмотрим множество $\lbrace 2n + 3m \vert n,m \in \mathbb{N} \rbrace$ . Теперь попробуем его упорядочить. То есть найти способ найти следующую пару чисел n и m, зная предыдущую. Очевидно, что: 2 + 2 + 2 = 3 + 3 и 2 + 2 > 3, 2

(1,0), (0,1), (2,0), (1,1), (3,0), (2,1), (4,0), (3,1), (5,0)…

Заметим, что четко прослеживается порядок и, соответственно, способ получения следующей пары чисел. Здесь нет никаких проблем и задача тривиальна.
Теперь рассмотрим множество $\lbrace 2n + \pi m \vert n,m \in \mathbb{N} \rbrace$ . К сожалению или к счастью, но это множество не получится упорядочить в том смысле, как предыдущее:

(1,0), (0,1), (2,0), (1,1), (3,0), (0,2), (2,1), (4,0), (3,1), (0,3)…

Если вы решили, что нашли точный порядок, то достройте эти пары дальше и увидите, что он нарушается. «Хаос» этих пар чисел напрямую связан с иррациональностью числа $\pi$ , доказанная Иоганном Ламбертом в 1761 году. Действительно, чтобы выстроить пары в ряд, мы вначале пытаемся уложить отрезок длиной 2 в отрезок длинной $\pi$ . Полученный остаток мы пытаемся уложить в отрезок длиной 2. Он вместиться только один раз. Это означает, что наш остаток «сыграет» свою роль уже на отрезке длиной $2 \pi$ , где вместиться уже не два отрезка длинной 2, а три. Проделывая такую операцию и далее, становиться понятно, что как только у нас складывается впечатления, что мы нашли порядок, он сломается через какое-то число шагов. Так как последний, еще не используемый, остаток рано или поздно «сыграет» свою роль и порядок поменяется. Стало быть, вопрос о нахождении «хорошего» алгоритма для этой задачи остается открытым.

Немного определений

Пусть $$( \mathbb{R} , +) \simeq ( \mathbb{R}_{>0} , \oplus)$» />, где <img src=$ — изоморфизм такой, что:
$f(x \oplus y) = f(x) + f(y)$
И, соответственно, для $g$ — обратной к $f$ :
$g(x + y) = g(x) \oplus g(y)$ .
Теперь определим интересующее нас множество:
$W_{\oplus} = \lbrace a_{2}f(2) + a_{3}f(3) + \dots + a_{n}f(n)+ \dots \vert \forall m \in \mathbb{N}, a_{m} \in \mathbb{N} \rbrace \setminus \lbrace 0 \rbrace$
$$\Rightarrow W_{\oplus} \subset \mathbb{R}_{>0}$» /><br />И пусть <img src=$ . Тогда:
$g(F(x,y)) = x \oplus y$
И $\mathbb{T}$ — образ множества $W_{\oplus}$ для отображения $g$ .
И, наконец, $\mathbb{P}_{\oplus} = \lbrace p \in \mathbb{T} \vert \forall w_{1},w_{2} \in W_{\oplus}, g(w_{1} + w_{2}) \neq p \rbrace$ — множество простых чисел для операции $\oplus$ .
Теперь легко пояснить эти определения на привычном нам примере. Для операции умножения, $f(x) = log_{2}(x)$ . А множество $W$ — это $log_{2}(\mathbb{N})$ . Тут стоит остановиться и объяснить, почему это важно.

Сама связь

На самом деле, мы, используя изоморфизм, получили, что сложность всех задач про простые числа эквивалента задачам про суммы логарифмов, которые являются иррациональными. То есть, как мы убедились на примере с множеством из чисел $\pi$ и 2, именно иррациональность вносит хаос. Так же и тут, иррациональность логарифмов распределяет простые числа на числовой прямой практически хаотичным способом. Возникает сложность в упорядочивании пар n и m во множестве, например, $\lbrace n + mlog_{2}3 \rbrace$ Другими словами, простота какого-нибудь числа напрямую зависит от, например, какого-то знака после запятой в числе $log_{2}3$ . Но мы определили простые числа не только для умножения, а вообще для произвольной бинарной операции. Я это сделал для того, чтобы показать, что наши простые числа ничем не уникальны.

RSA

Для бинарной операции x + xy + y:
$\mathbb{P} = \lbrace 2,4,6,10,12,16,18,22,28,30,36,40,42,46... \rbrace$ .
Хаотичность данного множества характеризуется иррациональными значениями изоморфизма на натуральных числах. К тому же, изоморфизм, по-видимому, не выражется через элементарные функции. Здесь мы по операции построили другие простые числа, распределение которых очевидным образом не зависит от распределения обычных простых чисел. Это дает нам возможность построения RSA на произвольной бинарной операции такой, чтобы изоморфизм был иррационален. Ведь функция логарифма слишком «хорошая» для криптоаналитиков. А здесь она ведет себя абсолютно непредсказуемым образом. Можно же и наоборот, построить изоморфизм, по которому будет определена коммутативная бинарная операция.

Взяв за основу произвольные простые числа, мы меняем задачу разложения составного числа на множители на задачу разложения практически произвольного иррационального числа на сумму двух других из заданного множества. Что-то мне подсказывает, что это задача должна относиться к классу NP.

В заключение

Человечество еще не решила много задач про простые числа, как математика подкидывает еще бесконечно подобных задач. Естественно будет задаться вопросом, что с этим делать? Мое предложение заключается в том, чтобы рассматривать все теоремы из Теории чисел не для сложения и умножения, а для сложения и произвольной коммутативной бинарной операции, замкнутой на натуральных числах. Тогда каждое утверждение про простые числа, были бы лишь следствием определенных свойств операции. Например, бесконечность простых чисел было бы следствием монотонности операции и достаточно быстрым ее ростом. Но это уже тема для отдельной статьи. Спасибо за внимание.