|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.11.2009, 19:50 | #1 |
Пользователь
Регистрация: 18.04.2009
Сообщений: 24
|
Нахождение остатка от деления очень больших чисел
Хочу реализовать алгоритм шифрования RSA, проблема с написанием функции, которая считает остаток от деления больших чисел (например 66^77 по модулю 120).
Интересно узнать идею, напрогать я и сам смогу. |
22.11.2009, 20:03 | #2 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
воспользуйтесь тем, что (a*b)%x==(a%x)*(b%x).
|
22.11.2009, 20:17 | #3 |
Пользователь
Регистрация: 18.04.2009
Сообщений: 24
|
Кстатииии! забыл сказать, что числа-т, от которых остаток надо находить задаются именно в виде a^b, просто надо как-то степень понизить, так как а вполне приемлемое число, просто в большой степени оно становится километровым
|
22.11.2009, 20:27 | #4 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Так я и говорю. Быстрое возведение в степень с одновременным взятием по модулю. Суть моего первого поста: (66*66*66*66*66)%13==((66%13)*(66%1 3)*(66%13)*(66%13)*(66%13))%13,
так же промежуточные результаты можно брать по модулю. |
22.11.2009, 20:27 | #5 |
C++ hater
СтарожилДжуниор
Регистрация: 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 |
22.11.2009, 20:38 | #6 |
Пользователь
Регистрация: 18.04.2009
Сообщений: 24
|
Спасибо, пошел думать
|
22.11.2009, 20:49 | #7 |
Пользователь
Регистрация: 18.04.2009
Сообщений: 24
|
С одной стороны хорошо, когда находишь (смотришь) решение, но с другой обидно, когда ваяешь часов 5 2 листа кода, который не работает..... и решается умными людьми в 4 строчки..... Еще раз большое спасибо
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как узнать что число не 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 |