Re: Evaluating large polynomials over Z_p
- To: mathgroup at smc.vnet.net
- Subject: [mg27916] Re: Evaluating large polynomials over Z_p
- From: Erich Mueller <emuelle1 at uiuc.edu>
- Date: Fri, 23 Mar 2001 04:31:49 -0500 (EST)
- Organization: University of Illinois at Urbana-Champaign
- References: <99cgos$8al@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
How about something like this
modPoly[Poly_, p_] := Mod[Poly /. Power[x, b_] -> PowerMod[x, b, p], p]
This function takes a polynomial in x, and turns all of the Powers into
PowerMod's, then takes Mod of the whole thing. I didn't have the patience
to use your routine to get a big prime number, but it seems to work for
small primes.
Erich
On 22 Mar 2001, Tim Ebringer wrote:
> 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.
>
>
>
>