возведение в степень и взятие по модулю

[Kukurudza]

мне нужно возвести очень длинное число (порядка 1000 знаков в десятичной системе) в очень большую степень (так же порядка 1000 знаков в десятичной системе) и взять от этого числа модуль. ну проще говоря
a^b % d
само собой a^b считать не реально, это и очень долго и очень длинное число получится (порядка 1 000 000 знаков)
может есть какое то свойство этой операции чтобы обойтись без a^b ??

[haruhi]

никаких свойств нет. единственный способ - реализоваться длинную арифметику. проще говоря считать вручную в столбик

[alexey_kip]

Можно написать программу для работы со сверхдлинными числами, например с 65536-ричной системой счисления. Можно ужасно большие числа в ужасно большие степени возводить))

[Kukurudza]

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

[evg_m]

информация к размышлению, для тек кто забыл.
(ax +b) *(cx+d) =acxx +adx +bcx +bd =(acx + ad + bc)*x +bd

(ax+b)*(cx+d) % x =?

[Serge_Bliznykov]

(ax+b)*(cx+d) % x =?

ход мыслей понравился! +1

а можно для тех, кто подзабыл математику (я себя имею в виду)
продолжить вывод для :
((ax+b)*(ax+b)*(ax+b) .... * (ax+b) ) % x = ???

если (ax+b) перемножаются N раз,
то это будет b^N % x

otvet = b % x;
for (i=1;i<N;i++)
  otvet = (otvet * b ) % x;

так?!

[SAMOUCHKA]

а тебе что, результат с абсолютной точностью нужен? в таких больших числах, в прочем как и любых абсолютная точность ни к чему. да такавой просто и не бывает.
к примеру гиря 1кг - точнее
1.0 - точнее
1.00 - точнее
1.000- так этому конца не будет. можно писать числа со сколь угодно большим колличеством знаков, как до запятой так и после. на деле окажется что такие длинные числа лиш математическая выкладка и не более, в реальном мире смысла не имеют. и для чего такие задачи? я так-бы преподу и сказал
а число которое ты указал это даже больше числа атомов во вселенной

[Serge_Bliznykov]

SAMOUCHKA, чепуху Вы говорить изволите! Это раз.

Говорить преподу, что задание глупое, потому что таких чисел в природе не бывает - бессмысленно и бесполезно. Это два.

третье.

а число которое ты указал это даже больше числа атомов во вселенной

Напомните, мне, пожалуйста, сколько у нас атомов во вселенной?..

и чётвёртое (последнее). А каким образом данная задача связана с числом атомов во вселенной?! Что, если числа большие, так можно и не напрягаться, так?!

[Kukurudza]

Ну это для алгоритма RSA. криптография. Да, препод всегда прав, если препод не прав, смотри пункт один у меня числа целые. без запятых

[veniside]

имхо, проще взять готовое и не парить мозг

http://www.submanifold.be/triade/GInt/gint.html