20.05.2025 05:10
ooptimum 29 4900 Источник

Эта история началась в далёком 1998 году. По какой-то неведомой сегодня причине, может от скуки, а может быть была какая-то задача, которую я не в силах сегодня вспомнить, но, как бы там ни было, меня заинтересовали закономерности в распределении простых чисел, т. е. таких, которые делятся без остатка только на себя и на единицу. Знакомых математиков у меня не было, а Интернет в то время был совершенно не таким, каким мы знаем его сегодня, поэтому найти в нём ответы на свои вопросы я в то время не смог.

Удивительно, но мне удалось очень быстро найти такие закономерности самостоятельно. Я обнаружил, что если взять ряд всех натуральных чисел, то есть все целые числа от единицы и больше, и разбить его на группы по 30 чисел, а затем расположить эти группы в виде строк таблицы одну под другой, то все простые числа будут расположены в столбцах этой таблицы с определёнными номерами. Исключением из этого правила являются лишь три первых простых числа: 2, 3 и 5, произведение которых между собой как раз равно 30. Другими словами, взяв любое число, можно с уверенностью сказать, может ли это число быть простым, в этом случае оно будет давать один из определённых остатков при делении на 30 — это и будет номер столбца в нашей таблице, или оно простым совершенно точно не является, оно — составное.

Долгое время я пребывал в наивной уверенности, что обладаю тайным знанием, а также в скромных мечтах, что однажды настанет день, когда мне получится поделиться им с человечеством. Конечно, всегда находились более насущные и срочные дела, пока несколько лет назад я не решил взяться за факторизацию. Честно говоря, я был довольно разочарован, когда я узнал, что моё открытие, оказывается, давно известно математикам. Как же я был наивен тогда! То, что я обнаружил тогда по наитию, легко объяснимо — любое простое число, большее 5, по определению не может делиться ни на 2, ни на 3, ни на 5. Следовательно, оно является взаимно простым с 30. Количество натуральных взаимно простых чисел с заданным числом n, меньших или равных ему, равно значению функции Эйлера для этого числа: \varphi(n). Число 30 имеет \varphi(30)=8 взаимно простых с ним чисел. Это означает, что все простые числа больше 5 будут давать один из следующих остатков при делении на 30:

\mathcal{R}_{30} = \{1, 7, 11, 13, 17, 19, 23, 29\}

Это и есть номера столбцов в нашей таблице, содержащих все простые числа больше 5.

Итак, факторизация. Основная теорема арифметики гласит, что любое составное число можно разложить на простые сомножители, причём единственным способом. Под способом здесь подразумевается то, что получившийся набор простых сомножителей уникален для любого целого числа. Операция разложения чисел на сомножители называется факторизацией. Довольно просто, не правда ли? Но при всей простоте формулировки мы пока не знаем формулы, которую можно было бы применить для решения этой задачи. Поскольку формулы нет, будем говорить об алгоритмах, которые математики исторически называют методами. Все известные (по крайней мере мне) методы факторизации основаны на той или иной форме перебора параметров, ведущей в итоге к решению.

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

Задача со звёздочкой

Пусть у нас есть 64-битное целое беззнаковое число с начальным значением 0, для скорости обработки хранящееся в регистре общего назначения 64-битного процессора. Будем увеличивать значение в этом регистре на единицу в каждой итерации цикла, не делая больше ничего, пока оно не достигнет максимально возможной величины (все биты равны 1). Какое время будет выполняться эта задача на современном процессоре с частотой 3 ГГц?

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

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

Я подумал, что если взять два числа из нашей таблицы остатков деления на 30, то их произведение будет иметь строго определённый остаток от деления на 30, а зная этот остаток, мы можем узнать, каким столбцам могут принадлежать исходные сомножители. Таким образом, у нас появляется дополнительная информация о исходных числах, произведение которых нам нужно факторизовать!

Давайте, наконец, введём стандартную формулу, связывающую искомые сомножители и их произведение. Вот её обычный вид:

N = p \cdot q,

где N - факторизуемое число.

Hidden text

Возможно, вы не раз видели эту формулу. Обычно под p и q подразумеваются простые сомножители, но в нашем случае это не обязательно так.

Т.е. если мы возьмем любые p и q из, например, первого и седьмого столбца, то их произведение N всегда будет в седьмом столбце (N \equiv 7 \pmod{30}), как и для p и q из одиннадцатого и семнадцатого столбцов. Это следует из того, что для любых
x := p \bmod 30 и y := q \bmod 30 верно, что

x \cdot y \equiv p \cdot q \pmod{30}

То есть, произведение остатков по модулю 30 (остатков от деления чисел p и q на 30) соответствует остатку от деления произведения p и q на 30.

Hidden text

Пусть

x \equiv 7 \pmod{30}, \quad y \equiv 11 \pmod{30}

Тогда:

x \cdot y \equiv 7 \cdot 11 \equiv 17 \pmod{30}

Если взять любые другие x', y', такие что:

x' = 7 + 30k, \quad y' = 11 + 30m, \quad \text{где } k, m \in \mathbb{Z}

то:

x' \cdot y' \equiv 7 \cdot 11 \equiv 17 \pmod{30}

Если вам, как и мне, более понятны словесные описания, то из всего этого следует, что мы можем выразить разность D между двумя произвольными числами p и q как сумму числа полных строк между ними в нашей таблице остатков по модулю 30 — n, умноженного на количество чисел в строке — 30, и абсолютного значения разности между номерами столбцов, в которых находятся p и q — \delta. На языке математики это записывается так:

D = p - q = 30n + \delta, \quad \text{где } n \in \mathbb{Z},\ \delta \in \Delta

где

\delta \equiv |p - q| \pmod{30}

Это позволяет нам вычислить все возможные значения \delta для каждого v \equiv N \pmod{30} и занести их в таблицу дельт, которую мы будем использовать в дальнейшем.

Hidden text

Чтобы построить эту таблицу, я перебрал все возможные пары чисел из \mathcal{R}_{30}, назовем числа каждой пары: a и b, где a \le b. Для каждой пары я:

  1. Перемножал эти два числа и вычислял остаток от деления на 30

v = a \cdot b \bmod{30}

  1. Вычислял разность:

\delta=b-a

  1. Группировал полученные \delta по соответствующему значению v.

Таким образом, для каждого возможного остатка v \in [0, 29] получался список дельт, которые реально возникают при перемножении.

Дополнительно я применил два метода фильтрации:

  • Исключил значения \delta, которые никогда не приводят к полному квадрату при вычислении m^2 = D^2 + 4N (подробнее см. далее);

  • Убрал такие дельты, которые дают одинаковые значения D при вычислениях.

Это позволило сократить число возможных дельт для каждого N \pmod{30}, то есть сократить максимальное теоретическое число операций при факторизации N.

Ключевая формула метода

Для факторизации заданного числа N мы должны найти такое значение D, при котором D^2 + 4N является полным квадратом (квадратным числом):

m = \sqrt{D^2 + 4N} \in \mathbb{Z},

Если мы найдём такое целочисленное значение m, то сомножители N находятся сразу по формулам:

p = \frac{m+D}{2}, \quad q = \frac{|m-D|}{2}.

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

Как работает алгоритм?

Сначала мы должны взять из таблицы все подходящие значения \delta для v = N \bmod 30 — мы будем подставлять их в формулу (30n + \delta)^2 + 4N и проверять, не получился ли в итоге полный квадрат. Если получился, то мы можем остановить алгоритм и найти значения сомножителей p и q. Однако алгоритм является универсальным и может быть применён к составным числам, число простых сомножителей которых больше двух. Поэтому, если мы не знаем наверняка, что число N является полупростым (произведением двух простых сомножителей), мы можем продолжить поиск всех сомножителей, пока не переберем все подходящие n и \delta. При этом абслютная величина n ограничена сверху:

|n| \le \left\lfloor \frac{N}{30} \right\rfloor.

Т.е. n не может превышать наше начальное число N, разделенное на 30 с округлением вниз до ближайшего целого. Мы можем перебирать абсолютные значения n от 0 до максимально возможного — в этом случае мы сначала проверяем близкие по значению кандидаты в сомножители, постепенно увеличивая разницу между ними, или наоборот — от максимально возможного до 0, изначально проверяя максимально удалённые друг от друга кандидаты, или использовать какую-нибудь комбинированную стратегию. Следует учитывать, что n может принимать и отрицательные значения, поскольку мы не знаем заранее какое из чисел p и q является бо́льшим.

Больше об отрицательных n

Хотя операция умножения коммутативна ({p}\cdot{q}={q}\cdot{p}), данный метод основан на разности D=p−q, величина которой зависит от порядка членов. Чтобы учесть все возможные случаи, мы допускаем отрицательные значения n, что позволяет находить решение вне зависимости от того, какой из сомножителей, p или q больше.

Пример 1:

Допустим, нам нужно факторизовать: N = 13315381 = 3929 \times 3389

  1. N \bmod 30 = 1

  2. Таблица даёт: \delta \in \{0, 6\}

  3. Пробуем \delta = 0, перебираем n = 0, 1, 2, \dots

  4. При n = 18:

D = 30 \cdot 18 + 0 = 540m^2 = 540^2 + 4 \cdot 13315381 = 53553124 = 7318^2

  1. Множители:

p = \frac{7318 + 540}{2} = 3929, \\q = \frac{7318 - 540}{2} = 3389

Мы нашли простые сомножители за 19 итераций. Если бы мы использовали метод Ферма, то смогли бы обнаружить эти сомножители всего за 10 итераций. В данном случае наш метод проигрывает методу Ферма из-за того, что p и q различаются незначительно, поскольку метод Ферма наиболее эффективен именно когда сомножители числа примерно равны между собой.

Попробуем пример с большей абсолютной разницей между p и q.

Пример 2:

N=190223063

Аналогично:

  1. N \bmod 30 = 23

  2. Допустимые дельты: \{2, 22\}

  3. При n = 300 и \delta = 2:

D={30}\cdot{300}+2=9002m^2 = 9002^2 + 4 \cdot 190223063 = 841928256 = 29016^2

  1. Получаем:

p = \frac{29016 + 9002}{2} = 19009, \\q = \frac{29016 - 9002}{2} = 10007

Мы нашли сомножители за 301 итерацию. Алгоритму Ферма потребовалось бы 715 итераций для поиска сомножителей.

Hidden text

При использовании метода Ферма мы бы начали и закончили значениями:

a_0=\lceil\sqrt{190223063}\rceil=13793,\quad \\a=\frac{p+q}{2}=\frac{10007+19009}{2}=14508

Что даёт 14508 - 13793 = 715 итераций.

Пример 3: отрицательное n

N = 1936007 = 2341 \times 827

  1. N \bmod 30 = 17

  2. Допустимые дельты: \{4, 16\}

  3. При n = -51 и \delta = 16:

D={30}\cdot{-51}+16=-1514m^2 = (-1514)^2+4 \cdot 1936007 = 10036224 = 3168^2

  1. Получаем:

p = \frac{-1514 + 3168}{2} = 827, \\q = \frac{|-1514 - 3168|}{2} = 2341

Таблица допустимых дельт (фрагмент)

N \bmod 30

\delta

0

0, 1, ..., 14

1

0, 6

2

1, 4, 11, 14

23

2, 22

29

8, 10, 28

(Полную таблицу см. в препринте)

Сложность алгоритма

Если k — число допустимых дельт (обычно 2–4), то:

O\left( \frac{2k \sqrt{N}}{30} \right) = O\left( \frac{k \sqrt{N}}{15} \right),

где поправочный коэффициент 2 введён из-за того, что мы должны перебирать как положительные, так и отрицательные n.

В худшем случае (при k = 15) данный метод имеет сложность O(\sqrt{N}), что совпадает со сложностью метода Ферма. Однако, из-за того, что в среднем k \approx 3 количество необходимых проверок уменьшается в 30 / (2k) \approx 5 раз, делая данный метод существенно быстрее для сравнимых значений |p - q| \gg 0.

Заключение

Метод решета дельт получился неожиданно простым и в то же время быстрым. Конечно, при работе с очень большими числами он не сравнится с более продвинутыми методами, такими как метод квадратичного решета или общий метод решета числового поля, но при этом он гораздо, нет, не так — он гораздо проще для понимания и реализации. При этом он остаётся достаточно эффективным при работе с числами, состоящими из десятков цифр.

Что мне особенно хочется отметить:

  • он не зависит от размерности N, только от разности |p - q|;

  • его можно легко распараллелить, скорость расчётов при этом растёт линейно (с поправкой на производительность узлов кластера);

  • можно использовать различные стратегии подбора n, что делает его особенно гибким.

Если вы увлекаетесь криптографией, алгоритмами или просто любите математику, а также умеете писать программы — попробуйте реализовать его сами на своем любимом ЯП. Я сделал это на C++, Python и Matlab. А если у вас под рукой есть вычислительный кластер... вдруг получится факторизовать что-то большое? Например, замахнуться на поиск решений RSA-чисел, многие из которых не найдены до сих пор. Если у вас это получится сделать с помощью метода решета дельт, обязательно дайте мне знать, мне будет очень приятно!

Полный препринт на OSF

Hidden text

Препринт опубликован на osf.io, т.к. я не являюсь математиком, не вхожу в академическую среду и у меня нет endorsement на arXiv.

? Комментарии c критикой и идеями по оптимизации — горячо приветствуются!

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


  1. AndriyS
    20.05.2025 06:20
    #28327354

    По ссылке на препринт открывает страницу с ошибкой : DOI Not Found.


    1. d_ilyich
      20.05.2025 06:20
      #28327632

      Кажется, вот правильная


    1. ooptimum Автор
      20.05.2025 06:20
      #28327992

      Очень странно, ещё вчера всё работало. Спасибо, что заметили! Поправил ссылку в статье.


  1. Naf2000
    20.05.2025 06:20
    #28329380

    Таблица огонь. Простые числа лежат только в указанных столбцах потому что в остальных лежат числа, делящиеся на делители 30. Почему именно 30? а не, например, 2*3*5*7=210?

    Вот вы там перебираете n. Какая гарантия, что произойдет остановка (найдете такое число) и/или когда следует остановиться?


    1. ooptimum Автор
      20.05.2025 06:20
      #28329418

      Правильно, в остальных столбцах находятся числа, не являющиеся взаимно простыми с 30. Возможно, мое объяснение оказалось не очень понятным? Что касается 210 - можно попробовать, но вычислений будет больше, т.е. будет менее эффективно. По поводу n - там внутри простая математика. Если вы факторизуете полупростое число, то гарантированно рано или поздно найдете ответ. Как только получите квадратное число при переборе, можете останавливаться - вы нашли решение.


  1. Nemoumbra
    20.05.2025 06:20
    #28329476

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

    Просили критику? Ну, давайте по пунктам...

    1) D = p - q = 30n + δ, где n - целое, а δ - ??? число. Что я должен был подумать при виде лапласиана Δ? Наверное, что дельта лежит во множестве дельт... Ah yes, the floor is made out of floor.

    2) Утверждение, что δ ≡ |p-q| (mod 30) мне кажется странным. Возьмите p = 10, q = 11.

    3) Почему-то автору неочевидно, что (хотя он специально сделал так, что каждый столбец таблицы содержит числа, дающие один конкретный остаток), что столбец произведения чисел из пары столбцов не зависит от самих чисел (x%30 * y%30 ≡ (xy)%30)

    4) Очень хотелось посмотреть, как себя поведёт итоговый алгоритм на каком-нибудь простом числе, например, 10^9 + 7.

    5) Первый шаг алгоритма - взять остаток от деления N на 30. Затем мы залезаем в таблицу и смотрим кандидаты-дельты. Во фрагменте таблицы из конца статьи я вижу строчку, соответствующую остатку 0. Зачем??? Если число разделилось на 30 нацело, мы уже получили разложение p=30, q=N/30.

    6) Окей, ладно, допустим, там не ноль, значит, сидим и для каждой дельты перебираем возможные значения n: вычисляем (30n +δ)^2 + 4N и  проверяем, не получился ли у нас точный квадрат... Стоп, а как мы это делаем? В статье про это ни слова! Вы уверены, что можно проверить, является ли число точным квадратом, не потеряв предполагаемый выигрыш от вашего алгоритма? Тут ведь даже асимптотика может сломаться.

    7) Ну и об асимптотике... Она взята с неба. Во-первых, откуда корень взялся? Мы же перебираем для каждой дельты 2* N/30 == N / 15 значений n. Может, я пропустил где-то упоминание перебора до корня? Да нет, вроде... Во-вторых, для разных остатков по модулю 30 у вас разное кол-во допустимых дельт, т.е. k = k(N) на самом деле, а не константа. А если мы не хотим исследовать эту функцию, то можно сказать, что кол-во всевозможных расстояний между остатками конечное, а значит, k(N) ограничена, т.е. k(N) = O(1). Таким образом мы выкидываем k совсем. А если после этого выкинуть числовые константы, мы получаем что-то типа O(N). Ой.

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


    1. ooptimum Автор
      20.05.2025 06:20
      #28330814

      Любая конструктивная критика — на пользу. Во-первых, я закончил ВУЗ очень давно и я не математик, но я стараюсь разобраться в теме с инженерной и прикладной точки зрения, поэтому я могу допускать ошибки в математической нотации или формулировках. Прошу простить мне этот мой недостаток. Достаточно обоснованно указать на ошибки и я их исправлю. Во-вторых, есть некая разница в принятой математической нотации между советской/российской школой и западной. Непонятные вам обозначения могут быть вызваны этим. Что именно было непонятно? Я постараюсь объяснить.

      переоткрытие базовых фактов арифметики остатков

      Непонятно, что именно вы имеете в виду. Я написал о том, как я пришел к этим находкам. И я старался написать научно-популярную статью, понятную не только узким специалистам, поэтому объяснял очевидные для кого-то и без этого вещи.

      Что я должен был подумать при виде лапласиана Δ? Наверное, что дельта лежит во множестве дельт...

      Это не лапласиан. В общем да, что дельта принадлежит некому множеству. Я не был уверен в том, как это сделать правильно. Предложите лучшее обозначение, чтобы я исправил?

      Утверждение, что δ ≡ |p-q| (mod 30) мне кажется странным. Возьмите p = 10, q = 11.Утверждение, что δ ≡ |p-q| (mod 30) мне кажется странным. Возьмите p = 10, q = 11.

      \delta в этом случае будет 1: |10-11|=1.

      Почему-то автору неочевидно, что (хотя он специально сделал так, что
      каждый столбец таблицы содержит числа, дающие один конкретный остаток),
      что столбец произведения чисел из пары столбцов не зависит от самих
      чисел (x%30 * y%30 ≡ (xy)%30)

      Наверное вы тут что-то не поняли. Я как раз и утверждаю ровно это и даю объяснение, почему это именно так для тех, кому это не очевидно. Более того, именно на этом факте и строится весь метод. Он является ключевым.

      Очень хотелось посмотреть, как себя поведёт итоговый алгоритм на каком-нибудь простом числе,

      Будет считать, пока не переберет все \delta и n, но ничего не найдет. Как и абсолютно любой другой метод факторизации, который также ничего не найдёт. Это же очевидно. Нет?

      Первый шаг алгоритма - взять остаток от деления N на 30. Затем мы
      залезаем в таблицу и смотрим кандидаты-дельты. Во фрагменте таблицы из
      конца статьи я вижу строчку, соответствующую остатку 0. Зачем??? Если
      число разделилось на 30 нацело, мы уже получили разложение p=30, q=N/30.

      Отличное замечание! Действительно, незачем. Это артефакт того, как я работал над алгоритмом. Я написал программу для проверки гипотезы и мне было лень считать большие полупростые, поэтому я наобум печатал что-то в районе десятка цифр, а потом факторизовал. Иногда получались числа, кратные 30 при этом, отсюда и эта строка. У меня, что называется, замылился глаз. Спасибо за то, что указали на это!

      Стоп, а как мы это делаем? В статье про это ни слова! Вы уверены, что
      можно проверить, является ли число точным квадратом, не потеряв
      предполагаемый выигрыш от вашего алгоритма?

      Разве на каждом шаге метода Ферма не нужно делать ровно ту же операцию, что и в решете дельт? Там ведь мы так же проверяем кандидаты на полный квадрат.

      Что касается асимптотики — я сделал, что было в моих силах, но вполне мог допустить здесь ошибку. Я пытался получить помощь профессиональных математиков в этом вопросе, но всем было как-то не до того. Поможете исправить?


      1. Nemoumbra
        20.05.2025 06:20
        #28331372

        И я старался написать научно-популярную статью, понятную не только узким специалистам, поэтому объяснял очевидные для кого-то и без этого вещи.

        Но почему-то функцию Эйлера и значок Z для обозначения множества целых чисел пояснять не стали.

        Предложите лучшее обозначение, чтобы я исправил?

        Да не нужно тут специальных обозначений, просто напишите границы, в которых лежит δ. Если написать `0 <= δ < 30`, то читатель поймёт, что речь об обычном делении с остатком, где n - целая часть, а δ - остаток.

        Думайте об этом так - когда читатель видит использование необъявленного символа (Δ), у него в голове вылетает исключение и статью он закрывает.

        δ в этом случае будет 1

        Ну да, а теперь подставьте p, q и δ в утверждение `p-q = 30n + δ`. Теперь видите проблему? `-1 = 30n + 1 <=> 30n = 2`. Ну это просто false для всех n. Вот почему я сказал, что утверждение кажется мне странным.

        Разве на каждом шаге метода Ферма не нужно делать ровно ту же операцию, что и в решете дельт?

        Да я как-то не думал про метод Ферма, когда это писал. Есть же и лобовой метод перебора до корня - там это не требуется (причём иногда метод Ферма медленнее лобового).

        Что касается асимптотики — я сделал, что было в моих силах, но вполне мог допустить здесь ошибку

        И я, и ещё один комментатор уже объяснили, что, да, вы допустили ошибку. И я уже вычислил правильную асимптотику - получилось O(N). Да, за линию. Да, хуже лобового метода. Мою логику я расписал в прошлом комментарии.

        Что я могу посоветовать... Откройте Youtube, вбейте там в поиске "Борис Трушин арифметика остатков". Посмотрите выпуски "Ботай со мной" N34, 36 и 37. Плюс-минус 35 ещё.

        А с асимптотикой... Посмотрите первую лекцию осеннего семестра по алгоритмам на лектории ФПМИ (1 курс, любой год), после этого возьмите лист А4 и проверьте, что

        1. Функия cos(n)/sqrt(n) + 10000 есть O(1).

        2. Если f(n) = O(n), то f(n) = O(n/2).

        Где читать про длинную арифметику - сходу не скажу, но 100% сейчас должно быть в интернете.


        1. ooptimum Автор
          20.05.2025 06:20
          #28331890

          -1 = 30n + 1 <=> 30n = 2.

          Откуда вы берете -1? И в статье, и в своем комментарии я написал, что там модуль от разницы, т.е. абсолютная величина - нет там минуса. По поводу линии и лобового метода - вы также ошибаетесь.


          1. Nemoumbra
            20.05.2025 06:20
            #28334054

            Откуда вы берете -1?

            Отсюда
            Отсюда

            p - q в статье без модуля в этой строчке. Подставляем 10 и 11 - получаем противоречие.

            По поводу линии и лобового метода - вы также ошибаетесь.

            Просто сказать, что я ошибаюсь... маловато будет. Мою логику я расписал, так что либо укажите точное место, где я ошибся в рассуждениях (с цитатой!), либо признайте свою ошибку.


            1. ooptimum Автор
              20.05.2025 06:20
              #28336048

              Никакого противоречия нет, D может иметь отрицательное значение. Смотрите 3 пример. Про асимптоту - не хуже лобового метода. Если делители есть, то один из них обязательно меньше или равен корню из N. Поскольку мы не ищем делители по отдельности, мы найдем оба не больше, чем за корень из N операций, как при линейном способе. Но на самом деле найдем скорее всего гораздо быстрее, чем линейным способом за счет фильтрации по дельтам.


              1. Nemoumbra
                20.05.2025 06:20
                #28340076

                Никакого противоречия нет, D может иметь отрицательное значение.

                Да не в этом противоречие! Ещё раз повторяю: в статье приведено утверждение `D = p - q = 30n +δ`. Я предложил вам подставить туда p = 10 и q = 11. Мы получим слева минус единицу, а справа: 30n + 1 (сами так сказали в первом комментарии: "δ в этом случае будет 1"!). Вот оно - противоречие! 30n + 1 ни при каких n не равно минус единице.

                Если делители есть, то один из них обязательно меньше или равен корню из N.

                2) Ваша ошибка довольно интересная - вы забыли рассмотреть случай, когда на вход алгоритму подаётся простое число. "Если делители есть..." Это всё замечательно, ну а если их нет? Вот тут-то собака зарыта!

                Ваш алгоритм будет перебирать n и δ в надежде, что 4N + (30n + δ)^2, пока не переберёт все кандидаты, а их у вас 2*N/30 для n и k(N) для δ. То бишь k(N) * N/15 проверок нужно сделать. Т.к. пятнадцать - константа, а k(N) - ограниченная функция, мы их выкидываем из асимптотики. Получаем O(N).


                1. ooptimum Автор
                  20.05.2025 06:20
                  #28342032

                  Смотрите, алгоритм рассматривает как отрицательные значения n, так и положительные. Да, вы правы, если p = 10 и q = 11, то D получится отрицательным и эта ветка никогда не найдет решение. Но алгоритм проверит и обратный случай, когда p = 11 и q = 10 - в этом случае решение будет найдено: D = 30 * 0 + 1 = 1. Посмотрите третий пример - ни при каких положительных значениях n решение не будет найдено, но оно найдено при отрицательном n. Ваш пример точно такой же - решения нет, когда мы считаем, что p < q, но оно есть, когда q > p. Из-за коммутативности операции умножения нет разницы, что мы примем за q, а что - за p, 10 или 11, но для алгоритма - есть. Мы пробуем оба варианта (знак у n).

                  Зачем пытаться разложить на множители простое число? Только для вычисления O-большого? Ну хорошо, пусть будет в невозможном случае O(N). Но меня не очень интересовали невозможные случаи, я рассматривал только случаи применения алгоритма для разложения на сомножители составных чисел.


      1. Refridgerator
        20.05.2025 06:20
        #28331594

        Это не лапласиан

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


  1. d_ilyich
    20.05.2025 06:20
    #28329482

    Раз уж речь о закономерностях в распределении простых чисел, недавно наткнулся на публикацию Finding the nearest prime to any large integer (по ссылке PDF). Там все числа расположены по шестиугольной спирали, и утверждается, что простые числа лежат строго на двух из радиальных линий.


    1. wataru
      20.05.2025 06:20
      #28330982

      Это чем-то мне напоминает замечательное открытие юных натуралистов, которые много месяцев изучали муравьев и нашли удивительную закономерность, что граница муравейников примерно в 3 раза длинее их ширины.


  1. confection
    20.05.2025 06:20
    #28330584

    ~200 лет?


    1. ooptimum Автор
      20.05.2025 06:20
      #28330588

      Верно!


  1. seregablog
    20.05.2025 06:20
    #28330688

    В статье описан метод Ферма, только очень запутанно и громоздко. По сравнению со стандартным описанием разница в следующем:

    1. Вместо разложения N=x^2 - y^2 ищется разложение 4N = m^2 - D^2 - это разумеется, безразлично
    2. При переборе число D представляется не в виде sqrt(N) + k, в виде 30n+ δ - представлять число можно как угодно, это принципиально ни на что не влияет

    Всё, что связано с числом 30 является элементарными рассуждениями об арифметике остатков. Конкретное число 30 не важно. По сути это сделано для уменьшения количества возможных значение δ при переборе D. Только это не имеет значения, потому что перебор идёт и по δ, и по n. При этом количество δ ограничено заранее известной небольшой константой, в вот n=O(N).

    В разделе "Сложность алгоритма" множество ошибок:

    1. В O-нотации пишутся коэффициенты k, 30, 2, 15, которые по сути являются константами
    2. "В худшем случае (при k = 15) данный метод имеет сложность" - худший случай это когда разница между делителями большая, а не k=15
    3."Однако, из-за того, что в среднем k \approx 3 количество необходимых проверок уменьшается в 30 / (2k) \approx 5 раз, делая данный метод существенно быстрее для сравнимых значений |p - q| \gg 0." - вы сравниваете асимптотическую оценку метода Ферма (в которой уже нет констант) с оценкой "своего" алгоритма в которой дописали константы. Так просто некорректно делать


    1. ooptimum Автор
      20.05.2025 06:20
      #28330850

      В основе — да, идея похожа на Ферма (хотя я и не вдохновлялся им, просто так получилось). Но в моём методе добавлена фильтрация по остаткам и таблица дельт, которая отсекает заведомо невозможные варианты. Это экономит шаги на практике и втором пример показывает, что выигрыш может быть ощутимым. Или он вас не убедил?


      1. seregablog
        20.05.2025 06:20
        #28340910

        Прежде всего, нет никакого вашего метода, это всё тот же метод Ферма, в котором числа перебираются в другом порядке.

        Это экономит шаги на практике

        Это-то как раз нигде не доказано. А подобрать удачный пример легко. Скажем, алгоритм, который всегда первым делителем проверяет 42, очень эффективно факторизует некоторые числа, и сильно экономит шаги на практике в этом случае.

        Сравним ваш способ перебора чисел и классический способ перебора в методе Ферма.

        Если говорить об асимптотической сложности, то ваш способ и обычный (т. е. последовательный перебор sqrt(N) +1, sqrt(N) + 2,...) дают одинаковую сложность, потому что это всё тот же метод Ферма (вам уже не раз указали, что раздел "Сложность алгоритма" написан некорректно).

        Давайте попробуем сравнить количество итераций в худшем случае:
        Пусть N=pq, p > q
        В вашем случае их будет (2kN)/30
        В обычном случае не более (p-q) / 2. Если меньший делитель равен 3, то (p-q)/2 = (N/3 - 3) / 2 = N/6

        Ваш способ будет эффективнее, если (2kN)/30 < N/6, т.е. при k<=2. По вашей таблице есть 8 строк из 29, для которых это выполняется. При этом если минимальный делитель будет больше 8, то таких значений не будет вообще. Также обычный способ перебора как-раз намного более прост и нагляден, чем ваш.


        1. ooptimum Автор
          20.05.2025 06:20
          #28342108

          Пусть N=pq, p > q
          В вашем случае их будет (2kN)/30

          В другой ветке комментариев я уже писал, что если есть решение, то оно будет найдено в любом случае не больше, чем за \sqrt(N) операций, т.к. находятся сразу оба сомножителя, один из которых гарантированно меньше или равен корню из N. Т.е. не \frac{2kN}{30}, а \frac{2k\cdot \sqrt{N}}{30} или \frac{k\cdot\sqrt{N}}{15}, как в статье. При каких условиях

          \frac{\sqrt{N}}{15}>p-q? Я мог ошибиться в расчётах (сейчас у меня ночь), но кажется, если числа p и q отличаются менее чем на 7%. В этом случае, данный алгоритм может проиграть.

          Что касается подбора примеров, то в этом моя совесть совершенно чиста. Верите вы или нет, но я брал пару случайных простых чисел и работал с ними, ничего не подбирая. Если вы все ещё не убеждены, то я планирую написать статью об алгоритмической реализации данного метода и опубликовать код на GitHub - мы сможем измерить потребное количество операций для любых сомножителей на практике. Там, кстати, есть один парадокс, который я не понимаю и, возможно, вы сможете его объяснить. Он связан с ещё одной оптимизацией, которую я обнаружил опытным путём и не могу объяснить её математически - я слишком слаб для этого, поэтому я ничего не написал в статье про неё. Я вижу, что вы хорошо разбираетесь в математике и возможно поможете разобраться.


  1. wataru
    20.05.2025 06:20
    #28330978

    Интересная идея. Но я бы не переоценивал ее практическую значимость.

    Сложность O(sqrt(N)*k/30).

    Есть еще более простой метод, который почти не медленнее, проще для понимания, легче параллелится и все остальное.

    Перебираем все числа до 2 до sqrt(N) и проверяем, являются ли они делителями N. Для ускорения проверяем не все числа, а только те, что взаимнопросты с 30 (вида 30k+d). Мы же простой делитель ищем.

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

    Еще интересный вопрос, а могли бы вы привести таблицу? Сдается мне, что оно не всегда сокращает количество дельт и для каких-то остатков N по модулю 30 может дать больше 8 дельт.

    @VAEСмотрите, у вас конкурент. Только тут используется обычная, общепринятая, всем понятная нотация, нет исторических отсылок с зашкаливающим пафасом, метод формально описан и приведена оценка его скорости. И сложность материала автор адекватно поставил "средний". Ваши статьи по сравнению с этим никуда не годятся. И результат налицо. Основная идея через формулу разницы квадратов почти такая же как у вас, но тут люди ее принимают и плюсы статье ставят, в отличии от ваших статей, где почему-то одни хейтеры собрались.


    1. ooptimum Автор
      20.05.2025 06:20
      #28331938

      Перебираем все числа до 2 до sqrt(N) и проверяем, являются ли они делителями N. Для ускорения проверяем не все числа, а только те, что взаимнопросты с 30 (вида 30k+d). Мы же простой делитель ищем.

      Вы описали ровно то, что этот метод и делает. Только вы предложили проверять все взаимнопростые, а я проверяю только подходящие - те, которые прошли фильтр, для этого таблица дельт и нужна.

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

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

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

      Что касается извлечения корня, тут без этого не обойтись. Но в библиотеке GMP есть быстрая функция проверки на то, является ли число полным квадратом - я использую её.


      1. wataru
        20.05.2025 06:20
        #28333122

        Вы описали ровно то, что этот метод и делает.

        Нет, ваш метод не проверяет, делится ли N на 30n+d. Вы считаете делитель по формуле (30n+d-k)/2, если вычисленное k=sqrt(4N+(30n+d)^2) целое. За счет этого вы фильтруете какие-то дельты, да.


        1. ooptimum Автор
          20.05.2025 06:20
          #28336054

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


          1. wataru
            20.05.2025 06:20
            #28337208

            Нет, у вас, кстати, надо проверять и не только взаимнопростые с 30 числа. Как раз потому что у вас другая логика алгоритма, основанная на другой формуле. Простой алгоритм использует формулу N=xk и перебирает x, ваш использует N=(x^2-k^2)/4 и тоже перебирает x. В простом, поскольку нас интересуют только простые x, можно исключить какие-то дельты. В вашем, поскольку разность квадратов должна давать определенный остаток по модулю 30, а квадраты дают только определенное подмножество остатоков, можно подобрать какие остатки должен иметь x. Тут другая логика отсечения, которая вытекает из выбранной формулы.


  1. wataru
    20.05.2025 06:20
    #28330988

    Про препринт все-таки скажу, в глаза бросилось: называть свой метод по своей фамилии, при том что вы сами говорите, что не математик - это вопиющая пошлость.


    1. Refridgerator
      20.05.2025 06:20
      #28331514

      Это же и главный критерий, по которой я пропускаю подобные статьи не читая (не в обиду автору). Настоящие математики называют свои работы по сути, а остальное делает уже история и признание других математиков. Например, оригинальная работа Чебышева про его знаменитые многочлены называется не "Многочлены Чебышева", а "О функциях, наименее уклоняющихся от нуля".