Evaluating large polynomials over Z_p
- To: mathgroup at smc.vnet.net
- Subject: [mg27850] Evaluating large polynomials over Z_p
- From: "Tim Ebringer" <drearyslig at hotmail.com>
- Date: Thu, 22 Mar 2001 04:29:55 -0500 (EST)
- Organization: Computer Science, University of Melbourne
- Sender: owner-wri-mathgroup at wolfram.com
Hi there,
Since I received such magnificent help last time I posted here, I hoped I
could squeeze your collective brains again. I wonder if there is a way to
evaluate a large polymonial over the integers modulo a large prime p without
extracting every single term and running PowerMod,
e.g. Get a 1000 bit prime:
p=Random[Integer,{2^999,2^1000}];While[\[Not]PrimeQ[p],
p=Random[Integer,{2^999,2^1000}]];
coeff=Random[Integer,{1,p-1}];
exponent=Random[Integer,{1,p-1}];
bigpoly=coeff x^exponent;
ok, so we should now have a big polynomail. Suppose we want to evaluate this
at x=5 (mod p), we would like to write
Mod[bigpoly /. x->5]
but this overflows. What we really want is Mathematica to
Mod[PowerMod[5,exponent,p]*coeff,p] for each term in the polynomial, and sum
them up (mod p, of course). Is there an elegant way to get Mathematica to do
this, or must I iterate over the polynomial and individually extract each
term?
Cheers,
Tim.