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

Fermat or Rabin/Miller PRP test uing YEAFFT

Expand Messages
  • j_chrtn
    Hello group, Does anyone of you knows if there exists a C program to perform PRP tests (basic Fermat test or Rabin/Miller test) using the YEAFFT library that
    Message 1 of 6 , Sep 2, 2008
    • 0 Attachment
      Hello group,

      Does anyone of you knows if there exists a C program to perform PRP
      tests (basic Fermat test or Rabin/Miller test) using the YEAFFT library
      that comes with glucas package ?

      As far as I know, glucas can only check for primality of Mersenne's
      numbers and cannot test other numbers for probable primality.

      Regards,

      JL
    • Phil Carmody
      ... I seem to remember it comes with the ability to replace GMP multiplication routines. Get that working, and then just use the usual GMP exponentiation
      Message 2 of 6 , Sep 2, 2008
      • 0 Attachment
        > Does anyone of you knows if there exists a C program to
        > perform PRP
        > tests (basic Fermat test or Rabin/Miller test) using the
        > YEAFFT library
        > that comes with glucas package ?
        >
        > As far as I know, glucas can only check for primality of
        > Mersenne's
        > numbers and cannot test other numbers for probable
        > primality.

        I seem to remember it comes with the ability to replace GMP multiplication routines.
        Get that working, and then just use the usual GMP exponentiation routines, and it will use the YEAFFT multiplications.

        Phil
      • Mark Rodenkirch
        Are there numbers of specific form that you want to test? For example, if you want to test numbers of the form k*b^n+/-1, then there are options that don t
        Message 3 of 6 , Sep 2, 2008
        • 0 Attachment
          Are there numbers of specific form that you want to test? For
          example, if you want to test numbers of the form k*b^n+/-1, then there
          are options that don't use YEAFFT.

          On Sep 2, 2008, at 8:04 AM, j_chrtn wrote:

          > Hello group,
          >
          > Does anyone of you knows if there exists a C program to perform PRP
          > tests (basic Fermat test or Rabin/Miller test) using the YEAFFT
          > library
          > that comes with glucas package ?
          >
          > As far as I know, glucas can only check for primality of Mersenne's
          > numbers and cannot test other numbers for probable primality.
          >
          > Regards,
          >
          > JL



          [Non-text portions of this message have been removed]
        • j_chrtn
          ... multiplication routines. ... routines, and it will use the YEAFFT multiplications. ... Hi Phil, If I can plug YEAFFT multiplication routines into GMP
          Message 4 of 6 , Sep 2, 2008
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...>
            wrote:
            >
            > > Does anyone of you knows if there exists a C program to
            > > perform PRP
            > > tests (basic Fermat test or Rabin/Miller test) using the
            > > YEAFFT library
            > > that comes with glucas package ?
            > >
            > > As far as I know, glucas can only check for primality of
            > > Mersenne's
            > > numbers and cannot test other numbers for probable
            > > primality.
            >
            > I seem to remember it comes with the ability to replace GMP
            multiplication routines.
            > Get that working, and then just use the usual GMP exponentiation
            routines, and it will use the YEAFFT multiplications.
            >
            > Phil
            >

            Hi Phil,

            If I can plug YEAFFT multiplication routines into GMP library, that
            great.
            However, in this case, I wonder how difficult it is to do and most of
            all how I can then take advantage of the ability of YEAFTT to
            parallelize computation on SMP computers from the GMP exponentiation
            routines ?

            Actually, this is mostly this ability of YEAFTT to fit well on SMP
            machines that interested me to test PRP of the form (n+1)^p-n^p and
            especially 138^p-137^p. This later case is very tough : I've checked
            all prime exponents up to 168000 and found no PRP :-(

            JL
          • j_chrtn
            ... there ... PRP ... Mersenne s ... Hello Mark, As mentioned in my previous reply to Phil, the numbers I want to check are (n+1)^p-n^p for which I don t know
            Message 5 of 6 , Sep 2, 2008
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, Mark Rodenkirch <mgrogue@...>
              wrote:
              >
              > Are there numbers of specific form that you want to test? For
              > example, if you want to test numbers of the form k*b^n+/-1, then
              there
              > are options that don't use YEAFFT.
              >
              > On Sep 2, 2008, at 8:04 AM, j_chrtn wrote:
              >
              > > Hello group,
              > >
              > > Does anyone of you knows if there exists a C program to perform
              PRP
              > > tests (basic Fermat test or Rabin/Miller test) using the YEAFFT
              > > library
              > > that comes with glucas package ?
              > >
              > > As far as I know, glucas can only check for primality of
              Mersenne's
              > > numbers and cannot test other numbers for probable primality.
              > >
              > > Regards,
              > >
              > > JL
              >
              >
              >
              > [Non-text portions of this message have been removed]
              >

              Hello Mark,

              As mentioned in my previous reply to Phil, the numbers I want to
              check are (n+1)^p-n^p for which I don't know any
              specialized/optimized program. So I used to use pfgw for this
              purpose. Pfgw is great but as far as I know cannot take advantage of
              SMP hardware...

              Do you have any idea of a program I could use for this form of
              numbers on SMP ?

              Regards,

              JL
            • Mark Rodenkirch
              pfgw is your best bet. I don t know if YEAFFT will be faster than it for numbers of that form. ... [Non-text portions of this message have been removed]
              Message 6 of 6 , Sep 2, 2008
              • 0 Attachment
                pfgw is your best bet. I don't know if YEAFFT will be faster than it
                for numbers of that form.

                On Sep 2, 2008, at 6:20 PM, j_chrtn wrote:

                > Hello Mark,
                >
                > As mentioned in my previous reply to Phil, the numbers I want to
                > check are (n+1)^p-n^p for which I don't know any
                > specialized/optimized program. So I used to use pfgw for this
                > purpose. Pfgw is great but as far as I know cannot take advantage of
                > SMP hardware...
                >
                > Do you have any idea of a program I could use for this form of
                > numbers on SMP ?
                >
                > Regards,
                >
                > JL



                [Non-text portions of this message have been removed]
              Your message has been successfully submitted and would be delivered to recipients shortly.