Архив задач олимпиады по математике и криптографии

Вскрытие RSA

Известно, что число 14197777 равно остатку от деления на 56887111  некоторого числа x, возведённого в куб. Числа x и 56887111 имеют общий делитель, отличный от 1, а число 56887111 является произведением двух простых чисел. Найдите хотя бы одно такое число x.

  • Решение

    • Решение

    Пусть y=14197777, N=p·q =56887111, p,q  – простые числа. По условию НОД(x,N)=p>1 , то есть x=t·p, где t – натуральное число.

    Так как y=rN(x3)   -  остаток от деления на N  числа   x3, то НОД(y,N)=p. Вычисляя НОД(14197777, 56887111), находим, что p=10667, тогда y=1331·p, а q=N/p=5333. Делим обе части уравнения 

    1331·p= rN((t·p)3)        

    на p, получаем:

    1331= rN( t3· p2) =  r5333( t3· 106672) = r5333( t3).

    Поэтому t = ³√1331 = 11 и x = t·p = 11·10667 = 117337.

  • Ответ

    • Ответ

     x = 117337