MicRo 130 Report post Posted March 12, 2006 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 0 Share this post Link to post Share on other sites

sQuid 149 Report post Posted March 12, 2006 You are probably more familiar with writing (x + a)^{n} = x^{n} + a ( mod(n) )which means that the two sides differ by a multiple of n. The modulus in the expression (x + a)^{n} = x^{n} + a ( mod(x^{r} -1 , n) )means that (x + a)^{n} = x^{n} + a ( mod(x^{r} -1) )and (x + a)^{n} = x^{n} + 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 x^{r} = 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. 0 Share this post Link to post Share on other sites

alvaro 21276 Report post Posted March 13, 2006 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. 0 Share this post Link to post Share on other sites

MicRo 130 Report post Posted March 14, 2006 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 ? 0 Share this post Link to post Share on other sites

grhodes_at_work 1385 Report post Posted March 15, 2006 Quote:Original post by MicRoPlease 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. 0 Share this post Link to post Share on other sites