Barlone,

в общем суть такая,
известны простые {p1,p2, ...}

про которые известно, что для
(x r+ a) (y r + b) = n * П ({p1,p2, ...})
есть решение

нужно выкинуть из уравнения максимальное количество pi, так что для уравнения будет существовать решение (r здесь - степень двойки)

n - не простое, и разложить его трудно
a = n mod r

r > n
kealon(Ruslan)... есть ли ненулевые целые решения у Диафантово уравнение второй степени с двумя неизвестными, вида
(x r+ a) (y r + b) = c
собственно a и = n

Barlone,

собственно исходное уравнение такое

(x r+ n) (y r + b) = n * П({Pi})

тривиальное решение при x=0, естественно не нужно

r может быть и меньше n

при r=2^k я всегда могу найти набор из (к - 1) простых чисел ({Pi}), при которых у этого уравнения будет хотя бы 1 ненулевое решение.

нет, c же зависит от набора {Pi}

Barlone,

в половине случаев это просто поиск простых удовлетворяющих
условию

Pi mod r = ([n^(fi(r1) - 1)] ^ i) mod r, i = 1..k-2

и ещё одно нужно для устранения симметрии
P0 mod r = -[n^(fi(r1) - 1)] mod r, i = 1..k-2

при выполнении этих условий 1 из множителей n по модулю r можно гарантированно составить из элементов этого набора, и уравнение будет иметь ненулевое решение

самое интересное:
к этому же уравнению можно свести задачу о рюкзаке.

была какая-то теорема, что диафантовым уравнением 2-й степени с 2-мя неизвестными можно описать любое множество чисел.
наверное можно так же и другие NP-полные задачи свести к этому уравнению.