Repeated squaring of polinomial mod r

[bbone]

Hi all!

Can somebody please give me any ideas on how to write a function that will compute p(x)^n mod(x^r - 1, n), where n is a large number by using repeated squaring algorithm?

 

[bbone]

I forgot to mention, that I need this only for this kind of polinomials: p(x) = x - a. So I have to compute
(x - a)^n mod (x^r - 1). r < n

 

[Cagliostro]

in would be something like this:

int yourFunc(int x, int a, int n, int r)
{
if(r < n)
((int)pow((x - a), n)) % ((int)pow(x, r) - 1);
}

Ion Filipski

ICQ: 95034075
AIM: IonFilipski
filipski@excite.com

 

[Salem]

> how to write a function that will compute p(x)^n mod(x^r - 1, n)
I'm guessing that this is for cryptography or something.

If this is so, you will need complete accuracy. The standard integer types do not have the range, and the floating point types are not accurate.

For accuracy with very large numbers, you need a 'BIGNUM' library. Here is one -

http://www.swox.com/gmp/

--

http://www.catb.org/~esr/faqs/smart-questions.html