Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] APRCL prime test

Expand Messages
  • Jason Moxham
    ... The recently corrected bug was type 3 , although as it was rare it acted like type 1 ... No specific reason , except the usual bugs that are in any program
    Message 1 of 3 , Jan 2, 2003
    • 0 Attachment
      On Thursday 02 Jan 2003 1:10 pm, Phil Carmody wrote:
      > --- Jason Moxham <j.l.moxham@...> wrote:
      > > A new version availible here
      > >
      > > http://217.35.81.229/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?
      >

      The recently corrected bug was type 3 , although as it was rare it acted like
      type 1

      > Is there any reason yet to actually doubt any of the 'is prime' results
      > that come from your APRCL? I'm proving everything I do in parallel, your

      No specific reason , except the usual bugs that are in any program

      > APRCL and Francois Morain's ECPP, which is a race that you're currently
      > winning, so at the moment nothing I'm doing is at risk (expect everything
      > takes more than twice as long).
      >

      Assuming the "problem" is fairly simple , and doesn't affect the speed much ,
      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 it
      > > 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?
      >

      If I muck up the search but not the actual calculation then yes , which is
      what I think the problem is

      > Phil
      >
      >
      > =====
      > 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.
      > http://mailplus.yahoo.com
      >
      > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      > The Prime Pages : http://www.primepages.org/
      >
      >
      >
      > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
    Your message has been successfully submitted and would be delivered to recipients shortly.