From: cet1@cus.cam.ac.uk (Chris Thompson) Newsgroups: sci.math Subject: Primality tests and factoring methods (was: Re: 9, prime gone bad....) Date: 9 Feb 1996 12:38:19 GMT [Newsgroups pruned; subject modified] In article , dik@cwi.nl (Dik T. Winter) writes: |> In article <4fdvcs$s9e@status.gen.nz> ericf@central.co.nz (Eric Flesch) writes: [...] |> > You have not demonstrated that prime numbers can be quickly verified |> > as being prime. |> |> But it can. Much faster than trying to determine the factors. There |> are deterministic methods that will give proof that a number is prime or |> not without trying to find any factor, and very much faster. I have a |> program here (*) that will tell you in a few minutes whether a 200-digit |> number is prime or not, and it is *not* probabilistic. |> |> As far as I know all factor finding methods are non-deterministic, except |> division by succesive primes. It isn't *that* bad. There are deterministic factoring methods that take time n^c to factor n, for values of c < 1/2. The most famous is Lehmann's n^{1/3} method (Math Comp 28 (1974) 637-646) based in carrying Fermat's difference-of-squares method through to its logical conclusion, but there are several others. Richard Pinch gave an interesting talk at the SECANTS meeting in December on the current state of research in this area. [But my notes on what he said are at home :-(] |> That is, all numbers succumb within the time |> estimated for the other methods (which is very long for 200-digit numbers) |> by the order-formula's, but as far as I know there is no proof that all will. |> But perhaps Bob Silverman or Peter Montgomery know better. One also needs to make a distinction between methods which have provable random f(n) time (i.e. with truely random inputs any n will be factored with probability > 1 - epsilon in time < C(epsilon)*f(n)) and those for which one knows their asymptotic behaviour only on a heurstic/experimental basis. There are known sub-exponential methods in the first category, but their constants aren't as good as those in the second. |> Also it is known that if the Riemann hypothesis holds that primality testing |> is even much cheaper than it is now, while it does not help very much in |> factor finding. |> -- |> (*) The program is by Lenstra and Cohen with some of the basics in it done |> by me. A short introduction about it can be found in some back issues of |> Mathematics of Computation (around 1986 say). There have been later |> improvements that make primality testing of 1000-digit numbers doable. |> Forget factorization of those numbers for the time being. Chris Thompson Email: cet1@cam.ac.uk ============================================================================== Newsgroups: alt.philosophy.objectivism,alt.sci.physics.new-theories,sci.physics,comp.ai,comp.ai.philosophy,sci.philosophy.meta,sci.math From: dik@cwi.nl (Dik T. Winter) Subject: Re: 9, prime gone bad. was RE: zero blah blah Date: Fri, 9 Feb 1996 00:03:00 GMT In article <4fdvcs$s9e@status.gen.nz> ericf@central.co.nz (Eric Flesch) writes: > rusin@washington.math.niu.edu (Dave Rusin) wrote: > >This is false. There are methods of determining the primality of an > >integer which are much faster and which, in particular, do not imply > >any knowledge of the factors if the number is indeed shown to be > >composite. Just to give a simple and useful example, if 2^n (mod n) > >isn't 2, then n isn't prime. > > All you have demonstrated is that the determination can be done > quickly for SOME numbers, i.e. those which can be quickly falsified. > You have not demonstrated that prime numbers can be quickly verified > as being prime. But it can. Much faster than trying to determine the factors. There are deterministic methods that will give proof that a number is prime or not without trying to find any factor, and very much faster. I have a program here (*) that will tell you in a few minutes whether a 200-digit number is prime or not, and it is *not* probabilistic. As far as I know all factor finding methods are non-deterministic, except division by succesive primes. That is, all numbers succumb within the time estimated for the other methods (which is very long for 200-digit numbers) by the order-formula's, but as far as I know there is no proof that all will. But perhaps Bob Silverman or Peter Montgomery know better. Also it is known that if the Riemann hypothesis holds that primality testing is even much cheaper than it is now, while it does not help very much in factor finding. -- (*) The program is by Lenstra and Cohen with some of the basics in it done by me. A short introduction about it can be found in some back issues of Mathematics of Computation (around 1986 say). There have been later improvements that make primality testing of 1000-digit numbers doable. Forget factorization of those numbers for the time being. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/