Re: [PrimeNumbers] APRCL prime test
- On Thursday 02 Jan 2003 1:10 pm, Phil Carmody wrote:
> --- Jason Moxham <j.l.moxham@...> wrote:The recently corrected bug was type 3 , although as it was rare it acted like
> > A new version availible here
> > http://220.127.116.11/gmp/prime1.15.tar.bz2
> > which corrects some minor bugs , thanks to Phil Carmody
> > NOTE:
> > This should still be regarded as experimental.
> There are three kinds of bugs:
> 1) Bugs that can make a prime number be declared composite
> 2) Bugs that can make a composite number be declared prime
> 3) Bugs that can do whatever teh dickens they like, including the above 2.
> The only numbers that I had probles with were numbers with a potentially
> difficult form, and the only problems I noticed were known primes being
> declared composite. Do you know which category the above bug fell into?
> Is there any reason yet to actually doubt any of the 'is prime' resultsNo specific reason , except the usual bugs that are in any program
> that come from your APRCL? I'm proving everything I do in parallel, your
> APRCL and Francois Morain's ECPP, which is a race that you're currentlyAssuming the "problem" is fairly simple , and doesn't affect the speed much ,
> winning, so at the moment nothing I'm doing is at risk (expect everything
> takes more than twice as long).
then I reckon I can get perhaps x5 speedup , and using some sort of encrypted
hash codes we can also have a prime signature/certificate. And of course
APRCL distributes over many cpus.
How does the APRCL speed compair to ECPP signature check only ?
> > I haven't done any work on itIf I muck up the search but not the actual calculation then yes , which is
> > since May last year and the source code is in a mess since in the middle
> > of testing some optimizations I discoved a possible problem with it , and
> > until I can resolve this problem I wont being doing any new
> > optimizations.
> > A brief description of the problem follows , in the hope that someone can
> > help me please.
> > The "problem" is pretty simple .
> > In the psuedoprime part of the test , we have to calculate a number in
> > the ring Z/NZ[\delta] and test whether it is a root of unity , where
> > delta is a primative p^k th root of unity. Like everyone else I represent
> > elements of this ring as polynominals mod the p^k cyclotomic polynominal
> > , with coeffs as intergers mod N . Now this is not the most effiecient
> > representation , but it is simple to program (or is it?). The calculation
> > poses no problem , it's the test to see whether the result is a root of
> > unity , how do you do it ?
> The pseudoprime is a search, and if the search fails the program returns
> 'is composite'. Therefore if you muck up teh search, you can only be left
> with a type-1 error? So your 'is primes' are still valid, surely?
what I think the problem is
> The answer to life's mystery is simple and direct:
> Sex and death. -- Ian 'Lemmy' Kilminster
> Do you Yahoo!?
> Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
> Unsubscribe by an email to: firstname.lastname@example.org
> The Prime Pages : http://www.primepages.org/
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/