Главная

О взаимосвязи простых и иррациональных чисел

2018-10-15 в 14:42, admin, рубрики: rsa, иррациональность, иррациональные числа, математика, простые числа, теория чисел, хаос

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

Введение

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

(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 )$ , где $f$ — изоморфизм такой, что:
$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}$
И пусть $F(x,y)=f(x) + f(y)$ . Тогда:
$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.

В заключение

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

Автор: ia_androsov

Источник