MicRo

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/messa...tml?1114255773

grumpy

This is a mathematics problem, not a computer science problem. And you're barking up the wrong tree in looking for an algorithm to do fast exponentiation. A computer can only search for examples where the congruence relationship is true (confirming the statement) or not true (one counter example disproves the identity, obviously).

You will probably find discussion of the problem easier to follow if you understand that mod(x,y) is the remainder that is left over when dividing x by y. For example, the remainder of dividing 5 by 3 is 2, so mod(5,3) = 2.

The statement "a congruent to b (modulo c)" [shorthand for "congruent to" is an equals sign with 3 bars] simply means that mod(c,a) = mod(c,b) i.e. when dividing a and b by c, both have the same remainder.

Another way of expressing the same thing is that "a congruent to b (modulo c)" means that a = b + k*c where k is some integer.