Пытаетесь найти бесплатную помощь в интернете, но не удается?
Вас интересует какой-то вопрос или хотите проверить свое решение?
Мы сделали универсальный сервис, где математики помогут Вам.

Найти три последние цифры в десятичной записи числа
Поступил вопрос 22 Октября 2017 по предмету "Математическая логика"
  1. Найти три последние цифры в десятичной записи числа 1234567^2017 2.Расшифровать сообщение 343343 если известно что оно зашифровано с помощью системы RSA с параметрами q=105097 p=48907 e=71
Поступил ответ 22 Октября 2017 от Викиматика

1. Три последние цифры в записи числа ${1234567}^{2017}$ есть суть остатка при делении его на $1000$. То есть задача сводится к вычислению ${1234567}^{2017}\ \left({{\rm mod} 1000\ }\right)$.

Поскольку ${\gcd  \left(1234567,\ 1000\right)\ }=1$, то по теореме Эйлера ${1234567}^{\varphi \left(1000\right)}\equiv 1\ \left({{\rm mod} 1000\ }\right)\Leftrightarrow {1234567}^{400}\equiv 1\ \left({{\rm mod} 1000\ }\right)$. Возводим обе части последнего сравнения в 5-ю степень, получаем ${1234567}^{2000}\equiv 1\ \left({{\rm mod} 1000\ }\right)$. Умножаем обе части последнего сравнения на ${1234567}^{17}$, получаем ${1234567}^{2017}\equiv {1234567}^{17}\ \left({{\rm mod} 1000\ }\right)$. Таким образом мы свели задачу вычисления к более простой ${1234567}^{17}\ \left({{\rm mod} 1000\ }\right)$. Поскольку $1234567\ \left({{\rm mod} 1000\ }\right)\equiv 567\ \left({{\rm mod} 1000\ }\right)$, то ${1234567}^{2017}\equiv {567}^{17}\ \left({{\rm mod} 100\ }0\right)$. Далее уже можно последовательно возводя в степень, вычислить ${567}^{17}\ \equiv 527\ \left({{\rm mod} 1000\ }\right)$.

Следовательно, ${1234567}^{2017}\ \equiv 527\ \left({{\rm mod} 1000\ }\right)$.

2. Так как пара простых чисел известна $p=48907,\ q=105097$, то открытый ключ будет равен $n=pq=48907\cdot 105097=5139978979$. Тогда значение функции Эйлера от $n$ будет равно $\varphi \left(n\right)=\varphi \left(pq\right)=\left(p-1\right)\left(q-1\right)=\left(48907-1\right)\left(105097-1\right)=5139824976$. Также известно число $e=71$, взаимно простое с $\varphi (n)$, то есть ${\gcd  \left(e,\ \varphi \left(n\right)\right)\ }=1$.

Для декодирования сообщения $343343$ необходимо знать мультипликативно обратный элемент к $e$ по модулю $\varphi \left(n\right)$. Пусть такой элемент равен $d$, тогда $e\cdot d\equiv 1$ $\left({\rm mod}\ \varphi \left(n\right)\right)\to 71d\equiv 1$ $\left({\rm mod}\ 5139824976\right)\to d\equiv 1013486615\ \left({\rm mod}\ 5139824976\right)$.

Декодирование сообщения $343343$ осуществляется ключом $\left(d,\ n\right)=(1013486615,\ 5139978979)$, для этого нужно вычислить ${343343}^d\ ({\rm mod}\ n)$, то есть ${343343}^{1013486615}\ \left({\rm mod}\ 5139978979\right)\equiv 2144845436\ \left({\rm mod}\ 5139978979\right)$. Итак, $2144845436$ --- декодированное сообщение.

×