Sign in to follow this  
MicRo

algorithm of fast exponentiation

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
A reasonably fast algorithm for exponentiation is this:
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.

Share this post


Link to post
Share on other sites
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 ?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.
Sign in to follow this