А что мы знаем о числе N = x * y, которое необходимо факторизировать?

1. Корень из N - для начала поиска чисел А и В.

2. Длина в битах - можно использовать для поиска окрестностей единиц.

3. Последние цифры - для определения последних цифр чисел x и y, и для определения шага (x + y) или А.

А что ещё?

Есть одно но:
мы не можем найти все такие остатки для больших чисел.

А если пользуясь термином "сокращает количество ... примерно в два раза",
то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз?

Я тут попробовал по китайской теореме смотрел остатки степеней 2 по модулю N, чтобы определить единицу.

Где-то после 2^20 идёт серьёзное увеличение по времени расчёта.

Видел публикации, где говорилось о более удобном модуле - 20.

Меньше выборок по остаткам.

А по разным простым модулям будут сложные построения.

Или все остатки собирать в одном массиве, чтобы число в массиве было равно количеству модулей.

То есть, должно выполняться уравнение по квадратичным вычетам:
(x+y) ² /4 - N = (x-y) ² /4 mod p

Обычно, в тесте Ферма при определения остатков перебираются показатели степени для определённого основания степени.

А есть ли работы по перебору оснований степени?

А почему рассматривается только s или d?

Необходимо рассматривать комбинацию разностей остатков для s и d.

В продолжение 22144685 :

4. Величину s = (х + y) mod 6

Решил поработать с р-методом логарифмирования.

Много разных публикаций с разными алгоритмами.
Скачал на Питоне программу, которая не всегда работает
https://ru.wikibooks.org/wiki/Реализации_алгоритмов/P-метод_Полларда_дискретного_логарифмирования

Было бы интересно обсудить данный метод.

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

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

Допустим, есть число n = x * y, где x и y – два простых числа.
Над числом n есть кольцо вычетов Zn.

Согласно алгоритму Гельфонда –Шенкса можно построить в кольце вычетов Zn две сетки чисел,
с помощью которых можно найти все вычеты для определённого некоторого числа q,
которых будет несколько в Zn.
Получается сетка чисел размером m = (n^(1/2) x (n^(1/2),
тогда, количество элементов сетки будет m.
И для определения числа q (или нескольких q) будет «шаг» на отрезке (1, n-1),
равный n/m .

Согласно 22097181 ищется число q = 1, и не каждое число, а только определённое число q =1,
на «расстоянии» (x + y) - 1 от последнего элемента кольца вычетов Zn.

Для этого вычета q = 1 достаточно ограничить отрезок (2*(n^(1/2), k*(n^(1/2)),
где k надо посчитать после учёта малых делителей.
Получается новая сетка чисел размером m1 = (((k-2)*(n^(1/2))^(1/2)) x (((k-2)*(n^(1/2))^(1/2)).

И «шаг» для определения числа A = (х + y)/2 будет равен 2*m / m1.

А какой «шаг» даст нам метод Ферма с перебором простых чисел?

У алгоритма Гельфонда -Шенкса есть одно неудобство:
необходимо сравнивать каждое число второй сетки с каждым числом первой сетки.

А если на первую сетку "наложить" третью сетку?
Некоторая сортировка.

Тогда в несколько раз можно уменьшить количество сравнений между первой и второй сетками.

mayton,

почти во всех известных методах факторизации за основу берется уравнение n = A^2 - B^2.
(или во всех ?)

А если за основу методов факторизации взять 2^(x + y) = 2^(n + 1) mod n?

Или за основу взять лучшее от этих двух уравнений.

Второе уравнение применяется только про дискретном логарифмировании.(?)

Интересный метод, но в нём нет 2^.
Я это имел в виду, а есть там + или - , то это уже вторично.

Заинтересовал метод факторизации (p-1) - метод Полларда.

И появилась задачка для выходных:

найти с помощью этого метода делители числа 3277.
То есть, выбрать с помощью этого метода набор простых делителей со степенями
для определения делителей числа 3277

https://ru.wikipedia.org/wiki/P?1-метод_Полларда

В этой статье спутаны 2 понятия.

Сначала - "сильные простые числа"

А потом - "Пусть N B-гладкостепенное"

Разница есть?