Нахождение остатка от деления очень больших чисел - Общие вопросы C/C++

Pavel_Ine · 22.11.2009, 19:50

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

Интересно узнать идею, напрогать я и сам смогу.

LeBron · 22.11.2009, 20:03

воспользуйтесь тем, что (a*b)%x==(a%x)*(b%x).

Pavel_Ine · 22.11.2009, 20:17

Кстатииии! забыл сказать, что числа-т, от которых остаток надо находить задаются именно в виде a^b, просто надо как-то степень понизить, так как а вполне приемлемое число, просто в большой степени оно становится километровым

LeBron · 22.11.2009, 20:27

Так я и говорю. Быстрое возведение в степень с одновременным взятием по модулю. Суть моего первого поста: (66*66*66*66*66)%13==((66%13)*(66%1 3)*(66%13)*(66%13)*(66%13))%13,
так же промежуточные результаты можно брать по модулю.

pproger · 22.11.2009, 20:27

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

пс. собсна опоздал

Pavel_Ine · 22.11.2009, 20:38

Спасибо, пошел думать

Pavel_Ine · 22.11.2009, 20:49

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

22.11.2009, 19:50	#1
Pavel_Ine Пользователь Регистрация: 18.04.2009 Сообщений: 24	Нахождение остатка от деления очень больших чисел Хочу реализовать алгоритм шифрования RSA, проблема с написанием функции, которая считает остаток от деления больших чисел (например 66^77 по модулю 120). Интересно узнать идею, напрогать я и сам смогу.

22.11.2009, 20:27	#5
pproger 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

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Как узнать что число не 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

22.11.2009, 20:03	#2
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	воспользуйтесь тем, что (ab)%x==(a%x)(b%x).

22.11.2009, 20:17	#3
Pavel_Ine Пользователь Регистрация: 18.04.2009 Сообщений: 24	Кстатииии! забыл сказать, что числа-т, от которых остаток надо находить задаются именно в виде a^b, просто надо как-то степень понизить, так как а вполне приемлемое число, просто в большой степени оно становится километровым

22.11.2009, 20:38	#6
Pavel_Ine Пользователь Регистрация: 18.04.2009 Сообщений: 24	Спасибо, пошел думать

22.11.2009, 20:49	#7
Pavel_Ine Пользователь Регистрация: 18.04.2009 Сообщений: 24	С одной стороны хорошо, когда находишь (смотришь) решение, но с другой обидно, когда ваяешь часов 5 2 листа кода, который не работает..... и решается умными людьми в 4 строчки..... Еще раз большое спасибо