Gennadiy Usov,

всё довольно просто
посмотри как перемножаются числа вида vp+1 в кольце p^2

[(v1 p+1) * (v2 p+1)]|p^2 = [v1* v2 p^2+(v1 + v2) p +1]|p^2 = [(v1 + v2) p +1]|p^2

находим n' : n*n' - v1 * p = 1

берём члены нашего кольца g(1) и g(-1)
находим v2 : g(1) * g(-1) = v2 p + 1

исходя из правила умножения получаем:

x = [[v2 ^-1 ]| _p * v1] | _p + i*p


все делители n будут лежать в множестве [g(1) ^ x] | _p^2

для отсечки лишних нужно выполнение условия [g(1) ^ x] < n и [g(-1) ^ x] < n

т.е. если мы имеем такой p для которого можно вывести "итератор" по числам <p в кольце p^2, то мы можем разложить на множители любое число n < p

Gennadiy Usov,

находим n' и v1 с помощью расширенного алгоритма Евклида , n' обычно обозначают n ^-1 |p, он равен n^(fi(p)-1)|p = n^(p-2)|p если p простое

x находим из полученного ранее соотношения [(vp+1)^x]| _p^2 = [vx p +1] | _p^2
подменив
v*x -> (n'*n - 1)/p
v -> (G(1)*G(-1) - 1)/p
собственно опять же с помощью расширенного алгоритма Евклида

1. ничего
2. в общем-то не будут
алгоритм даёт a,b,d: an + bp = d
где d будет =1, так как n и b взаимнопростые - это НОД(n,p)
и либо a, либо b будет меньше нуля, но об этом обычно не пишут, так как довольно очевидно, что знак можно поменять, добавив np или -np
[an + np] + [bp - np] = d

приводишь результаты к виду
n*n' - v1 * p = 1
и всё

верно: 14 * 61 = 856 = 855 + 1 = 19*45 + 1

g должен быть от p, а не от p^2, т.е. 31: 2 * 31 = 1 * 61 + 1
для теста пока пойдёт и он
"итератора" то, про который я говорил - 22052583 , у нас пока так и нет

соответственно x=14 + i*p

Gennadiy Usov,

ну так у нас и итератора аналитического нет.
Что проще? умножать постоянно непонятно сколько или вычислить несколько вариантов пусть даже в очень большой степени?

т.е. если бы мы, например, знали что все числа <p пробегаются с помощью формулы g ^k*a | _{p2 решение системы было бы тривиально}

а там есть пары с обоими значениями меньше 61?
нет ????, значит наш заход неверен

начальная постановка моего вопроса была: "как пробежать по всем числам меньше p в кольце p^2?"
ты спросил "зачем?"
я привёл это выражение, которое дополняет систему

а по поводу того, что числа > p, так это произведение двух чисел
мы же пытаемся получить n'*n через произведение двух чисел - если итератор пробегаетcя по всем числам, то он обязательно одним из чисел зацепит делитель либо n либо n'

Gennadiy Usov,

так у тебя есть итератор? так что вполне ожидаемый результат

Gennadiy Usov,

эта формула даёт n'*n,
даёт?
даёт ...
а то что подаёшь на входе фигню, и получаешь фигню - вполне закономерно