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/