Comments 42
По ссылке на препринт открывает страницу с ошибкой : DOI Not Found.
Кажется, вот правильная
Очень странно, ещё вчера всё работало. Спасибо, что заметили! Поправил ссылку в статье.
Таблица огонь. Простые числа лежат только в указанных столбцах потому что в остальных лежат числа, делящиеся на делители 30. Почему именно 30? а не, например, 2*3*5*7=210?
Вот вы там перебираете n. Какая гарантия, что произойдет остановка (найдете такое число) и/или когда следует остановиться?
Правильно, в остальных столбцах находятся числа, не являющиеся взаимно простыми с 30. Возможно, мое объяснение оказалось не очень понятным? Что касается 210 - можно попробовать, но вычислений будет больше, т.е. будет менее эффективно. По поводу n - там внутри простая математика. Если вы факторизуете полупростое число, то гарантированно рано или поздно найдете ответ. Как только получите квадратное число при переборе, можете останавливаться - вы нашли решение.
Не в обиду автору, но читать было сложно. Много рукомахания, переоткрытие базовых фактов арифметики остатков, непонятные обозначения.
Просили критику? Ну, давайте по пунктам...
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), а что-то как минимум линейное (кроме совсем простых действий, скажем, чётность узнать). Предлагаю автору попробовать в этом разобраться.
Любая конструктивная критика — на пользу. Во-первых, я закончил ВУЗ очень давно и я не математик, но я стараюсь разобраться в теме с инженерной и прикладной точки зрения, поэтому я могу допускать ошибки в математической нотации или формулировках. Прошу простить мне этот мой недостаток. Достаточно обоснованно указать на ошибки и я их исправлю. Во-вторых, есть некая разница в принятой математической нотации между советской/российской школой и западной. Непонятные вам обозначения могут быть вызваны этим. Что именно было непонятно? Я постараюсь объяснить.
переоткрытие базовых фактов арифметики остатков
Непонятно, что именно вы имеете в виду. Я написал о том, как я пришел к этим находкам. И я старался написать научно-популярную статью, понятную не только узким специалистам, поэтому объяснял очевидные для кого-то и без этого вещи.
Что я должен был подумать при виде лапласиана Δ? Наверное, что дельта лежит во множестве дельт...
Это не лапласиан. В общем да, что дельта принадлежит некому множеству. Я не был уверен в том, как это сделать правильно. Предложите лучшее обозначение, чтобы я исправил?
Утверждение, что δ ≡ |p-q| (mod 30) мне кажется странным. Возьмите p = 10, q = 11.Утверждение, что δ ≡ |p-q| (mod 30) мне кажется странным. Возьмите p = 10, q = 11.
в этом случае будет 1: 
.
Почему-то автору неочевидно, что (хотя он специально сделал так, что
каждый столбец таблицы содержит числа, дающие один конкретный остаток),
что столбец произведения чисел из пары столбцов не зависит от самих
чисел (x%30 * y%30 ≡ (xy)%30)
Наверное вы тут что-то не поняли. Я как раз и утверждаю ровно это и даю объяснение, почему это именно так для тех, кому это не очевидно. Более того, именно на этом факте и строится весь метод. Он является ключевым.
Очень хотелось посмотреть, как себя поведёт итоговый алгоритм на каком-нибудь простом числе,
Будет считать, пока не переберет все и 
, но ничего не найдет. Как и абсолютно любой другой метод факторизации, который также ничего не найдёт. Это же очевидно. Нет?
Первый шаг алгоритма - взять остаток от деления N на 30. Затем мы
залезаем в таблицу и смотрим кандидаты-дельты. Во фрагменте таблицы из
конца статьи я вижу строчку, соответствующую остатку 0. Зачем??? Если
число разделилось на 30 нацело, мы уже получили разложение p=30, q=N/30.
Отличное замечание! Действительно, незачем. Это артефакт того, как я работал над алгоритмом. Я написал программу для проверки гипотезы и мне было лень считать большие полупростые, поэтому я наобум печатал что-то в районе десятка цифр, а потом факторизовал. Иногда получались числа, кратные 30 при этом, отсюда и эта строка. У меня, что называется, замылился глаз. Спасибо за то, что указали на это!
Стоп, а как мы это делаем? В статье про это ни слова! Вы уверены, что
можно проверить, является ли число точным квадратом, не потеряв
предполагаемый выигрыш от вашего алгоритма?
Разве на каждом шаге метода Ферма не нужно делать ровно ту же операцию, что и в решете дельт? Там ведь мы так же проверяем кандидаты на полный квадрат.
Что касается асимптотики — я сделал, что было в моих силах, но вполне мог допустить здесь ошибку. Я пытался получить помощь профессиональных математиков в этом вопросе, но всем было как-то не до того. Поможете исправить?
И я старался написать научно-популярную статью, понятную не только узким специалистам, поэтому объяснял очевидные для кого-то и без этого вещи.
Но почему-то функцию Эйлера и значок 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 и проверьте, что
Функия cos(n)/sqrt(n) + 10000 есть O(1).
Если f(n) = O(n), то f(n) = O(n/2).
Где читать про длинную арифметику - сходу не скажу, но 100% сейчас должно быть в интернете.
-1 = 30n + 1 <=> 30n = 2.
Откуда вы берете -1? И в статье, и в своем комментарии я написал, что там модуль от разницы, т.е. абсолютная величина - нет там минуса. По поводу линии и лобового метода - вы также ошибаетесь.
Откуда вы берете -1?
p - q в статье без модуля в этой строчке. Подставляем 10 и 11 - получаем противоречие.
По поводу линии и лобового метода - вы также ошибаетесь.
Просто сказать, что я ошибаюсь... маловато будет. Мою логику я расписал, так что либо укажите точное место, где я ошибся в рассуждениях (с цитатой!), либо признайте свою ошибку.
Никакого противоречия нет, D может иметь отрицательное значение. Смотрите 3 пример. Про асимптоту - не хуже лобового метода. Если делители есть, то один из них обязательно меньше или равен корню из N. Поскольку мы не ищем делители по отдельности, мы найдем оба не больше, чем за корень из N операций, как при линейном способе. Но на самом деле найдем скорее всего гораздо быстрее, чем линейным способом за счет фильтрации по дельтам.
Никакого противоречия нет, 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).
Смотрите, алгоритм рассматривает как отрицательные значения 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). Но меня не очень интересовали невозможные случаи, я рассматривал только случаи применения алгоритма для разложения на сомножители составных чисел.
Да алгоритм тут не при чём! Читающие статью видят вот это (см. скриншот):
Прежде, чем читать дальше, читатель подставляет p = 10, q = 11 сюда, от греха подальше. Видит D = -1 = 30n + 1. Это ни при каком n не выполнено, значит, автор где-то ошибся. Статью можно, в целом, закрывать. Что там какой-то алгоритм потом описывается - уже неважно.
Душню ли я? Есть такое... Но это прям сразу бросилось в глаза.
Что касается асимптотики, в другой ветке вам довольно хорошо расписали, почему не доказано наличие корня (если коротко - перебираются не числа до корня, а просто какие-то числа, которые могут дать два делителя в итоге, например, на последней итерации алгоритма).
Можете, кстати, добавить счётчик в программу и после разложения сравнить кол-во опробованных пар (n, δ), прежде чем получился квадрат, с корнем из N. Затем прогоните программу на всех числах подряд (составных, конечно, раз уж простые вы не поддерживаете). Честно интересно, насколько на практике выполняется ваше голословное утверждение.
Хорошо, я сам просил критиковать статью. Смотрите, ваш пример с 10 и 11 (N=11*10=110) решается данным методом так:
Множители:
Данное решение найдено на первом же шаге. Если мы не будем останавливать алгоритм, то найдем ещё два решения:
Множители:
Множители:
Как вы предлагаете улучшить статью, чтобы не было такого восприятия, какое было у вас?
Касательно счётчика: предлагаю вам дать мне, скажем, 5 полупростых чисел, где p и q различаются, скажем, на порядок. Прошу об этом вас, чтобы не было обвинений, что я подобрал числа. Только не давайте слишком большие, 9 или 10 разрядов вполне достаточно - я не хочу слишком долго ждать результат. Сравним число операций с методом Ферма, раз я сам выбрал его за эталон. Согласны?
Это не лапласиан
Поясняю: то был тонкий намёк на то, что вам не известно про понятие лапласиана, иначе вы не выбрали бы этот символ (так как он уже занят и общепринят). То есть автоматически классифицирует вас в группу дилетантов, ищущих решения сложных задач простыми, но "хитрыми" способами.
Раз уж речь о закономерностях в распределении простых чисел, недавно наткнулся на публикацию Finding the nearest prime to any large integer (по ссылке PDF). Там все числа расположены по шестиугольной спирали, и утверждается, что простые числа лежат строго на двух из радиальных линий.
~200 лет?
В статье описан метод Ферма, только очень запутанно и громоздко. По сравнению со стандартным описанием разница в следующем:
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
3."Однако, из-за того, что в среднем 
количество необходимых проверок уменьшается в 
раз, делая данный метод существенно быстрее для сравнимых значений 
." - вы сравниваете асимптотическую оценку метода Ферма (в которой уже нет констант) с оценкой "своего" алгоритма в которой дописали константы. Так просто некорректно делать
В основе — да, идея похожа на Ферма (хотя я и не вдохновлялся им, просто так получилось). Но в моём методе добавлена фильтрация по остаткам и таблица дельт, которая отсекает заведомо невозможные варианты. Это экономит шаги на практике и втором пример показывает, что выигрыш может быть ощутимым. Или он вас не убедил?
Прежде всего, нет никакого вашего метода, это всё тот же метод Ферма, в котором числа перебираются в другом порядке.
Это экономит шаги на практике
Это-то как раз нигде не доказано. А подобрать удачный пример легко. Скажем, алгоритм, который всегда первым делителем проверяет 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, то таких значений не будет вообще. Также обычный способ перебора как-раз намного более прост и нагляден, чем ваш.
Пусть N=pq, p > q
В вашем случае их будет (2kN)/30
В другой ветке комментариев я уже писал, что если есть решение, то оно будет найдено в любом случае не больше, чем за 
операций, т.к. находятся сразу оба сомножителя, один из которых гарантированно меньше или равен корню из N. Т.е. не 
, а 
или 
, как в статье. При каких условиях
? Я мог ошибиться в расчётах (сейчас у меня ночь), но кажется, если числа p и q отличаются менее чем на 7%. В этом случае, данный алгоритм может проиграть.
Что касается подбора примеров, то в этом моя совесть совершенно чиста. Верите вы или нет, но я брал пару случайных простых чисел и работал с ними, ничего не подбирая. Если вы все ещё не убеждены, то я планирую написать статью об алгоритмической реализации данного метода и опубликовать код на GitHub - мы сможем измерить потребное количество операций для любых сомножителей на практике. Там, кстати, есть один парадокс, который я не понимаю и, возможно, вы сможете его объяснить. Он связан с ещё одной оптимизацией, которую я обнаружил опытным путём и не могу объяснить её математически - я слишком слаб для этого, поэтому я ничего не написал в статье про неё. Я вижу, что вы хорошо разбираетесь в математике и возможно поможете разобраться.
Верите вы или нет, но я брал пару случайных простых чисел и работал с ними, ничего не подбирая
Вполне возможно. Случайно выбирая числа, рано или поздно попадётся удачное. Суть в том, что ваш пример ничего доказывать в принципе не может
Он связан с ещё одной оптимизацией, которую я обнаружил опытным путём и не могу объяснить её математически - я слишком слаб для этого
Вам в комментариях намекают, что если вы не сильны в математике, то излишне самоуверенно заявлять об изобретении нового алгоритма факторизации чисел, выпускать препринт, да называть его собственным именем
Вы много раз написали про sqrt(N), но ни разу не доказали. Один из делителей не превосходит sqrt(N), это правда. Из этого напрямую не следует, что ваш способ найдёт этот делитель за sqrt(N) итераций.
В методе перебора делителей в худшем случае понадобится sqrt(N) итераций, потому что делители перебираются последовательно. В вашем способе числа D перебираются в виде 30n+ δ , где n=-N/30 до N/30, а δ - возможные остатки (всего их k). Эти числа, в отличие от перебора делителей, идут не последовательно и аналогичное доказательство не проходит. Из описания в статье следует, что в худшем случае нужно перебрать (2kN)/30 чисел. Никакого обоснования для количества sqrt(N) в статье нет.
Если способ действительно всегда находит делитель не более чем за sqrt(N) операций, приведите математическое доказательство этого факта.
Я пока не знаю, как доказать это математически, но могу сделать это практически. Я взял 50 случайных пар простых 5-значных 
и 
и определил количество шагов для поиска решения. В 9 случаях из 50 метод решета дельт был медленнее метода Ферма - при близких и , в остальных случаях быстрее. Самое быстрое решение было на паре 17029*56737 - данным методом решение находится за 664 шага, а методу Ферма для этого требуется 5799 шагов, т.е. он в 8,73 раза медленнее на данном примере. В среднем получилось, что метод решета дельт быстрее метода Ферма примерно в 3 раза. Все решения, найденные данным методом, были найдены за менее чем 
шагов.
Я подготовил таблицу с этими данными, но не могу вставить её в комментарий так, чтобы форматирование сохранилось (жду ответа от модераторов, как это сделать). Если вам всё ещё интересно, то давайте оставим споры и обвинения, и попробуем совместно улучшить описание метода. В конце концов, это пойдет на пользу всем.
Я добавил сравнительную таблицу непосредственно в статью после оценки сложности.
Интересная идея. Но я бы не переоценивал ее практическую значимость.
Сложность O(sqrt(N)*k/30).
Есть еще более простой метод, который почти не медленнее, проще для понимания, легче параллелится и все остальное.
Перебираем все числа до 2 до sqrt(N) и проверяем, являются ли они делителями N. Для ускорения проверяем не все числа, а только те, что взаимнопросты с 30 (вида 30k+d). Мы же простой делитель ищем.
Использование разности квадратов у вас довольно хитро и возможно действительно позволяет сократить количество различных дельт с 8 до 2, но требует больше вычислений. Тут возведение в квадрат, сумма, а потом извлечение корня вместо одного деления. Плюс надо еще как-то модифицировать алгоритм извлечения корня, чтобы сразу проверить на целочисленность. А потом еще надо вычислить сами делители. Не факт, что это будет быстрее на самом деле.
Еще интересный вопрос, а могли бы вы привести таблицу? Сдается мне, что оно не всегда сокращает количество дельт и для каких-то остатков N по модулю 30 может дать больше 8 дельт.
@VAEСмотрите, у вас конкурент. Только тут используется обычная, общепринятая, всем понятная нотация, нет исторических отсылок с зашкаливающим пафасом, метод формально описан и приведена оценка его скорости. И сложность материала автор адекватно поставил "средний". Ваши статьи по сравнению с этим никуда не годятся. И результат налицо. Основная идея через формулу разницы квадратов почти такая же как у вас, но тут люди ее принимают и плюсы статье ставят, в отличии от ваших статей, где почему-то одни хейтеры собрались.
Перебираем все числа до 2 до sqrt(N) и проверяем, являются ли они делителями N. Для ускорения проверяем не все числа, а только те, что взаимнопросты с 30 (вида 30k+d). Мы же простой делитель ищем.
Вы описали ровно то, что этот метод и делает. Только вы предложили проверять все взаимнопростые, а я проверяю только подходящие - те, которые прошли фильтр, для этого таблица дельт и нужна.
Использование разности квадратов у вас довольно хитро и возможно действительно позволяет сократить количество различных дельт с 8 до 2, но требует больше вычислений. Тут возведение в квадрат, сумма, а потом извлечение корня вместо одного деления. Плюс надо еще как-то модифицировать алгоритм извлечения корня, чтобы сразу проверить на целочисленность. А потом еще надо вычислить сами делители. Не факт, что это будет быстрее на самом деле.
Это лишь математическая нотация. В реальном алгоритме умножения нет вообще. На самом деле каждое новое значение D вычисляется как член двух арифметических прогрессий - 2 операции сложения. Возможно, у меня будет время на вторую статью с описанием алгоритма с точки зрения программиста, в которой я опишу практическую реализацию алгоритма.
Если бы у нас был метод нахождения пересечения двух прогрессий - мы бы нашли ответ за одну операцию, т.к. все квадратные числа также являются членами прогрессии.
Что касается извлечения корня, тут без этого не обойтись. Но в библиотеке GMP есть быстрая функция проверки на то, является ли число полным квадратом - я использую её.
Вы описали ровно то, что этот метод и делает.
Нет, ваш метод не проверяет, делится ли N на 30n+d. Вы считаете делитель по формуле (30n+d-k)/2, если вычисленное k=sqrt(4N+(30n+d)^2) целое. За счет этого вы фильтруете какие-то дельты, да.
Я имел в виду, что проверяются также взаимнопростые числа, как и в вашем предложении, только не все, о чем пишете вы, а подходящие. Это вопрос логики работы алгоритма же, а не конкретной формулы.
Нет, у вас, кстати, надо проверять и не только взаимнопростые с 30 числа. Как раз потому что у вас другая логика алгоритма, основанная на другой формуле. Простой алгоритм использует формулу N=xk и перебирает x, ваш использует N=(x^2-k^2)/4 и тоже перебирает x. В простом, поскольку нас интересуют только простые x, можно исключить какие-то дельты. В вашем, поскольку разность квадратов должна давать определенный остаток по модулю 30, а квадраты дают только определенное подмножество остатоков, можно подобрать какие остатки должен иметь x. Тут другая логика отсечения, которая вытекает из выбранной формулы.
Что вы под результатом разумеете?
Но я бы не переоценивал ее практическую значимость.
Я добавил в статью дополнительную информацию со сравнением количества потребных шагов для нахождения решения для двух методов - решета дельт и Ферма. Ускорение примерно в 3 раза в среднем может иметь практическую значимость, как считаете?
Не, не решает. Ускорение в несколько раз достигается просто обычной программной оптимизацией. Мой личный рекорд - ускорение в 40 раз, используя ассемблер. И в целом ради ускорения в 2-3 раза я за оптимизацию не берусь.
Ну и практическую значимость имеет разложение не на два множителя, а на их произвольное количество. И сравнивать результат надо не с самым простым алгоритмом по количеству итераций, а с его реализаций в популярных мат.пакетах. Если ваш алгоритм разложит число на множители в 10 раз быстрее (по секундомеру), чем например Mathematica - вот тогда да, атмосфера в комментариях будет совсем другой.
Вы говорите об одном виде оптимизации, я я - о другом. Один и тот же алгоритм можно реализовать на разных ЯП и, очевидно, скорость работы будет разной, но число шагов останется одинаковым. Говоря про ускорение я имел в виду сокращение именно числа требуемых шагов для нахождения результата.
Про препринт все-таки скажу, в глаза бросилось: называть свой метод по своей фамилии, при том что вы сами говорите, что не математик - это вопиющая пошлость.
Это же и главный критерий, по которой я пропускаю подобные статьи не читая (не в обиду автору). Настоящие математики называют свои работы по сути, а остальное делает уже история и признание других математиков. Например, оригинальная работа Чебышева про его знаменитые многочлены называется не "Многочлены Чебышева", а "О функциях, наименее уклоняющихся от нуля".
Основное описание метода я готовил именно для публикации здесь. Публикация препринта с именным методом - это защита от того, что кто-то с прищуренными глазами утащит его и опубликует под своим. Какие времена, такие и нравы. Предлагаю на этом закрыть тему моральных аспектов и сосредоточиться на главном.
Решето дельт — простой способ раскладывать числа на множители, о котором вам не рассказывали