MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

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/



  • Prev by Date: FW: Re: Frequencies function
  • Next by Date: Cuboid & RotateShape
  • Previous by thread: Re:FW: Re: Frequencies function
  • Next by thread: Cuboid & RotateShape