Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 22.11.2009, 19:50   #1
Pavel_Ine
Пользователь
 
Аватар для Pavel_Ine
 
Регистрация: 18.04.2009
Сообщений: 24
По умолчанию Нахождение остатка от деления очень больших чисел

Хочу реализовать алгоритм шифрования RSA, проблема с написанием функции, которая считает остаток от деления больших чисел (например 66^77 по модулю 120).

Интересно узнать идею, напрогать я и сам смогу.
Pavel_Ine вне форума Ответить с цитированием
Старый 22.11.2009, 20:03   #2
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

воспользуйтесь тем, что (a*b)%x==(a%x)*(b%x).
LeBron вне форума Ответить с цитированием
Старый 22.11.2009, 20:17   #3
Pavel_Ine
Пользователь
 
Аватар для Pavel_Ine
 
Регистрация: 18.04.2009
Сообщений: 24
По умолчанию

Кстатииии! забыл сказать, что числа-т, от которых остаток надо находить задаются именно в виде a^b, просто надо как-то степень понизить, так как а вполне приемлемое число, просто в большой степени оно становится километровым
Pavel_Ine вне форума Ответить с цитированием
Старый 22.11.2009, 20:27   #4
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Так я и говорю. Быстрое возведение в степень с одновременным взятием по модулю. Суть моего первого поста: (66*66*66*66*66)%13==((66%13)*(66%1 3)*(66%13)*(66%13)*(66%13))%13,
так же промежуточные результаты можно брать по модулю.
LeBron вне форума Ответить с цитированием
Старый 22.11.2009, 20:27   #5
pproger
C++ hater
СтарожилДжуниор
 
Аватар для pproger
 
Регистрация: 19.07.2009
Сообщений: 3,333
По умолчанию

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

пс. собсна опоздал
I invented the term Object-Oriented, and I can tell you I did not have C++ in mind. (c)Alan Kay

My other car is cdr.

Q: Whats the object-oriented way to become wealthy?
A: Inheritance
pproger вне форума Ответить с цитированием
Старый 22.11.2009, 20:38   #6
Pavel_Ine
Пользователь
 
Аватар для Pavel_Ine
 
Регистрация: 18.04.2009
Сообщений: 24
По умолчанию

Спасибо, пошел думать
Pavel_Ine вне форума Ответить с цитированием
Старый 22.11.2009, 20:49   #7
Pavel_Ine
Пользователь
 
Аватар для Pavel_Ine
 
Регистрация: 18.04.2009
Сообщений: 24
По умолчанию

С одной стороны хорошо, когда находишь (смотришь) решение, но с другой обидно, когда ваяешь часов 5 2 листа кода, который не работает..... и решается умными людьми в 4 строчки..... Еще раз большое спасибо
Pavel_Ine вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как узнать что число не Float(без остатка) при результате деления? zotox Помощь студентам 7 19.07.2009 15:49
алгоритм сравнения больших чисел со сдвигом WOLFak Паскаль, Turbo Pascal, PascalABC.NET 0 29.12.2008 22:36
Составить программу, определяющую количество чисел, делящихся без остатка на три phoenixSV Паскаль, Turbo Pascal, PascalABC.NET 2 05.12.2008 15:05
Библиотека больших чисел на Delphi Victor1987 Помощь студентам 10 11.04.2008 08:25