Re: PowerMod[] - Mathematica 5.0 - problem/error/bug?
- To: mathgroup at smc.vnet.net
- Subject: [mg73041] Re: PowerMod[] - Mathematica 5.0 - problem/error/bug?
- From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
- Date: Tue, 30 Jan 2007 23:36:34 -0500 (EST)
- Organization: The Open University, Milton Keynes, UK
- References: <epn9t2$chv$1@smc.vnet.net>
Anton Vrba wrote:
> In Mathematica 5.0 I found on my system the following incorrect result regarding the PowerMod[] function
>
> You agree that PowerMod[2,17 p, p]=2^17 for p prime and p>2^17
>
> Mathematica 5.0 calculates PowerMod[2,17 p, p] as 2^2
> for p=126322571 through to p=2147483647. (one can change the 2 to any base and the wrong answer base^2 is calculated)
>
> below the notebook file converted to text format.
>
> Have I a problem in my system? or is this a Mathematica 5.0 bug or possibly a new Pentium bug?
>
> best regards
> Anton
>
> In[60]:=
> p=Prime[123456780]
> y=PowerMod[2,17 p,p]
> FactorInteger[y]
> "y is the correct result"
>
> p=Prime[103456780]
> y=PowerMod[2,17 p,p]
> FactorInteger[y]
> "y should equal 2^17 and not 2^2"
>
> m=5
> y=PowerMod[2,(2^(32 m)-1) p,p]
> FactorInteger[y]
> m=12
> y=PowerMod[2,(2^(32 m)-1) p,p]
> FactorInteger[y]
> "y equal 2^(m+1) is a cute result"
>
> Out[60]=2543568329
> Out[61]=131072
> Out[62]={{2,17}}
> Out[63]=y is the correct result
> Out[64]=2112226087
> Out[65]=4
> Out[66]={{2,2}}
> Out[67]=y should equal 2^17 and not 2^2
> Out[68]=5
> Out[69]=64
> Out[70]={{2,6}}
> Out[71]=12
> Out[72]=8192
> Out[73]={{2,13}}
> Out[74]=y equal 2^(m+1) is a cute result
>
> In[75]:=
> "here is the range of the error"
> p=Prime[7181138]
> FactorInteger[PowerMod[2,17 p,p]]
> p=Prime[7181138+1]
> FactorInteger[PowerMod[2,17 p,p]]
> p=Prime[105097565]
> FactorInteger[PowerMod[2,17 p,p]]
> p=Prime[105097565+1]
> FactorInteger[PowerMod[2,17 p,p]]
> Out[75]=here is the range of the error
> Out[76]=126322543
> Out[77]={{2,17}}
> Out[78]=126322571
> Out[79]={{2,2}}
> Out[80]=2147483647
> Out[81]={{2,2}}
> Out[82]=2147483659
> Out[83]={{2,17}}
Here is what I got on my system:
In[1]:=
$Version
Out[1]=
5.2 for Microsoft Windows (June 20, 2005)
In[2]:=
p=Prime[123456780]
y=PowerMod[2,17 p,p]
FactorInteger[y]
"y is the correct result"
p=Prime[103456780]
y=PowerMod[2,17 p,p]
FactorInteger[y]
"y should equal 2^17 and not 2^2"
m=5
y=PowerMod[2,(2^(32 m)-1) p,p]
FactorInteger[y]
m=12
y=PowerMod[2,(2^(32 m)-1) p,p]
FactorInteger[y]
"y equal 2^(m+1) is a cute result"
Out[2]=
2543568329
Out[3]=
131072
Out[4]=
{{2,17}}
Out[5]=
y is the correct result
Out[6]=
2112226087
Out[7]=
131072
Out[8]=
{{2,17}}
Out[9]=
y should equal 2^17 and not 2^2
Out[10]=
5
Out[11]=
749529127
Out[12]=
{{53,1},{14142059,1}}
Out[13]=
12
Out[14]=
33793814
Out[15]=
{{2,1},{16896907,1}}
Out[16]=
y equal 2^(m+1) is a cute result
In[17]:=
"here is the range of the error"
p=Prime[7181138]
FactorInteger[PowerMod[2,17 p,p]]
p=Prime[7181138+1]
FactorInteger[PowerMod[2,17 p,p]]
p=Prime[105097565]
FactorInteger[PowerMod[2,17 p,p]]
p=Prime[105097565+1]
FactorInteger[PowerMod[2,17 p,p]]
Out[17]=
here is the range of the error
Out[18]=
126322543
Out[19]=
{{2,17}}
Out[20]=
126322571
Out[21]=
{{2,17}}
Out[22]=
2147483647
Out[23]=
{{2,17}}
Out[24]=
2147483659
Out[25]=
{{2,17}}
Regards,
Jean-Marc