x, y, z

Как вычислять степень по модулю?

# 13 Апр 2015 11:10:14
Андрей
По какому алгоритму можно вычислить (105^467) mod 527?
# 15 Апр 2015 02:37:38
Enko
Программно $a^n\mod m$ можно вычислять так:

x=1;
for(int i=0; i<n; i++)
{
x = x*a;
if( x >= m ) x = x % m;
}


См. алгоритмы возведения в степень.

Можно попытаться упростить выражение.

$105 = 3\cdot 5\cdot 7$, $527 = 17\cdot 31$ - разложение на простые множители.

$105$ взаимно просто с $527$, поэтому $105$ обратимый элемент кольца ${\Bbb Z}_{527}$.

По теореме Эйлера, если $\text{НОД}(a,m)=1$, то $a^{\varphi(m)}\equiv 1 \mod m$.

$\varphi(527)=(17-1)(31-1)=480$, поэтому $105^{480} \equiv 1\mod 527$, откуда следует $105^{467} \equiv 105^{-13}\mod 527$. Но вычисление это упрощение не облегчает, а даже наоборот.
*Имя:
Заголовок:
[tex-clear] [tex-help] [ted]
  • formulas >

*Вычислите
Captcha
Отправляя данные, вы соглашаетесь с Правилами сайта.