Остаток от деления, двойная степень

[Ascar]

задача, нахождение остатка от деления у двухэтажной степени

${{X}^7}^7 \mod K \equiv m$

1 вариант
вычислить значение

${7}^7 =823543$

и вычислять
${X}^{823543} \mod K \equiv m$

2 вариант

${X}^7 \mod K \equiv m_1$
${m_1}^7 \mod K \equiv m_2$
${m_2}^7 \mod K \equiv m_3$
${m_3}^7 \mod K \equiv m_4$
${m_4}^7 \mod K \equiv m_5$
${m_5}^7 \mod K \equiv m_6$
${m_6}^7 \mod K \equiv m$

При увеличении степени, первый вариант - слишком большое число для работы получается
Второй вариант требует 7 итераций и при возрастании верхней степени соответсвенно дольше работают.
Нет ли более быстрого способа для вычисления остатка при двухэтажной степени.

[whitefox]

Если $X$ и $K$ взаимно просты, то $X^{7^7}\equiv X^{7^7\bmod\lambda(K)}\pmod K,$ где $\lambda(K)$ это функция Кармайкла.

[Sonic86]

Зависит от величины $m$ и его разложения на множители.
Если множители достаточно малы, то юзаем функцию Кармайкла (или малую теорему Ферма с китайской теореомй об остатках).
Если множители велики - юзаем двоичное возведение в степень.
Определять точку пересечения будет муторно.

[iifat]

На всякий случай повторю вышесказанное простыми словами: последовательность $a_n=m^n\pmod k$ (с фиксированными константами $m$, $k$) — периодическая. Теорию можно поискать по ключевым словам малая теорема Ферма, функция Эйлера, функция Кармайкла. Это позволяет перейти от задачи выяснения остатка степени к выяснению остатка от деления показателя степени на длину периода.

[Ascar]

спасибо всем... пошол читать теорию

[VAL]

Ascar в сообщении #1131142 писал(а):

спасибо всем... пошол читать теорию

(Оффтоп)

И учебник по русскому языку обязательно почитайте.