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

В заключение


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

Комментарии (25)


  1. myxo
    15.10.2018 19:41
    #19238789
    +3

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

    И да.
    «простата какого-нибудь числа напрямую зависит от, например, какого-то знака после запятой»
    Знаю, что такое нужно в личку. Но тут не удержался xD


  1. ia_androsov Автор
    15.10.2018 19:59
    #19238845
    +1

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


    1. myxo
      15.10.2018 21:54
      #19239145
      +1

      Как ехидно говорил мой препод по матану: «Если вам это кажется очевидно, то для вас не будет никаких проблем это доказать».

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

      Или вы также требуете, чтобы f вычислялась за константу?


      1. ia_androsov Автор
        15.10.2018 22:02
        #19239165

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


        1. myxo
          15.10.2018 22:16
          #19239237
          +1

          Ну вот. Теперь у вас есть нормально поставленное утверждение. Теперь продемонстрируйте для первого множества такую функцию f и докажите, что для второго такого f нет. Потому-что ваши словесные рассуждения совершенно непонятны.

          Вот это меня совсем убило *сова.jpg*

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

          К тому же в вашем примере для первого множества отсутствуют, например, пара чисел (0, 2) Спрашивается почему?


          1. ia_androsov Автор
            15.10.2018 22:22
            #19239261

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


    1. Kisva
      15.10.2018 22:04
      #19239181

      Есть еще порядок Шарковского.


    1. zuko3d
      15.10.2018 22:52
      #19239345

      Из курса алгебры я помню, что отношение частичного порядка — это отношение, которое является рефлексивным (a >= a), транзитивным (a >= b, b >= c => a >= c) и антисимметричным (a >= b, b >= a => a = b). Отношение строгого порядка — это отрицание какого-то отношения частичного порядка.

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

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


      1. ia_androsov Автор
        15.10.2018 22:59
        #19239369

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


  1. Sirion
    15.10.2018 23:14
    #19239401

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

    У вас в профиле указано «математик». Могу я поинтересоваться вашим образованием и местом работы? Не ради каких-то понтомерок, просто хочу лучше понимать контекст ваших рассуждений.


  1. xi-tauw
    16.10.2018 10:26
    #19240445
    +1

    1) Простые числа никогда не были чем-то уникальным. Не обязательно переводить умножение в сложение через логарифм, достаточно обобщиться до многочленов и посмотреть на неприводимые многочлены.
    2) Связь вида «там хаос и тут хаос, значит они связаны» не выглядит обоснованной.


  1. kirtsar
    16.10.2018 13:33
    #19241621

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


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

    Простые числа, насколько я понимаю, уже давным давно обобщены — надо смотреть в сторону простых-максимальных идеалов и операций с ними.


    1. ia_androsov Автор
      16.10.2018 13:34
      #19241633

      Действительно похоже, вы правы. Однако там используются лишь целые положительные числа. Здесь же — иррациональные. Да, они обобщены, как вы заметили. Но это обобщение не позволяет работать с изоморфизмами таким образом.


  1. Refridgerator
    16.10.2018 14:12
    #19241913

    Утверждению «вариант улучшенного алгоритма RSA» в статье нет никакого обоснования. Независимый эксперт уже проверил его на преимущество и криптостойкость?


    1. ia_androsov Автор
      16.10.2018 14:17
      #19241957

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


      1. Refridgerator
        16.10.2018 14:26
        #19242027

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


  1. Refridgerator
    16.10.2018 16:33
    #19242723

    Кстати. Золотое сечение — 1,6180339887… иррационально. Однако если мы разложим его в цепную дробь
    image
    то увидим, что никакого хаоса нет и в помине. Из чего следует, что из иррациональности вовсе не следует хаотичность.


    1. kirtsar
      16.10.2018 16:36
      #19242737

      Просто для справки добавлю, что любая квадратичная иррациональность представляется в виде периодической цепной дроби.


    1. ia_androsov Автор
      16.10.2018 16:40
      #19242763

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


      1. Refridgerator
        16.10.2018 18:06
        #19243139

        Трансцендентное число также не является гарантией хаоса. Например, основание натурального логарифма представимо в виде e=[2;1,2,1,1,4,1,1,6,1,1,8,...,1,1,2n-2,1,1,2n,...]


        1. ia_androsov Автор
          16.10.2018 18:13
          #19243189

          Однако периодов не будет. Да, пример хороший. Тогда мне следует более строго определить «степени хаотичности» и дополнить исследование, учитывая такие числа. И тогда интересно было бы «упорядочить» множество {n + m*sqrt(2)}. Видимо, должен существовать хороший способ. И дальше попробовать проделать это же с множеством {n + m*e}. Но вот если взять уже множество {n + m*sqrt(2) + k*e}, то видимо все равно появится хаос, из-за «укладывания» sqrt(2) в число e.


      1. Refridgerator
        16.10.2018 18:26
        #19243243

        Да и для числа пи есть (обобщённое) разложение:
        image


        1. ia_androsov Автор
          16.10.2018 18:49
          #19243345

          А есть что-то подобное для логарифма?


          1. Refridgerator
            16.10.2018 18:56
            #19243379

            Есть — разложение в степенной ряд.


            1. ia_androsov Автор
              16.10.2018 19:03
              #19243407

              Боюсь, что это не подойдет. Я изучу эту тему, спасибо за замечания.