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

Re: [PrimeNumbers] Fermat or Rabin/Miller PRP test uing YEAFFT

Expand Messages
  • 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 1 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 2 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 3 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 4 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.