Re: Evaluating large polynomials over Z_p
- To: mathgroup at smc.vnet.net
- Subject: [mg27909] Re: [mg27850] Evaluating large polynomials over Z_p
- From: Andrzej Kozlowski <andrzej at platon.c.u-tokyo.ac.jp>
- Date: Fri, 23 Mar 2001 04:31:36 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
I think this ought to be done by the function PolynomialReduce, but
unfortunately it fails as soon as the degree of polynomial starts getting
fairly large, as do some other Mathematica functions. This is what happens
for small exponents (using your code):
In[1]:=
Clear[p,bigpoly,coeff,exponent]
In[2]:=
p=Random[Integer,{2^9,2^10}];While[¬PrimeQ[p],
p=Random[Integer,{2^9,2^10}]];
In[3]:=
coeff=Random[Integer,{1,p-1}];
exponent=Random[Integer,{1,p-1}];
In[5]:=
bigpoly=coeff x^exponent;
In[6]:=
Last[PolynomialReduce[bigpoly,x-5,Modulus->p]]
Out[6]=
512
So far so good, but if we increase the exponent this is what we get:
In[8]:=
p=Random[Integer,{2^99,2^100}];While[¬PrimeQ[p],
p=Random[Integer,{2^99,2^100}]];
In[9]:=
coeff=Random[Integer,{1,p-1}];
exponent=Random[Integer,{1,p-1}];
In[11]:=
bigpoly=coeff x^exponent;
In[13]:=
Last[PolynomialReduce[bigpoly, x - 5, Modulus -> p]]
PolynomialReduce::poly2:
417577929809586904637242164284
177873420024357863081162204185 x
is not a well-formed polynomial in {x}.
Modulus -> 1005854439688729486368423855587
You can also check that other functions also do not work, e.g.:
In[14]:=
CoefficientList[bigpoly,x]
CoefficientList::lrgexp: Exponent is out of bounds for function
CoefficientList.
CoefficientList[177873420024357863081162204185*x^417577929809586904637242164
284, x]
Fortunately it is not hard to write a program that does work at least for
your original example (more or less in the way you yourself suggested):
In[15]:=
eval[bigpoly_,{x_,n_,p_}]:=Mod[Map[PowerMod[n,#,p]&,Exponent[bigpoly,x,List]
].Mod[If[Head[#]===Plus,List@@#,{#}]&@bigpoly/.x->1,p],p]
Now let's try your original example:
In[16]:=
p=Random[Integer,{2^999,2^1000}];While[¬PrimeQ[p],
p=Random[Integer,{2^999,2^1000}]];
In[17]:=
coeff=Random[Integer,{1,p-1}];
exponent=Random[Integer,{1,p-1}];
In[19]:=
bigpoly=coeff x^exponent;
In[20]:=
eval[bigpoly,{x,5,p}]
4569640098844404886880611326088131662447418418173107326499736996478266475652
26011521853\
8571832254776782054677506252761408921677915269811842525045569339854674714660
54850282289\
5155420560034054097303670852790389524265386454102927009998547998552848505132
58104575351\
9467140854379956999717314047537215638311
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
on 3/22/01 10:29 AM, Tim Ebringer at drearyslig at hotmail.com 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.
>
>
>
>