RE: Together chokes with Prime Modulus > 46337
- To: mathgroup at smc.vnet.net
- Subject: [mg15182] RE: [mg15155] Together chokes with Prime Modulus > 46337
- From: "Ersek, Ted R" <ErsekTR at navair.navy.mil>
- Date: Fri, 18 Dec 1998 02:10:59 -0500
- Sender: owner-wri-mathgroup at wolfram.com
The limitation of Together (Modulus->p) also effects ProvablePrimeQ.
See below.
In[1]:=
<<NumberTheory`PrimeQ`
In[2]:=
ProvablePrimeQ[25217504003]
Together::"modm": "Modulus \!\(25217504003\) is too large for this
implementation."
Together::"modm": "Modulus \!\(25217504003\) is too large for this
implementation."
Together::"modm": "Modulus \!\(25217504003\) is too large for this
implementation."
General::"stop": "Further output of \!\(Together :: \"modm\"\) will be
suppressed during this calculation."
Out[2]=
$Aborted
After several minutes I got tired of waiting and aborted.
Cheers,
Ted Ersek
>
>One of the great things about Mathematica is that you can do exact
>calculations with very large numbers. For example:
>
>In[1]:=
>3^123-7^69
>Out[1]=
>28018763581994152068926844488\
>663468681310215695058256067220
>
>In the next line Together works in modulo 46337 and I get the answer in
>a flash!
>(note 46337 is a prime number)
>
>In[2]:=
>Together[1/x+1/(x+1), Modulus->46337] Out[2] (2*(23169 + x))/(x*(1 + x))
>
>Next try using Together with any prime modulus larger than 46337 and
>Mathematica will choke.
>
>I would have guessed the functions that use the Modulus option could
>work in modulo prime where the prime modulus has a hundred digits or
>more with no problem. Instead Mathematica flat-out quits for modulo
>greater than 46337.
>
>Is it impractical to make a version that will do modular algebra with a
>large modulus?
>
>I can evaluate NextPrime[10^10000] and I doubt Mathematica will refuse
>to try it. I might have to wait over a year for an answer. I might
>run out of memory before I get an answer, but I expect Mathematica will
>not give up. Using Modulus 46337 Together hasn't even got to the point
>where it takes a little while, but it will refuse to work with a
>modulus any larger. Why?
>
>
>Cheers,
>Ted Ersek
>
I think this is a very interesting question and I hope some expert will
send a illuminating reply. I just wanted to add a few observations to
the above message.
The limitation in modular arithemtic to the prime 46337 affects besides
Together, the functions PolynomialGCD, PolynomialLCM, Factor and Solve,
and perhaps other functions which I have not investigated. Functions
like Expand, Apart do not seem to have any limitation. When applied
modulo a prime larger than 46337, Together, PolynomialGCD,
PolynomialLCM, and Factor give up at once and produce the same message:
In[1]:=
Factor[x^2+x,Modulus->46349]
Factor::modm:
Modulus 46349 is too large for this implementation. Out[1]=
2
Factor[x + x , Modulus -> 46349]
Solve behaves slightly diffferently. It works in the most trivial cases:
In[2]:=
Solve[{x-1==0, Modulus==46349},Mode->Modular]
Out[2]=
{{Modulus -> 46349, x -> 1}}
but not in slightly harder ones:
In[3]:=
Solve[{x^2-1==0, Modulus==46349},Mode->Modular] Roots::badmod: Cannot
factor input modulo 46349. Roots::badmod: Cannot factor input modulo
46349. Out[3]=
{ToRules[Modulus == 46349 &&
2
Roots[x == 1, x, Modulus -> 46349]]}
This suggests to me that the problem is related to factoring of
polynomials mod p. If I recall correctly (and my knowledge of this area
may be obsolete by about 10 years), there is no deterministic
polynomial time algorithm for factoring polynomials mod p. The usual
practice is to use probabilistic algorithms, which have a slight chance
of not stopping at all. There is, however, a fast way of factoring mod
p, but it requires one to assume the truth of the Generalized Riemann
Hypothesis. Unfortunately the Mathematica Book seems to give no
information on the implementation of mod p algorithms. I do hope
someone famililiar with these matters will respond to Ted's message.
This leads me to an interesting question. As is well known, Gregory
Chaitin ("The Limits of Mathematics" and other places) has been
advocating accepting the Riemann Hypothesis as a kind of "experimental
axiom", rather like what physicists do with their theories. While I
don't think this will ever be accepted in pure mathemtics, (where
people prefer to talk of results being true "modulo" the Riemann
hypthesis), Mathematica is already doing soemthing like this with its
PrimeQ function. (I functions like NextPrime mentioned in Ted's
message do not give a genuine "prime certificate", although the
NumberTheory`PrimeQ` package does contain very much slower function
which does provide one). Perhaps algorithms based on GRH should also be
implemented in the same way?
Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp/
http://eri2.tuins.ac.jp/