MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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.




  • Prev by Date: ISOLDE for Mathematica?
  • Next by Date: Re: Mathematica can talk!
  • Previous by thread: ISOLDE for Mathematica?
  • Next by thread: Re: Evaluating large polynomials over Z_p