Как найти все X

[gofkane]

f(x) mod g(x) = 0

Как найти все корни уравнения быстрее чем за O(x)? f и g - линейные функции.

[Abstraction]

Кто такой n? Решений уравнения, скажем, x mod x = 0 - бесконечно много, с такими случаями как?

[p51x]

на РСА решили напасть?

[Abstraction]

А с каких пор в RSA линейные функции? Там как бы экспонента...

[gofkane]

Ну давайте конкретный пример для которого всё и делается:

n = const

1) (n - x - 2) mod (2 * x - 2) = 0
2) (n + x) mod (2 * x + 2) = 0

Если пробегать по всем x то не укладывается по времени. Пробовал после первого найденного подбором увеличивать так: x= g(x+1); - теряет много корней.

[Abstraction]

1) m=(n-3), y=(x-1), имеем m = (2z+1)y при произвольном целом z;
2) m=(n-1), y=(x+1), имеем m = (2z+1)y при произвольном целом z.
Осталось в каждом случае разложить m на множители...

[gofkane]

Сообщение от Abstraction

1) m=(n-3), y=(x-1), имеем m = (2z+1)y при произвольном целом z;
2) m=(n-1), y=(x+1), имеем m = (2z+1)y при произвольном целом z.
Осталось в каждом случае разложить m на множители...

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

[Abstraction]

(n - x - 2) mod (2 * x - 2) = 0
n-x-2 = z*(2x-2)
n-3=2z*(x-1)+(x-1)
n-3=(2z+1)(x-1)
Берём n-3, выделяем из него степень 2, оставшееся раскладываем на множители. Каждое подмножество множества его нечётных множителей соответствует некоторому целому z, остальное - некоторому целому x. Отдельно стоит отметить чётность решений: если y - решение, то -y - тоже решение.