Re(2): Re: Together chokes with Prime Modulus > 46337
- To: mathgroup at smc.vnet.net
- Subject: [mg15186] Re(2): [mg15179] Re: [mg15155] Together chokes with Prime Modulus > 46337
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Fri, 18 Dec 1998 23:20:27 -0500
- Sender: owner-wri-mathgroup at wolfram.com
Thanks for replying. I am a topologist not a number theorist, but I did teach number theory about 8 years ago (using Mathematica v. 1!) and most of the knowledge of this area I have was acquired then. I guess the texts I used must have been about more than 20 years old then! I now remebered that the GRH is indeed used in proving that certain algorithms work in polynomial time ( it tells one the distribution of residues mod p) and not in the acutal construction of these algorithms. So my remarks concerning it are probably irrelevant. The question of the reason for the limitation of modular arithmetic remains unanswered and seems very interesting. It appears to be something of practical importance. In a message sent to me Ted Ersek pointed out that the ProvablePrimeQ function (part of the NumberTheory`PrimeQ` package) fails in certain cases to work precisely for this reason: try ProvablePrimeQ[25217504003]. On the other hand switching to the Pratt Certificate method by setting SmallPrime to some very large value (say 10^12)works at once. So somehow the elliptic curve method makes use of modular Together and fails, in a case that it ought to manage without difficulty (?) Have you got any idea if this restriction (on Together etc ) has an interersting "theoretical" cause, e.g. some algoritms not being known to work for large primes? If so it should to be documented, shouldn't it? Andrzej On Fri, Dec 18, 1998, Daniel Lichtblau <danl at wolfram.com> wrote: >>The limitation in modular arithemtic to the prime 46337 affects besides >>Together, the functions PolynomialGCD, PolynomialLCM, Factor and Solve, > >This is in essence the correct family (throw in Cancel and FactorList >which are clones of Together and Factor). But actually Solve is not >affected. It just issues a warning that some problem arose in an attempt >at making the problem easier, then keeps going. In the example you show >it finds a "solution" but cannot adequately simplify it. > > >>If I recall correctly...there is no deterministic >>polynomial time algorithm for factoring polynomials mod p > >There is such an algorithm, goes back around 30 years. Factoring over >the integers is not polynomial time (in bad cases) except with an >algorithm that has not proven to be useful in practice for that >particular purpose. What irony. Lattice reduction was invented to make >univariate factorization polynomial time, it is incredibly useful in >number theory applications, but so far as I know it is only of >theoretical interest for factorization. > >The probabilistic method is that of Cantor and Zassenhaus (if I remember >correctly). I think one can arrange that the probability of failure is >for all practical purposes negligeable. I also believe this does not >require GRH to prove. That machinery is more commonly needed when doing >complexity analyses of integer factorization algorithms. > > >Daniel Lichtblau >Wolrfam Research > Andrzej Kozlowski Toyama International University JAPAN http://sigma.tuins.ac.jp/ http://eri2.tuins.ac.jp/