to Navi1982
Насчет возведения числа в большую степень могу подсказать на мой взгляд вполне отличный метод. Сложность заключается в том, что при вычислениях реальных 512 и/или 1024, и/или N - значных чисел не возможно пользоваться встроенными арифметическими операциями языков программирования!
У меня была недавно лаба, связанная с шифрованием методом RSA. Так вот длина ключа(для шифрования/расшифрования) должна должна вычисляться с помощью квадратов чисел большой разрядности.
На первый взгляд может показаться, что это очень сложно, но это, ИМХО, наиболее быстро, удобно и надежно.
^ - этим знаком я буду обозначать возведение в степень!
В качестве примера: (432^678) mod 987.
Первым делом надо найти степени числа 432:
Код:
(432^2) mod 987 = (432^2) mod 987 = 81
(432^4) mod 987 = (81^2) mod 987 = 639
(432^8) mod 987 = (639^2) mod 987 = 690
(432^16) mod 987 = (690^2) mod 987 = 366
(432^32) mod 987 = (366^2) mod 987 = 711
(432^64) mod 987 = (711^2) mod 987 = 177
(432^128) mod 987 = (177^2) mod 987 = 732
(432^256) mod 987 = (732^2) mod 987 = 870
(432^512) mod 987 = (870^2) mod 987 = 858
Число 678 можно представить как
, то
Код:
(432^678) mod 987 = (432^512 ∙ 432^128 ∙ 432^32 ∙ 432^4 ∙ 432^2) mod 987 =
(81∙639∙711∙732∙858) mod 987 = 204
В лабе по шифрованию RSA я РЕАЛЬНО использовал ключи, длиной не менее 2048 символов (такова была задача), и после реализации задачи таким методом, все работало на ура, но приходилось пользоваться методами против "залипания" клавиш во время работы программы!