algorithm of fast exponentiation
Author
Hi, I am really clueless, i am begging you for help with this problem :
i wanna know if (x + a)^n is congruent to x^n + a (mod (x^r - 1), n)
where numbers a, n, r are given, x is unknown ...and n is VERY HIGH number
I know that left and right side are congruent to each other
if (x + a)^n mod (x^r - 1) = (x^n + a) mod (x^r - 1)
but:
a) I don't know what means that ,n in (mod (x^r - 1), n)
b) Beacuse n is very high, it would be good to use algorithm of fast exponentiation, but when i was searching on google, i've found only simple examples of fast exponentation...I need to use this method on given POLYNOMS and i don't know how :(
Please help...i am working on agrawal algorithm as a school project and I have to refer it next week....
P.S: I've found a link, where same problem was solved, but I didn't undestand it well: https://nrich.maths.org/discus/messages/20805/24083.html?1114255773
You are probably more familiar with writing
(x + a)n = xn + a ( mod(n) )
which means that the two sides differ by a multiple of n.
The modulus in the expression
(x + a)n = xn + a ( mod(xr -1 , n) )
means that
(x + a)n = xn + a ( mod(xr -1) )
and
(x + a)n = xn + a ( mod(n) ).
Another way of thinking about it is that, if you were write out some polynomial in x, you can simplify it by substituting xr = 1 and any coefficient by its remainder mod n.
The Agrawal et al. paper on "Primes in P" is pretty well written so you should be able to follow it. And for fast modular exponentiation you might like to take a look at the Russian Peasant Algorithm.
(x + a)n = xn + a ( mod(n) )
which means that the two sides differ by a multiple of n.
The modulus in the expression
(x + a)n = xn + a ( mod(xr -1 , n) )
means that
(x + a)n = xn + a ( mod(xr -1) )
and
(x + a)n = xn + a ( mod(n) ).
Another way of thinking about it is that, if you were write out some polynomial in x, you can simplify it by substituting xr = 1 and any coefficient by its remainder mod n.
The Agrawal et al. paper on "Primes in P" is pretty well written so you should be able to follow it. And for fast modular exponentiation you might like to take a look at the Russian Peasant Algorithm.
A reasonably fast algorithm for exponentiation is this:
If this is not fast enough, post again.
M pow(M m, integer_type n){ if(n==1) return m; if(n%2==0) return pow(m*m,n/2); if(n%3==0) return pow(m*m*m,n/3); return m*pow(m,n-1);}If this is not fast enough, post again.
Author
That's exactly, what I wanted, thank you very much sQuid. As you suggested I've used the Russian Peasant algorithm and I've modifed it to polynom exponentation...
Everythink works well, but there remains one step in agrawal algorithm, which I have no idea, how to implement...
....Have you any idea how can I find out if given N = a^b ?
Everythink works well, but there remains one step in agrawal algorithm, which I have no idea, how to implement...
....Have you any idea how can I find out if given N = a^b ?
Quote:Original post by MicRo
Please help...i am working on agrawal algorithm as a school project and I have to refer it next week....
School projects are against forum policy in general. Read the Forum FAQ for the specific rules. Original poster needs to show evidence of trying to solve the problem, and followups should not provide the answer.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
