Комментарии 6
В общем случае, для вычисления σ(n) для произвольного n вам понадобятся все предыдущие значения σ, поскольку в начале рекурсивной формулы стоят σ(n-1) и σ(n-2). Даже если предположить, что какую-то часть из предыдущих значений σ можно вычислить более эффективно за счёт частичной факторизации, итоговая сложность O(n) не изменится.
Если я не ошибаюсь, есть алгоритм для подсчёта σ(n) за O(n^(2/3) (log log n)^(1/3)). (Такой точно есть для Φ(n), суммы φ(i) для 1<=i<=n, и для некоторых других мультипликативных функций). Но даже этот метод сложнее, чем простой перебор всех делителей до n^(1/2).
Пока что для нахождения x и y, таких что x^2=y^2 (mod n) и x!=y, ничего лучше общего метода решета числового поля не придумали.
Можете ли вы использовать ваши наработки для разложения, например, вот этого числа?
Так в Г2± – модели НРЧ в клетке () всегда лежит сумма делителей N, если само число N помещено в клетке ().
Смотрим клетку с числом 21. Ищем сумму делителей (3+7=10). Не находим.
Вопрос — «в [соседней] клетке всегда лежит сумма делителей» — это к чему было сказано?
В статье приведен пример 3 поясняющий это для числа 147 = 21.7. Сумма равна не 21+7 =28, а 21+7 +1 +147 = 176.
Но тем не менее, закономерность интересная и может быть в совокупности с другими даже найдёт какое-то применение. Хотя пока применений не видно.
Если Вы знаете координаты N, то знаете и его делите, поскольку y^2-x^2=(y+x)(y-x)
Метод ферма просто перебирает (A+I) ^2-N, пока не найдётся полный квадрат. Расширенный метод ещё подбирает k чтобы kN было более квадратным числом за счёт того, что факторы k группировались к p и q, сближая k1*p и k2*q, но общего метода подбора k нет. Поэтому квадратичное решето попросту подбирает побольше B-гладких чисел среди x^2+N и затем подбирает произведение нескольких таких гладких, чтобы все степени входящих простых были четными. Общее решето числового поля использует более быстрые полиномы чем вторая степень за счёт чего ещё ускоряет результат нахождения подходящей разницы квадратов.
Алгоритм Ферма можно ускорить так же как и метод перебора делителей. Перебирать делители можно только простые или хотя бы похожие на простые. Решето Эратосфена работает довольно быстро, быстрее чем пробные деления на все подряжд делители. Можно брать только нечетные, т.е. вида 2k+1, можно брать праймориальные модули 2*3, 2*3*5, и т.д. 6i+-1 или 30i+-(1,7,11,13) дают не только простые, но довольно экономны. Аналогичным образом ускоряется и метод Ферма. Факт о разной четности y^2 и х^2 легко развивается в разрешенные вычеты по праймориальным модулям. Более того, можно брать не полный праймориал, а только факторы, по которым N даёт квадратичным невычет. Но это ускоряет перебор в несколько раз, не экспоненциально.
Поработайте с вашими идеями с gpt o1 он быстро поможет отсеять непродуктивные пути, скрывая тривиальность многих идей, их тождественность уже известным фактам.
Я тоже много времени посвятил таблице разностей квадратов, более того, если вы возьмёте полу целые числа Получается много интереснее, а ещё интереснее если Вы возьмёте шаг обратный малым праймориалам, хотя бы 1/6 или 1/30. Очень красиво. Но в задаче факторизации это не слишком помогает. А вот представление таких полу целых или обратнопраймориальных в качестве фритов (фракций битов) для разреженного представления N по менее чем двоичным основания даёт интересное направление для поиска гладких множителей к N, дающих факторизации y^2-kN=x^2
Факторизация чисел и сумма неизвестных делителей. Часть IV