Совпадение элементов двух последовательностей

[denfedorov]

Имеется соотношение
Дано $ P_1$ , $ P_2$ - простые числа
$ a $ , $b$ - целые неотрицательные числа
$ 0<a<b $
$ X = (Y^a) \mod P_1 $
$ X = ((Y^a )( Y^b)) \mod P_2 $
$ X<P_1<P_2 $

"Равно " в формулах - это именно равно, а не "сравнимо по модулю"
как найти пару X,Y удовлетворяющую формулам, исключая способ перебора всех вариантов

Я пытался разобраться, но так как $ P_1$ и $ P_2$ - взаимно простые числа - то операции сложения и вычитания и умножения по модулю невозможны. Я пытался привести систему к общему модулю $P_1P_2$ - но не увидел намека на решение.В идеале хотелось бы получить зависимость $Y$ от $X$

[zhoraster]

Тема перемещена в Карантин.

Поправьте формулы и сообщите об этом в теме Сообщение в карантине исправлено.

[AKM]

Возвращено.

[Sonic86]

$Y<p_1p_2$
В общем случае зависимость $Y$ от $X$ не будет функциональной, поскольку, если $(X,Y)$ удовлетворяет системе, то и $(X,Yz)$ удовлетворяет системе, где $z: z \equiv g_j^{\frac{p_j-1}{d_j}k_j} \pmod p_j$ $g_j$ - образующие по модулям $p_j$, $d_1 = \gcd (a, p_1-1), d_2 = \gcd (a+b, p_2-1)$, $k_j$ - натуральные.

Можно систему переписать так:
$\left\{ \begin{array}{ll} y^a-x = p_1q_1, q_1 < \frac{y^a}{p_1}\\ y^{a+b}-x = p_2q_2, , q_2 < \frac{y^{a+b}}{p_2} \end{array} $
Выражая $x$ из 1-го и подставляя во 2-е, получим уравнение $y^{a+b}-y^a = p_2q_2-p_1q_1$. Подставляя произвольное $y$ можно получить довольно много решений при произвольных $a,b$ с помощью алгоритма Евклида.

Задание не очень естественно выглядит. Откуда такое взялось?

[denfedorov]

Sonic86 в сообщении #445178 писал(а):

Задание не очень естественно выглядит. Откуда такое взялось?

Решал проблему, компьютерного толка, хотел сократить скорость работы программы, а это задание возникло в ходе проверки одной гипотезы оптимизации вычислений