2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Остаток от деления, двойная степень
Сообщение12.06.2016, 17:52 


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

${{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 итераций и при возрастании верхней степени соответсвенно дольше работают.
Нет ли более быстрого способа для вычисления остатка при двухэтажной степени.

 Профиль  
                  
 
 Re: Остаток от деления, двойная степень
Сообщение12.06.2016, 20:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Остаток от деления, двойная степень
Сообщение12.06.2016, 21:28 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Остаток от деления, двойная степень
Сообщение13.06.2016, 03:09 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Остаток от деления, двойная степень
Сообщение13.06.2016, 03:12 


27/11/08
111
спасибо всем... пошол читать теорию

 Профиль  
                  
 
 Re: Остаток от деления, двойная степень
Сообщение13.06.2016, 07:43 
Заслуженный участник


27/06/08
4058
Волгоград
Ascar в сообщении #1131142 писал(а):
спасибо всем... пошол читать теорию

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group