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

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

В заключение


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

Похожие публикации

Комментарии 26
    +5
    В таком виде совершенно не понятно что вы подразумеваете под «упорядочить множество {f(n, m)|n, m in N}».
    То, как пишете вы: «способ найти следующую пару чисел n и m, зная предыдущую.» — элементарно и, вообще говоря, не зависит от функции, которую вы к этим числам применяете. Очевидно, вы имеете в виду что-то другое.

    И да.
    «простата какого-нибудь числа напрямую зависит от, например, какого-то знака после запятой»
    Знаю, что такое нужно в личку. Но тут не удержался xD
      +1
      Спасибо, исправил. У меня было несколько вариантов, как строго задать очевидную вещь. В таких множествах я имел ввиду нахождение просто взаимосвязи. Я думаю, что интуитивно понятно, что, например, во множестве степеней двойки «порядок» находиться очень просто, а во множестве простых чисел — нет. Вы правы, способ существует всегда — полный перебор. Я имел ввиду явную формулу для любой пары. Полный перебор формулой являться не будет, так как множество — бесконечно.
        +1
        Как ехидно говорил мой препод по матану: «Если вам это кажется очевидно, то для вас не будет никаких проблем это доказать».

        Я правильно понимаю, что под порядком вы понимаете это.
        Для мн-ва A = {a} задан порядок если существует биекция А <-> N (обозначим такие пары a_n) и функция f: A -> A, которая для каждого a_n вычисляет a_{n+1}
        Иными словами если множество счетно и по элементу n можно однозначно определить эл-т n+1?

        Или вы также требуете, чтобы f вычислялась за константу?
          0
          Для множества, про которое вы написали, биекция будет существовать всегда. Как раз потому, что множество — счетно. Да, вы выразили мою мысль наиболее правильно, сказав про вычисление f за константу. По крайней мере, нахождение n-ой пары за полиномиальное время.
            +1
            Ну вот. Теперь у вас есть нормально поставленное утверждение. Теперь продемонстрируйте для первого множества такую функцию f и докажите, что для второго такого f нет. Потому-что ваши словесные рассуждения совершенно непонятны.

            Вот это меня совсем убило *сова.jpg*
            Очевидно, что: 2 + 2 + 2 = 3 + 3 и 2 + 2 > 3, 2 < 3. Таким образом, пары чисел распределены следующим образом:

            К тому же в вашем примере для первого множества отсутствуют, например, пара чисел (0, 2) Спрашивается почему?
              0
              (0,2) = (3,0) как раз из-за равенства 2 + 2 + 2 = 3 + 3. Удобно выбирать вторую пару, а не первую. Но можно было бы везде выбрать и первую пару — это не принципиально. Простите, боюсь, что я не могу доказать, что для второго множества не существует такой функции f. Я лишь сказал, что эта проблема остается открытой, так как абсолютно не очевидна. А доказательство, которое вы хотите, привело бы и к решению известной проблемы P/NP.
          0
          Есть еще порядок Шарковского.
            0
            Из курса алгебры я помню, что отношение частичного порядка — это отношение, которое является рефлексивным (a >= a), транзитивным (a >= b, b >= c => a >= c) и антисимметричным (a >= b, b >= a => a = b). Отношение строгого порядка — это отрицание какого-то отношения частичного порядка.

            Теперь попробуем его упорядочить. То есть найти способ найти следующую пару чисел n и m, зная предыдущую

            Само это высказывание выглядит неверным. Рациональные числа упорядочены, но не получится найти «следующую пару».
            Возможно, Вам стоило бы найти другой термин для того, что хотелось описать.
              0
              Я знаю об этой проблеме в терминологии. Вы абсолютно правы в определении порядка. Я пытался избежать именно этого понимания. Здесь я имел ввиду порядок в смысле выстроить пары в счетный ряд по возрастанию и ничего больше. И это можно сделать всегда в этих множествах. Важно лишь нахождение алгоритма для этого. Порядок из курса алгебры куда более общее понятие. Я учту это и в дальнейшем буду использовать другие термины. Спасибо за ваш комментарий.
              0
              во множестве степеней двойки «порядок» находиться очень просто, а во множестве простых чисел — нет.

              Но стоит эти степени двойки умножить на нечётные числа как сразу теряется их порядок, связано с гипотезой Коллатца, которая по хаотичности не уступает простым числам.
              +3
              Водоразделом в этом посте служит заголовок «Сама связь». До неё идут понятные рассуждения, которые проводятся непонятно зачем. После — непонятные рассуждения.

              У вас в профиле указано «математик». Могу я поинтересоваться вашим образованием и местом работы? Не ради каких-то понтомерок, просто хочу лучше понимать контекст ваших рассуждений.
                +2
                1) Простые числа никогда не были чем-то уникальным. Не обязательно переводить умножение в сложение через логарифм, достаточно обобщиться до многочленов и посмотреть на неприводимые многочлены.
                2) Связь вида «там хаос и тут хаос, значит они связаны» не выглядит обоснованной.
                  0
                  Взяв за основу произвольные простые числа, мы меняем задачу разложения составного числа на множители на задачу разложения практически произвольного иррационального числа на сумму двух других из заданного множества. Что-то мне подсказывает, что это задача должна относиться к классу NP.


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

                  Простые числа, насколько я понимаю, уже давным давно обобщены — надо смотреть в сторону простых-максимальных идеалов и операций с ними.
                    0
                    Действительно похоже, вы правы. Однако там используются лишь целые положительные числа. Здесь же — иррациональные. Да, они обобщены, как вы заметили. Но это обобщение не позволяет работать с изоморфизмами таким образом.
                    0
                    Утверждению «вариант улучшенного алгоритма RSA» в статье нет никакого обоснования. Независимый эксперт уже проверил его на преимущество и криптостойкость?
                      0
                      Очевидно, что он не хуже обычного RSA, так как RSA является частным случаем «варианта улучшенного RSA». В остальном предлагаю стать вам «независимым экспертом».
                        0
                        Увы, не для всех это очевидно. К примеру, не каждое подмножество эллиптических кривых имеет криптографическую ценность.
                      0
                      Кстати. Золотое сечение — 1,6180339887… иррационально. Однако если мы разложим его в цепную дробь
                      image
                      то увидим, что никакого хаоса нет и в помине. Из чего следует, что из иррациональности вовсе не следует хаотичность.
                        0
                        Просто для справки добавлю, что любая квадратичная иррациональность представляется в виде периодической цепной дроби.
                          0
                          Теорема Лагранжа: Число представляется в виде бесконечной периодической цепной дроби тогда и только тогда, когда оно является иррациональным решением квадратного уравнения с целыми коэффициентами.
                          Да, для алгебраических иррациональных чисел все может быть вполне хорошо. Мне хотелось бы рассматривать преимущественно трансцендентные числа. Например, все логарифмы от натуральных чисел являются трансцендентными числами или целыми, конечно.
                            0
                            Трансцендентное число также не является гарантией хаоса. Например, основание натурального логарифма представимо в виде e=[2;1,2,1,1,4,1,1,6,1,1,8,...,1,1,2n-2,1,1,2n,...]
                              0
                              Однако периодов не будет. Да, пример хороший. Тогда мне следует более строго определить «степени хаотичности» и дополнить исследование, учитывая такие числа. И тогда интересно было бы «упорядочить» множество {n + m*sqrt(2)}. Видимо, должен существовать хороший способ. И дальше попробовать проделать это же с множеством {n + m*e}. Но вот если взять уже множество {n + m*sqrt(2) + k*e}, то видимо все равно появится хаос, из-за «укладывания» sqrt(2) в число e.
                              0
                              Да и для числа пи есть (обобщённое) разложение:
                              image
                                0
                                А есть что-то подобное для логарифма?
                                  0
                                  Есть — разложение в степенной ряд.
                                    0
                                    Боюсь, что это не подойдет. Я изучу эту тему, спасибо за замечания.

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое