В распределении простых чисел обнаружена дифракционная картина, примерно как у квазикристаллов


    В марте 2016 года Роберт Дж. Лемке-Оливер и Каннан Соундарараджан из Стэнфордского университета открыли новый шаблон в распределении простых чисел. Оказалось, что простые числа специфически распределяются по числовому пространству. Подробнее см. перевод статьи «Структура и случайность простых чисел» на Хабре.

    К изучению темы подключились специалисты из других областей, в том числе химии. И успешно. Профессор теоретической химии Сальваторе Торкуато вместе с теоретиком чисел Мэтью де Курси-Айрлэнд нашли новые шаблоны в распределении простых чисел, о которых раньше не было известно. Оказалось, что распределение простых чисел образует фракталоподобную дифракционную картину, чем-то похожую на картину дифракции у экзотических квазикристаллов.

    Профессор Торкуато специализируется на изучении закономерностей в структурах физических систем, таких как кристаллы и коллоиды. Стандартный способ изучения структуры — дифракция рентгеновских лучей. Беспорядочные молекулы в жидкостях или газе отражают лучи во всех направлениях, не создавая заметного рисунка. Но симметрично расположенные атомы в кристалле синхронно отражают световые волны, создавая периодические яркие пятна выраженной дифракции (пики Брэгга). Анализ пиков Брэгга даёт возможность понять внутреннюю структуру кристалла или иного материала, который создаёт такую картину.

    Так вот, в новых научных статьях Торкуато и других (1, 2, 3) показано, что обнаруженная упорядоченная структура в распределении простых чисел — ни что иное как фракталоподобная дифракционная картина, примерно как у квазикристаллов.

    Картина пиков Брэгга на решётке из простых чисел похожа на квазикристаллы, но всё-таки отличается от них. Торкуато говорит, что простые числа как физическая система «являются совершенно новой категорией структур». Исследователи назвали этот новый фракталоподобный рисунок «эффективной предельной периодичностью» (effective limit-periodicity).

    Рисунок состоит из периодической последовательности светлых вершин, которые отражают наиболее общие интервалы простых чисел: все они нечётные (кроме 2), многие рядом друг с другом. Самые яркие пики (пары, разделённые двумя цифрами) чередуются через равные промежутки времени с менее яркими пиками, отражая простые числа, разделённые шестью цифрами. Между ними ещё более тусклые пики, соответствующие более удаленным парам простых чисел и т. д. Всё это — бесконечное количество пиков Брэгга, помещённых друг внутрь друга.


    Подобная структура пиков Брэгга наблюдалась и раньше — в дифракционных картинах квазикристаллов.


    Беспорядочные молекулы в жидкостях или газе отражают лучи во всех направлениях, не создавая заметного рисунка. Но симметрично расположенные атомы в кристалле синхронно отражают световые волны, создавая периодические яркие пятна выраженной дифракции. Как выяснилось, шаблон распределения простых чисел образует фрактальную дифракционную картину, примерно как у квазикристаллов

    Квазикристаллы — странные материалы, обнаруженных в 1980-х годах. Они характеризуются симметрией, запрещённой в классической кристаллографии, и наличием дальнего порядка. Математической моделью квазикристаллов являются апериодичные мозаики типа известной мозаики Пенроуза. В таких мозаиках отсутствует трансляционная симметрия, присутствует повторяемость и квазикристалличность (симметрия пятого порядка).


    Фрагмент мозаики Пенроуза типа P1 (из плиток шести типов)

    В случае простых чисел расстояния между пиками являются пропорциональными частями друг друга, в отличие от иррационально разнесённых пиков Брэгга квазикристаллов. «Простые числа фактически предполагают совершенно другое состояние позиций частиц, похожее на квазикристаллы, но не похожее на квазикристаллы», — сказал Торкуато.

    Открытие дифракционной картины нельзя назвать прорывным открытием для теории чисел, потому что основная часть этих шаблонов уже была описана ранее, только другими математическими методами (не через дифракцию квазикристаллов). Так, с помощью дифракционной картины возможно предсказание «двойников» типа 17 и 19 — это математический эквивалент первой гипотезы Харди — Литлвуда относительно существования кортежей простых чисел на данном отрезке числовой прямой. Одно из правил запрещает триплеты из последовательных нечётных чисел после {3, 5, 7}. Это же объясняет, почему следующий по яркости пик Брэгга в дифракционной картине соответствует числам, разделённым шестью цифрами, а не четырьмя.

    Новая научная работа — просто свежий взгляд на проблему равномерного распределения простых чисел и более простой способ вывести некий «единый закон» для них. Кроме того, это необычный способ анализа математической проблемы с точки зрения кристаллографии, а именно с точки зрения относительно молодой области исследований, называемой «апериодическим порядком», которая изучает неповторяющиеся модели и лежит на пересечении кристаллографии, динамических систем, гармонического анализа и дискретной геометрии. Эта отрасль науки выросла после открытия квазикристаллов, когда стало понятно, что старые методы тут не работают.

    Распределение простых чисел напоминает особый апериодический порядок, известный с 1950-х годов. Он называется предельной периодичностью (limit periodicity). В таких системах периодические интервалы вложены в бесконечную иерархию, так что в любом интервале система содержит части шаблонов, которые повторяются только в большем интервале, как в плитке Тейлора-Соколара.


    Плитка Тейлора-Соколара

    Теоретические расчёты показывают, что предельно-периодические фазы вещества должны иметь возможность формироваться в природе, и такие системы могут иметь необычные свойства. Но никто не догадался связать предельную периодичность с простыми числами. Теперь мы знаем, что такая связь есть, причём простые числа демонстрируют новый вид предельной перодичности — «эффективную» предельную периодичность, потому что синхронность в расстояниях между простыми числами по всей системе соблюдается только статистически.

    Возникает вопрос: как закономерности в распределении простых чисел могут сказаться на стойкости криптографических алгоритмов?

    «Я получаю действительно много писем на эту тему. Хотя это интересное исследование, но оно не имеет отношения к криптографии, — написал в своём блоге известный криптограф Брюс Шнайер. — Криптографам не интересен поиск простых чисел или даже их распределение. Стойкость алгоритмов криптографии с открытым ключом типа RSA связана со сложностью факторизации больших составных чисел, которые являются произведением простых чисел. А это совершенно другое дело».

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



    GlobalSign

    236,00

    Компания

    Поделиться публикацией
    Комментарии 56
      +13
      Представьте, что по числовой прямой слева направо катится колесо с длиной окружности, равной 2. На ободе колеса имеется радиальный выступ, которым оно «выталкивает» из числовой прямой каждое второе число.
      Затем по числовой прямой катится похожее колесо с длиной окружности, равной 3. Это колесо убирает каждое третье число и т.д.
      Все сохранившиеся на числовой прямой числа будут простыми. Можете представить себе ее вид, после того, как по ней проедет n колес с разной длиной окружности?
      Мне кажется, получится нечто похожее на интерференцию волн.
        +13
        Представьте, что по числовой прямой слева направо катится колесо
        Любопытное представление решета Эратосфена, не встречал такого :)

        С другой стороны, не уверен, что «колесо с длиной окружности, равной 2» так уж легко представить.
          0
          Одно колесо то представить легко, а вот несколько колес, у которых радиусы (не длины) соотносятся определенным образом — сложнее.
            0
            Радиусы и длины.
            +6
            С другой стороны, не уверен, что «колесо с длиной окружности, равной 2» так уж легко представить.

            Классический ответ: представляем колесо с длиной окружности c и полагаем c = 2.

              +1
              я где то встречал такой вариант описания.
              только не колесо, а циркуль мерный.
              но идея близкая.
                0
                Есть видео как это показали на автокаде:
                youtu.be/UYkLz8BIS8k
                  0
                  показали на автокаде
                  Окружность в видео, всё же, не катится и числа не «выталкивает» (а жаль) :) Но применение AutoCAD «не по назначению», определённо, неожиданное.
                +7

                Другими словами, n будет простым числом тогда и только тогда, когда


                image

                  +3
                  А там, где есть формула, всегда интересно нарисовать график) Wolfram сходу выдал такое:


                  Затухает слишком быстро, поэтому добавил масштабирующий множитель 2n/n2

                  на большем диапазоне


                  Правильнее, конечно, дискретно рисовать:
                    0
                    а еще лучше будет гистограмму по модулю сделать, с единичной высотой столбцов
                      +2
                      Высота столбиков пропорциональна количеству делителей числа.
                      image
                    0
                    Ещё так можно:

                    Заменив в гамма-функции n на x, можно полноценный непрерывный график построить, например для n=23:

                    Более правильно, конечно, так:

                    чтобы при целых n<2 тоже получать нули.

                    (Возможно, в произведении n-1 будет достаточно, нужен взгляд настоящего математика)
                      0
                      Скрытый текст

                      Первый график имеет решения там где N/x дает целое число, второй график где x целое число.

                      Совместно будет так:



                      Уравнение имеет решения в точках делителей числа N, но аналитически скорее всего не решается.
                      0
                      просто в wolframalpha.com наберите x mod k,
                      и он выдаст красивую 3d графику.
                        0

                        Это вы к чему?

                          0
                          то что любое число x можно проверить на простоту формулой
                          $$\prod_{n=2}^{\sqrt{x}}(x \mod n}) $$


                      0
                      Прочитал бы эту статью пораньше, то же б написал такой комментарий.
                      Ну может не с такой красивой аналогией про колеса, конечно.

                      Не пойму о чем сыр бор то? Статьи, ученые, еще статьи…
                      Они реально про принцип решета Эратосфена не в курсе были?
                      В школе прогу писал еще.
                        0
                        А вы в курсе, что такое аналитический вид функции?
                          0
                          Да.
                      0
                      Всё это — бесконечное количество пиков Брэгга, помещённых друг внутрь друга.

                      те простые числа не такие и простые — они делятся на «пики Брэгга»
                        +9
                        Статья сильно напомнила анекдот, как студент к экзамену по биологии выучил одну единственную тему «бобёр», вытаскивает билет, там «рыба». «Ну, рыба живет в воде. Но у нее, к сожалению, нет длинного плоского хвоста и четырех лап. А если бы были, она была бы как бобёр. А вот бобры...»
                          0
                          Звучит как «CRISPR в математике». Маленькая революция происходит прямо сейчас.
                            –2
                            Если это правда, все должны на ушах стоять. Это же упрощает дальнейший поиск больших простых чисел. На порядки упрощает. А это, в свою очередь, современной криптографии — кувалдой по роже.
                              +3

                              Быстро находить большие простые числа можно и сейчас. Только задаче факторизации это поможет.

                                0
                                Быстро????
                                  +2
                                  Поиск по списку и нумерацию никто не отменял: primes.utm.edu/lists

                                  Есть реально огромные списки.
                                    +1
                                    Ну для RSA нужны же простые примерно с половину ключа. Сейчас популярны RSA-2048/RSA-4096. Из-за того, что «плотность» простых убывает достаточно медленно, даже в диапазоне 2^1024...2^2048 можно просто взять случайное число и проверять каждое следующее на простоту. Проверку на простоту на практике делают вероятностным, но быстрым методом Миллера-Рабина.
                                      0
                                      Более того, простых чисел в этом диапазоне уже столько, что человечество никогда не переберёт все из них, так что даже готовый полный список никак не мешает криптографии, держащейся на факторизации больших чисел.
                                +3
                                тот, кто писал нашу матрицу, слишком увлёкся переиспользованием кода
                                  0
                                  Наоборот, теперь смысл простых чисел сильно упрощается и неизвестно еще какие последствия это даст в физике, астрономии и других науках. Той же теории струн например.
                                  +3
                                  Из детства запомнила фантастический рассказ. Люди считали цифры после запятой числа пи. В какой-то момент там началось осмысленное послание толи от высшего разума, толи от внеземных цивилизаций, типа раз вы, человечество, доросли до такого уровня вычислений, пришла пора сообщить вам истину.

                                  Похоже и в распределении простых чисел, кто рисуночек накатал. Смайлик наверное.
                                    +2
                                    Карл Саган. Контакт.
                                      +1

                                      Да это ладно, с помощью числа пи в теории фильмы даже смотреть, которые еще не вышли в прокат

                                        +2
                                        Запретить!!!
                                        0
                                        можно вообще ничего не писать, так как все что вы можете написать все равно есть в числе пи))
                                        0
                                        Беспорядочные молекулы в жидкостях или газе отражают лучи во всех направлениях, не создавая заметного рисунка. Но симметрично расположенные атомы в кристалле синхронно отражают световые волны, создавая периодические яркие пятна выраженной дифракции

                                        Ну если скажем часть атомов отражают в 2 направления, часть в 3, часть в 4, или наоборот, отклоняют лучи с этих позиций, то вполне логично, каждая 2, 3, 4 точка будет иметь некую особенность, которая усиливается при наложении эффектов от других групп. Решето Эратосфена.

                                          0
                                          Скорее здесь не о симметричности, а о дальнем порядке речь, который имеет упорядоченную картину отражения.
                                          –2
                                          Я не очень могу в математику — она для меня слишком абстрактна, и, возможно, то, что я скажу, может показаться глупым, но повторяется ли эта картина в других системах счисления, с какими-нибудь экзотическими базисами? Универсальны ли оказываются простые числа при переводе из системы в систему?

                                          И лирическое — если распределение чисел напоминает дифракционную картину квазикристалла, то может это и есть тот самый философский камень, который искали столетиями алхимики?
                                            +2
                                            Любая система счисления, какой бы экзотической она не была, — это всего лишь способ репрезентации чисел. Если вы возьмёте N камушков и сложили их в кучку, то как бы вы не изощрялись с записью числа N, на саму кучку это не повлияет.
                                            Само число не меняет никаких своих свойств от того, что вы его записали по-другому. В том числе и их взаимная делимость остаётся прежней.
                                              0
                                              я буду обновлять…
                                                0
                                                Я тоже такой себе математик, но определённо сами по себе простые числа существуют вне зависимости от того, по какому базисному основанию их записывают. Да и что бы такого особенного и внезапно подошедшего математике в базисе 2*5, по логике-то. Но в целом присоединяюсь к вопросу.

                                                А лирическое с немного физической стороны… А много ли мы знаем о катализаторах и квантовых эффектах на уровне межатомных взаимодействий? Невозможно исключить существование определённого катализатора, при котором определённый(-ые) из 7 (6) стабильных изотопов ртути, с числом протонов 80 и нейтронов (116,) 118, 119, 120, 121, 122, 124 через относительно холодную ядерную реакцию трансформируются в своего соседа 197-Au с 79 протонами и 118 нейтронами. Ну и что-то побочно соответственно выделяя, конечно — водород там, или нейтрон, или ядро гелия а также прочие нейтрино и фотоны, которые для физика алхимика «и пущай лелят, мне золото надо».
                                                0
                                                Между теорией чисел и кристаллографией/квантами вообще явно есть какая-то связь, они очень похожи. Юрий Манин вот ее долго искал и доискался до квантового компьютера. Интересно, читает ли он эту статью сейчас?
                                                  0
                                                  :-). Это потому что у Вселенной два конца: Один и Тот же…

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

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