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/