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

Re: Sieving a (new) form

Expand Messages
  • Paul Underwood
    ... Phil Carmody not only has a sieve for this form, he also has a PRP test program that is quicker than PFGW for this form. Good luck! Paul
    Message 1 of 9 , Nov 3, 2005
    View Source
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, Cletus Emmanuel <cemmanu@y...> wrote:
      >
      > Can anyone sieve the form N= (2^k)*(2^(k+1) + 1) + 1?
      >
      > Mark R., can you customize Multisieve?
      >
      > Phil C., can you customize ksieve?
      >
      >
      > Can anyone else customize a sieve?
      >

      Phil Carmody not only has a sieve for this form, he also has a PRP
      test program that is quicker than PFGW for this form.

      Good luck!

      Paul
    • eharsh82
      Is there a paper/explanation how Phil managed to make his program faster than PFGW. I think he does mult mod 2^3*x-1. So he can use DWT. But PFGW uses this
      Message 2 of 9 , Nov 5, 2005
      View Source
      • 0 Attachment
        Is there a paper/explanation how Phil managed to make his program
        faster than PFGW.

        I think he does mult mod 2^3*x-1. So he can use DWT. But PFGW uses
        this also. Is his program faster than GW's library?

        Harsh Aggarwal

        --- In primenumbers@yahoogroups.com, "Paul Underwood"
        <paulunderwood@m...> wrote:
        >
        > --- In primenumbers@yahoogroups.com, Cletus Emmanuel
        <cemmanu@y...> wrote:
        > >
        > > Can anyone sieve the form N= (2^k)*(2^(k+1) + 1) + 1?
        > >
        > > Mark R., can you customize Multisieve?
        > >
        > > Phil C., can you customize ksieve?
        > >
        > >
        > > Can anyone else customize a sieve?
        > >
        >
        > Phil Carmody not only has a sieve for this form, he also has a PRP
        > test program that is quicker than PFGW for this form.
        >
        > Good luck!
        >
        > Paul
        >
      • Paul Underwood
        Hi, it s a simple enough trick. Cletus New form is equal to: N=2^(2*k+1)+2^k + 1, a trinomial. Now, when doing exponent-based test of Fermat we practically
        Message 3 of 9 , Nov 5, 2005
        View Source
        • 0 Attachment
          Hi,

          it's a simple enough trick. Cletus' "New" form is equal to:

          N=2^(2*k+1)+2^k + 1, a trinomial.

          Now, when doing exponent-based test of Fermat we practically do a
          squaring and a modular reduction, both repeatedly for as many bits as
          there are in "N". It is the modular reduction which is where we can
          save time over PFGW by just shifting computer bits and not doing the
          lengthy generic method that PFGW employs instead.

          Think about it binary:

          U*2^(2*k+1) == -U*(2^k) -U Modulo N

          The left hand side ends in just 2*k+1 zeros. The multipler M which
          comes from a squaring (during exponention) makes the left hand side
          greater than "N" -- we just add the right hand side:

          (A^2) = U*2^(2*k+1)+L = L-U*(2^k) -U all Mod N

          (U and L are used to be indicative of upper and lower order bits.)

          An actual implementation might be slightly different.

          FatPhil's "C" code is faster than George's assembler library used by
          PFGW for this particular form :0

          DWT orientated it's not (yet!)

          Paul

          --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...> wrote:
          >
          > Is there a paper/explanation how Phil managed to make his program
          > faster than PFGW.
          >
          > I think he does mult mod 2^3*x-1. So he can use DWT. But PFGW uses
          > this also. Is his program faster than GW's library?
          >
          > Harsh Aggarwal
          >
          > --- In primenumbers@yahoogroups.com, "Paul Underwood"
          > <paulunderwood@m...> wrote:
          > >
          > > --- In primenumbers@yahoogroups.com, Cletus Emmanuel
          > <cemmanu@y...> wrote:
          > > >
          > > > Can anyone sieve the form N= (2^k)*(2^(k+1) + 1) + 1?
          > > >
          > > > Mark R., can you customize Multisieve?
          > > >
          > > > Phil C., can you customize ksieve?
          > > >
          > > >
          > > > Can anyone else customize a sieve?
          > > >
          > >
          > > Phil Carmody not only has a sieve for this form, he also has a PRP
          > > test program that is quicker than PFGW for this form.
          > >
          > > Good luck!
          > >
          > > Paul
          > >
          >
        • eharsh82
          If this is how Phil s program works, I do not see how it will be faster than PFGW for base2. If you use PFGW -j3*a. Then PFGW, uses DWT, and should be saving
          Message 4 of 9 , Nov 5, 2005
          View Source
          • 0 Attachment
            If this is how Phil's program works, I do not see how it will be
            faster than PFGW for base2.

            If you use PFGW -j3*a. Then PFGW, uses DWT, and should be saving
            time in modular reductions, so I see no reason why Phil's sieve is
            faster. May be a benchmark will help, or if Phil could answer my
            question.

            Harsh


            --- In primenumbers@yahoogroups.com, "Paul Underwood"
            <paulunderwood@m...> wrote:
            >
            > Hi,
            >
            > it's a simple enough trick. Cletus' "New" form is equal to:
            >
            > N=2^(2*k+1)+2^k + 1, a trinomial.
            >
            > Now, when doing exponent-based test of Fermat we practically do a
            > squaring and a modular reduction, both repeatedly for as many bits
            as
            > there are in "N". It is the modular reduction which is where we can
            > save time over PFGW by just shifting computer bits and not doing
            the
            > lengthy generic method that PFGW employs instead.
            >
            > Think about it binary:
            >
            > U*2^(2*k+1) == -U*(2^k) -U Modulo N
            >
            > The left hand side ends in just 2*k+1 zeros. The multipler M which
            > comes from a squaring (during exponention) makes the left hand side
            > greater than "N" -- we just add the right hand side:
            >
            > (A^2) = U*2^(2*k+1)+L = L-U*(2^k) -U all Mod N
            >
            > (U and L are used to be indicative of upper and lower order bits.)
            >
            > An actual implementation might be slightly different.
            >
            > FatPhil's "C" code is faster than George's assembler library used
            by
            > PFGW for this particular form :0
            >
            > DWT orientated it's not (yet!)
            >
            > Paul
            >
            > --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...> wrote:
            > >
            > > Is there a paper/explanation how Phil managed to make his
            program
            > > faster than PFGW.
            > >
            > > I think he does mult mod 2^3*x-1. So he can use DWT. But PFGW
            uses
            > > this also. Is his program faster than GW's library?
            > >
            > > Harsh Aggarwal
            > >
            > > --- In primenumbers@yahoogroups.com, "Paul Underwood"
            > > <paulunderwood@m...> wrote:
            > > >
            > > > --- In primenumbers@yahoogroups.com, Cletus Emmanuel
            > > <cemmanu@y...> wrote:
            > > > >
            > > > > Can anyone sieve the form N= (2^k)*(2^(k+1) + 1) + 1?
            > > > >
            > > > > Mark R., can you customize Multisieve?
            > > > >
            > > > > Phil C., can you customize ksieve?
            > > > >
            > > > >
            > > > > Can anyone else customize a sieve?
            > > > >
            > > >
            > > > Phil Carmody not only has a sieve for this form, he also has a
            PRP
            > > > test program that is quicker than PFGW for this form.
            > > >
            > > > Good luck!
            > > >
            > > > Paul
            > > >
            > >
            >
          • Paul Underwood
            Hmm, -j3*a for 2^(2*k)+2^k+1 ? Cletus form 2^(2*k+1)+2^k+1 is different. (FatPhil s *sieve* is the only one I know of for Cletus New form.) Paul
            Message 5 of 9 , Nov 5, 2005
            View Source
            • 0 Attachment
              Hmm,

              -j3*a for 2^(2*k)+2^k+1 ?

              Cletus' form 2^(2*k+1)+2^k+1 is different.

              (FatPhil's *sieve* is the only one I know of for Cletus' "New" form.)

              Paul

              --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...> wrote:
              >
              > If this is how Phil's program works, I do not see how it will be
              > faster than PFGW for base2.
              >
              > If you use PFGW -j3*a. Then PFGW, uses DWT, and should be saving
              > time in modular reductions, so I see no reason why Phil's sieve is
              > faster. May be a benchmark will help, or if Phil could answer my
              > question.
              >
              > Harsh
              >
              >
              > --- In primenumbers@yahoogroups.com, "Paul Underwood"
              > <paulunderwood@m...> wrote:
              > >
              > > Hi,
              > >
              > > it's a simple enough trick. Cletus' "New" form is equal to:
              > >
              > > N=2^(2*k+1)+2^k + 1, a trinomial.
              > >
              > > Now, when doing exponent-based test of Fermat we practically do a
              > > squaring and a modular reduction, both repeatedly for as many bits
              > as
              > > there are in "N". It is the modular reduction which is where we can
              > > save time over PFGW by just shifting computer bits and not doing
              > the
              > > lengthy generic method that PFGW employs instead.
              > >
              > > Think about it binary:
              > >
              > > U*2^(2*k+1) == -U*(2^k) -U Modulo N
              > >
              > > The left hand side ends in just 2*k+1 zeros. The multipler M which
              > > comes from a squaring (during exponention) makes the left hand side
              > > greater than "N" -- we just add the right hand side:
              > >
              > > (A^2) = U*2^(2*k+1)+L = L-U*(2^k) -U all Mod N
              > >
              > > (U and L are used to be indicative of upper and lower order bits.)
              > >
              > > An actual implementation might be slightly different.
              > >
              > > FatPhil's "C" code is faster than George's assembler library used
              > by
              > > PFGW for this particular form :0
              > >
              > > DWT orientated it's not (yet!)
              > >
              > > Paul
              > >
              > > --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...> wrote:
              > > >
              > > > Is there a paper/explanation how Phil managed to make his
              > program
              > > > faster than PFGW.
              > > >
              > > > I think he does mult mod 2^3*x-1. So he can use DWT. But PFGW
              > uses
              > > > this also. Is his program faster than GW's library?
              > > >
              > > > Harsh Aggarwal
              > > >
              > > > --- In primenumbers@yahoogroups.com, "Paul Underwood"
              > > > <paulunderwood@m...> wrote:
              > > > >
              > > > > --- In primenumbers@yahoogroups.com, Cletus Emmanuel
              > > > <cemmanu@y...> wrote:
              > > > > >
              > > > > > Can anyone sieve the form N= (2^k)*(2^(k+1) + 1) + 1?
              > > > > >
              > > > > > Mark R., can you customize Multisieve?
              > > > > >
              > > > > > Phil C., can you customize ksieve?
              > > > > >
              > > > > >
              > > > > > Can anyone else customize a sieve?
              > > > > >
              > > > >
              > > > > Phil Carmody not only has a sieve for this form, he also has a
              > PRP
              > > > > test program that is quicker than PFGW for this form.
              > > > >
              > > > > Good luck!
              > > > >
              > > > > Paul
              > > > >
              > > >
              > >
              >
            • eharsh82
              I think there is a misunderstanding here. I was talking about Phil s FFT client for PIES and not his sieve client. Any idea why is it faster than PFGW. Harsh
              Message 6 of 9 , Nov 5, 2005
              View Source
              • 0 Attachment
                I think there is a misunderstanding here. I was talking about Phil's
                FFT client for PIES and not his sieve client. Any idea why is it
                faster than PFGW.

                Harsh


                --- In primenumbers@yahoogroups.com, "Paul Underwood"
                <paulunderwood@m...> wrote:
                >
                > Hmm,
                >
                > -j3*a for 2^(2*k)+2^k+1 ?
                >
                > Cletus' form 2^(2*k+1)+2^k+1 is different.
                >
                > (FatPhil's *sieve* is the only one I know of for Cletus' "New"
                form.)
                >
                > Paul
                >
                > --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...> wrote:
                > >
                > > If this is how Phil's program works, I do not see how it will be
                > > faster than PFGW for base2.
                > >
                > > If you use PFGW -j3*a. Then PFGW, uses DWT, and should be saving
                > > time in modular reductions, so I see no reason why Phil's sieve
                is
                > > faster. May be a benchmark will help, or if Phil could answer my
                > > question.
                > >
                > > Harsh
                > >
                > >
                > > --- In primenumbers@yahoogroups.com, "Paul Underwood"
                > > <paulunderwood@m...> wrote:
                > > >
                > > > Hi,
                > > >
                > > > it's a simple enough trick. Cletus' "New" form is equal to:
                > > >
                > > > N=2^(2*k+1)+2^k + 1, a trinomial.
                > > >
                > > > Now, when doing exponent-based test of Fermat we practically
                do a
                > > > squaring and a modular reduction, both repeatedly for as many
                bits
                > > as
                > > > there are in "N". It is the modular reduction which is where
                we can
                > > > save time over PFGW by just shifting computer bits and not
                doing
                > > the
                > > > lengthy generic method that PFGW employs instead.
                > > >
                > > > Think about it binary:
                > > >
                > > > U*2^(2*k+1) == -U*(2^k) -U Modulo N
                > > >
                > > > The left hand side ends in just 2*k+1 zeros. The multipler M
                which
                > > > comes from a squaring (during exponention) makes the left hand
                side
                > > > greater than "N" -- we just add the right hand side:
                > > >
                > > > (A^2) = U*2^(2*k+1)+L = L-U*(2^k) -U all Mod N
                > > >
                > > > (U and L are used to be indicative of upper and lower order
                bits.)
                > > >
                > > > An actual implementation might be slightly different.
                > > >
                > > > FatPhil's "C" code is faster than George's assembler library
                used
                > > by
                > > > PFGW for this particular form :0
                > > >
                > > > DWT orientated it's not (yet!)
                > > >
                > > > Paul
                > > >
                > > > --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...>
                wrote:
                > > > >
                > > > > Is there a paper/explanation how Phil managed to make his
                > > program
                > > > > faster than PFGW.
                > > > >
                > > > > I think he does mult mod 2^3*x-1. So he can use DWT. But
                PFGW
                > > uses
                > > > > this also. Is his program faster than GW's library?
                > > > >
                > > > > Harsh Aggarwal
                > > > >
                > > > > --- In primenumbers@yahoogroups.com, "Paul Underwood"
                > > > > <paulunderwood@m...> wrote:
                > > > > >
                > > > > > --- In primenumbers@yahoogroups.com, Cletus Emmanuel
                > > > > <cemmanu@y...> wrote:
                > > > > > >
                > > > > > > Can anyone sieve the form N= (2^k)*(2^(k+1) + 1) + 1?
                > > > > > >
                > > > > > > Mark R., can you customize Multisieve?
                > > > > > >
                > > > > > > Phil C., can you customize ksieve?
                > > > > > >
                > > > > > >
                > > > > > > Can anyone else customize a sieve?
                > > > > > >
                > > > > >
                > > > > > Phil Carmody not only has a sieve for this form, he also
                has a
                > > PRP
                > > > > > test program that is quicker than PFGW for this form.
                > > > > >
                > > > > > Good luck!
                > > > > >
                > > > > > Paul
                > > > > >
                > > > >
                > > >
                > >
                >
              • Paul Underwood
                Oh I see. There are two good reasons why FatPhil s PIES program is quick: FatPhil s good programming abilities; and the many tricks employed by Dan Bernstien
                Message 7 of 9 , Nov 6, 2005
                View Source
                • 0 Attachment
                  Oh I see.

                  There are two good reasons why FatPhil's PIES program is quick:
                  FatPhil's good programming abilities; and the many "tricks" employed
                  by Dan Bernstien in his library:
                  http://cr.yp.to/djbfft.html

                  Paul
                  --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...> wrote:
                  >
                  > I think there is a misunderstanding here. I was talking about Phil's
                  > FFT client for PIES and not his sieve client. Any idea why is it
                  > faster than PFGW.
                  >
                  > Harsh
                  >
                  >
                  > --- In primenumbers@yahoogroups.com, "Paul Underwood"
                  > <paulunderwood@m...> wrote:
                  > >
                  > > Hmm,
                  > >
                  > > -j3*a for 2^(2*k)+2^k+1 ?
                  > >
                  > > Cletus' form 2^(2*k+1)+2^k+1 is different.
                  > >
                  > > (FatPhil's *sieve* is the only one I know of for Cletus' "New"
                  > form.)
                  > >
                  > > Paul
                  > >
                  > > --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...> wrote:
                  > > >
                  > > > If this is how Phil's program works, I do not see how it will be
                  > > > faster than PFGW for base2.
                  > > >
                  > > > If you use PFGW -j3*a. Then PFGW, uses DWT, and should be saving
                  > > > time in modular reductions, so I see no reason why Phil's sieve
                  > is
                  > > > faster. May be a benchmark will help, or if Phil could answer my
                  > > > question.
                  > > >
                  > > > Harsh
                  > > >
                  > > >
                  > > > --- In primenumbers@yahoogroups.com, "Paul Underwood"
                  > > > <paulunderwood@m...> wrote:
                  > > > >
                  > > > > Hi,
                  > > > >
                  > > > > it's a simple enough trick. Cletus' "New" form is equal to:
                  > > > >
                  > > > > N=2^(2*k+1)+2^k + 1, a trinomial.
                  > > > >
                  > > > > Now, when doing exponent-based test of Fermat we practically
                  > do a
                  > > > > squaring and a modular reduction, both repeatedly for as many
                  > bits
                  > > > as
                  > > > > there are in "N". It is the modular reduction which is where
                  > we can
                  > > > > save time over PFGW by just shifting computer bits and not
                  > doing
                  > > > the
                  > > > > lengthy generic method that PFGW employs instead.
                  > > > >
                  > > > > Think about it binary:
                  > > > >
                  > > > > U*2^(2*k+1) == -U*(2^k) -U Modulo N
                  > > > >
                  > > > > The left hand side ends in just 2*k+1 zeros. The multipler M
                  > which
                  > > > > comes from a squaring (during exponention) makes the left hand
                  > side
                  > > > > greater than "N" -- we just add the right hand side:
                  > > > >
                  > > > > (A^2) = U*2^(2*k+1)+L = L-U*(2^k) -U all Mod N
                  > > > >
                  > > > > (U and L are used to be indicative of upper and lower order
                  > bits.)
                  > > > >
                  > > > > An actual implementation might be slightly different.
                  > > > >
                  > > > > FatPhil's "C" code is faster than George's assembler library
                  > used
                  > > > by
                  > > > > PFGW for this particular form :0
                  > > > >
                  > > > > DWT orientated it's not (yet!)
                  > > > >
                  > > > > Paul
                  > > > >
                  > > > > --- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...>
                  > wrote:
                  > > > > >
                  > > > > > Is there a paper/explanation how Phil managed to make his
                  > > > program
                  > > > > > faster than PFGW.
                  > > > > >
                  > > > > > I think he does mult mod 2^3*x-1. So he can use DWT. But
                  > PFGW
                  > > > uses
                  > > > > > this also. Is his program faster than GW's library?
                  > > > > >
                  > > > > > Harsh Aggarwal
                  > > > > >
                  > > > > > --- In primenumbers@yahoogroups.com, "Paul Underwood"
                  > > > > > <paulunderwood@m...> wrote:
                  > > > > > >
                  > > > > > > --- In primenumbers@yahoogroups.com, Cletus Emmanuel
                  > > > > > <cemmanu@y...> wrote:
                  > > > > > > >
                  > > > > > > > Can anyone sieve the form N= (2^k)*(2^(k+1) + 1) + 1?
                  > > > > > > >
                  > > > > > > > Mark R., can you customize Multisieve?
                  > > > > > > >
                  > > > > > > > Phil C., can you customize ksieve?
                  > > > > > > >
                  > > > > > > >
                  > > > > > > > Can anyone else customize a sieve?
                  > > > > > > >
                  > > > > > >
                  > > > > > > Phil Carmody not only has a sieve for this form, he also
                  > has a
                  > > > PRP
                  > > > > > > test program that is quicker than PFGW for this form.
                  > > > > > >
                  > > > > > > Good luck!
                  > > > > > >
                  > > > > > > Paul
                  > > > > > >
                  > > > > >
                  > > > >
                  > > >
                  > >
                  >
                Your message has been successfully submitted and would be delivered to recipients shortly.