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

APRCL prime test

Expand Messages
  • Jason Moxham
    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
    Message 1 of 3 , Jan 2, 2003
    • 0 Attachment
      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. 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 ?

      My first try was to power it , and see if it is 1 , this works (but see below)
      but is slow.
      The second attempt was to check it directly by working out how each root of
      unity is represented as a polynominal , and doing a direct compairison , this
      works (but see below) and is very fast. This is how everyone does it.

      The problem is that the two above approaches assume that the representation of
      elements of the ring as polynominals is unique.

      A simpler example would be consider the representation of rational numbers as
      a pair of intergers , how do test that a number is 1 ? , you must either put
      the representation into canonical form (divide top and bottom by the gcd) or
      check for all possible representations of 1 as a fraction (which in this case
      is trivial)

      The "problem" is that I do know how to do this test , but no one else does it
      this way , why ???
      either they have all forgotten , and that their programs all have this error ,
      or that there is some reason/trick that I've missed that gets around it , or
      I have a completely incorrect understanding of the algorithm.

      I know of no examples of where this happens in practice , although I'm sure I
      can construct a artificial example . I think it may happen when the p^k 'th
      cyclotomic polynominal is reducible over Z/NZ (where N is the number being
      tested) and p,k the usual .

      Help please!!!


      Jason Moxham
      j.l.moxham@...
    • Phil Carmody
      ... 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)
      Message 2 of 3 , Jan 2, 2003
      • 0 Attachment
        --- 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?

        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 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).

        > 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?

        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
      • 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 3 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.