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

Re: p-SPRP

Expand Messages
  • djbroadhurst
    ... Excellent! Maybe you could send this to Richard Pinch, via email address at http://www.chalcedon.demon.co.uk/rgep.html and tempt him into to spare-time
    Message 1 of 12 , Sep 1, 2002
    • 0 Attachment
      Leonid Durman wrote:
      > If n < 18,985,627 is a both
      > 31 and 1171 -SPRP, then n is prime.
      Excellent!
      Maybe you could send this to Richard Pinch, via
      email address at
      http://www.chalcedon.demon.co.uk/rgep.html
      and tempt him into to spare-time pseudoprime
      hunting?
      David
    • Phil Carmody
      ... Great work, Leonid. I briefly looked at this problem in the past, but I restricted myself to a smaller set of bases, and discovered that I was almost
      Message 2 of 12 , Sep 1, 2002
      • 0 Attachment
        --- Leonid Durman <durman@...> wrote:
        > Hello all,
        >
        > I have made small researches for page.
        > Strong PRPs
        > http://www.utm.edu//research/primes/prove/prove2_3.html
        >
        > I checked only two bases what to detect the best values for "Combining these
        > tests to prove primality".
        >
        > Chris Caldwell write:
        > > If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.
        >
        > checked a1<109, a2< 7919 and other values are retrieved:
        > If n < 9,254,521 is a both 103 and 6871-SPRP, then n is prime.
        > If n < 9,863,461 is a both 17 and 6661-SPRP, then n is prime.
        > and best
        > If n < 18,985,627 is a both 31 and 1171 -SPRP, then n is prime.
        >
        > Who more densely researched Combining tests for 2,3,4 ... values? More than
        > it is known on page Chris.
        > You see the knowledge of these numbers has practical value and to success
        > competes with the sieve of Eratosthenes with small numbers, for the daily
        > tests, because not enough memory requires.


        Great work, Leonid.
        I briefly looked at this problem in the past, but I restricted myself to a
        smaller set of bases, and discovered that I was almost certainly just
        treading over ground covered by Jaeschke already.

        Am I right in thinking that your a1/a2 distinction was to first find a1-SPSPs
        for all a1 in range, and then only check a2-SPSP-ness for this restricted
        set of candidates?

        This looks like it's screaming for some distributed computing effort...
        With a massively parallel modular multiplier/exponentiator such as Jim's or David's
        from their GFNSieve, it might be possible to push this a lot further.
        I'd happily stick my PPro/200 on this 24/7 for many a month, as it's doing
        nothing else presently (I know - it's a crime against primality).
        It looks like it can be distributed easily, as it's can be turned into a
        2D-task (which means it's easy to make sure people don't tread on each
        other's toes, and can still run as long as they want).


        Phil


        =====
        "The hottest places in Hell are reserved for those who, in
        times of moral crisis, preserved their neutrality."
        -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
        to whom this has been incorrectly attributed ever since.

        __________________________________________________
        Do You Yahoo!?
        Yahoo! Finance - Get real-time stock quotes
        http://finance.yahoo.com
      • Jason Moxham
        ... some more examples for composite bases remember to check gcd(n,base)=1 bases 2 & 1226150 and n
        Message 3 of 12 , Sep 1, 2002
        • 0 Attachment
          On Sunday 01 Sep 2002 11:46 pm, Phil Carmody wrote:
          > --- Leonid Durman <durman@...> wrote:
          > > Hello all,
          > >
          > > I have made small researches for page.
          > > Strong PRPs
          > > http://www.utm.edu//research/primes/prove/prove2_3.html
          > >
          > > I checked only two bases what to detect the best values for "Combining
          > > these tests to prove primality".
          > >
          > > Chris Caldwell write:
          > > > If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.
          > >
          > > checked a1<109, a2< 7919 and other values are retrieved:
          > > If n < 9,254,521 is a both 103 and 6871-SPRP, then n is prime.
          > > If n < 9,863,461 is a both 17 and 6661-SPRP, then n is prime.
          > > and best
          > > If n < 18,985,627 is a both 31 and 1171 -SPRP, then n is prime.
          > >

          some more examples

          for composite bases remember to check gcd(n,base)=1
          bases
          2 & 1226150 and n<38,210323 then n is prime
          2 & 305185 and n<72,498253 and sqrt condition then n is prime
          2 & 1121 & 6165 and n<20689,557337
          2 & 463 & 735 & 849 and n<5,486664,348901 then n is prime

          sqrt condition is checking that square root of -1 mod n are the same for all
          bases , this comes for "free" in the SPRP test ( we only test it if it is
          easy to find)

          > > Who more densely researched Combining tests for 2,3,4 ... values? More
          > > than it is known on page Chris.
          > > You see the knowledge of these numbers has practical value and to success
          > > competes with the sieve of Eratosthenes with small numbers, for the daily
          > > tests, because not enough memory requires.
          >
          > Great work, Leonid.
          > I briefly looked at this problem in the past, but I restricted myself to a
          > smaller set of bases, and discovered that I was almost certainly just
          > treading over ground covered by Jaeschke already.
          >
          > Am I right in thinking that your a1/a2 distinction was to first find
          > a1-SPSPs for all a1 in range, and then only check a2-SPSP-ness for this
          > restricted set of candidates?
          >
          > This looks like it's screaming for some distributed computing effort...
          > With a massively parallel modular multiplier/exponentiator such as Jim's or
          > David's from their GFNSieve, it might be possible to push this a lot
          > further. I'd happily stick my PPro/200 on this 24/7 for many a month, as
          > it's doing nothing else presently (I know - it's a crime against
          > primality).

          for finding SPRP's for a fixed set of bases it is best NOT to use any powering
          at all , I can dig out some referances if your interested , they use a
          backtracking search .

          > It looks like it can be distributed easily, as it's can be turned into a
          > 2D-task (which means it's easy to make sure people don't tread on each
          > other's toes, and can still run as long as they want).
          >

          It is easy to distribute , although note my code is not optimal , and
          temporary disabled (internet troubles..again..)

          http://217.35.81.229/dist.html

          jason

          >
          > Phil
          >
          >
          > =====
          > "The hottest places in Hell are reserved for those who, in
          > times of moral crisis, preserved their neutrality."
          > -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
          > to whom this has been incorrectly attributed ever since.
          >
          > __________________________________________________
          > Do You Yahoo!?
          > Yahoo! Finance - Get real-time stock quotes
          > http://finance.yahoo.com
          >
          >
          > Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
          > The Prime Pages : http://www.primepages.org
          >
          >
          >
          > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
        • Leonid Durman
          Hello all, ... It still best practical results. I have spent only hour for search. But at the large expenditures of time and resources it is possible to
          Message 4 of 12 , Sep 1, 2002
          • 0 Attachment
            Hello all,

            Jason wrote:
            >for composite bases remember to check gcd(n,base)=1
            >bases
            >2 & 1226150 and n<38,210323 then n is prime
            >2 & 305185 and n<72,498253 and sqrt condition then n is prime
            >2 & 1121 & 6165 and n<20689,557337
            >2 & 463 & 735 & 849 and n<5,486664,348901 then n is prime

            It still best practical results.
            I have spent only hour for search. But at the large expenditures of time and
            resources it is possible to discover the best values.
            Excellent work.


            >for finding SPRP's for a fixed set of bases it is best NOT to use any
            powering
            >at all , I can dig out some referances if your interested , they use a
            >backtracking search .

            Yes, certainly. I am interested in any information which can to help,
            and I plan to create the high-performance code on an assembler.
            I would be interested to discover the best outcomes for values n<2^64. The
            sieve here is already less effective, a lot of memory permanently requires
            even if to optimize. And for practical researches with prime, SPRP test
            would be useful.

            Regards

            Leonid Durman
          • Phil Carmody
            ... You basically mean remember the last-but-one value in the SPRP test. ... If you could get those references I d be grateful. I don t know exactly what you
            Message 5 of 12 , Sep 2, 2002
            • 0 Attachment
              --- Jason Moxham <j.l.moxham@...> wrote:
              > for composite bases remember to check gcd(n,base)=1
              > bases
              > 2 & 1226150 and n<38,210323 then n is prime
              > 2 & 305185 and n<72,498253 and sqrt condition then n is prime
              > 2 & 1121 & 6165 and n<20689,557337
              > 2 & 463 & 735 & 849 and n<5,486664,348901 then n is prime
              >
              > sqrt condition is checking that square root of -1 mod n are the same for all
              > bases , this comes for "free" in the SPRP test ( we only test it if it is
              > easy to find)

              You basically mean remember the last-but-one value in the SPRP test.

              > > > Who more densely researched Combining tests for 2,3,4 ... values? More
              > > > than it is known on page Chris.
              > > > You see the knowledge of these numbers has practical value and to success
              > > > competes with the sieve of Eratosthenes with small numbers, for the daily
              > > > tests, because not enough memory requires.
              > >
              > > Great work, Leonid.
              > > I briefly looked at this problem in the past, but I restricted myself to a
              > > smaller set of bases, and discovered that I was almost certainly just
              > > treading over ground covered by Jaeschke already.
              > >
              > > Am I right in thinking that your a1/a2 distinction was to first find
              > > a1-SPSPs for all a1 in range, and then only check a2-SPSP-ness for this
              > > restricted set of candidates?
              > >
              > > This looks like it's screaming for some distributed computing effort...
              > > With a massively parallel modular multiplier/exponentiator such as Jim's or
              > > David's from their GFNSieve, it might be possible to push this a lot
              > > further. I'd happily stick my PPro/200 on this 24/7 for many a month, as
              > > it's doing nothing else presently (I know - it's a crime against
              > > primality).
              >
              > for finding SPRP's for a fixed set of bases it is best NOT to use any powering
              > at all , I can dig out some referances if your interested , they use a
              > backtracking search .

              If you could get those references I'd be grateful.

              I don't know exactly what you mean by a backtracking search, but last night
              I thought about possible ways to approach this, and many ideas I came up
              with didn't involve performing SPRP tests. Some involved trial-dividing
              a few thousand large numers for small factors, others involved taking
              discrete logarthms modulo small bases (where small= half the size of the
              composites we'd be searching). In fact I was completely bamboozled by the
              number of different approaches to this problem that I could come up with.

              > > It looks like it can be distributed easily, as it's can be turned into a
              > > 2D-task (which means it's easy to make sure people don't tread on each
              > > other's toes, and can still run as long as they want).
              >
              > It is easy to distribute , although note my code is not optimal , and
              > temporary disabled (internet troubles..again..)
              >
              > http://217.35.81.229/dist.html

              You can always upload stuff like this to the files area of the yahoogroup.
              Just create a folder for it to keep things neat.

              Phil


              =====
              "The hottest places in Hell are reserved for those who, in
              times of moral crisis, preserved their neutrality."
              -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
              to whom this has been incorrectly attributed ever since.

              __________________________________________________
              Do You Yahoo!?
              Yahoo! Finance - Get real-time stock quotes
              http://finance.yahoo.com
            • djbroadhurst
              I see that Jason used 2 & x & y ... That makes the problem rather easy up to n=10^13, since one can pinch the file
              Message 6 of 12 , Sep 2, 2002
              • 0 Attachment
                I see that Jason used 2 & x & y ...
                That makes the problem rather easy up to
                n=10^13, since one can pinch the file
                http://www.chalcedon.demon.co.uk/rgep/spsp-13.gz
                How about up to 10^14 Jason :-)
                David
              • Phil Carmody
                ... Wipe that smilie off your post, David. Jason has all 2 SPSPs up to 4,503,586,330,870,201 Pinch is _such_ a 20th century resource... Phil ===== The hottest
                Message 7 of 12 , Sep 2, 2002
                • 0 Attachment
                  --- djbroadhurst <d.broadhurst@...> wrote:
                  > I see that Jason used 2 & x & y ...
                  > That makes the problem rather easy up to
                  > n=10^13, since one can pinch the file
                  > http://www.chalcedon.demon.co.uk/rgep/spsp-13.gz
                  > How about up to 10^14 Jason :-)

                  Wipe that smilie off your post, David.
                  Jason has all 2 SPSPs up to 4,503,586,330,870,201
                  Pinch is _such_ a 20th century resource...

                  Phil


                  =====
                  "The hottest places in Hell are reserved for those who, in
                  times of moral crisis, preserved their neutrality."
                  -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
                  to whom this has been incorrectly attributed ever since.

                  __________________________________________________
                  Do You Yahoo!?
                  Yahoo! Finance - Get real-time stock quotes
                  http://finance.yahoo.com
                • djbroadhurst
                  ... But the smilie was written _after_ studying http://217.35.81.229/spp.html so what joke is on whom, Phil? David (whose humour[?] is known to be perverse)
                  Message 8 of 12 , Sep 2, 2002
                  • 0 Attachment
                    I wrote:
                    > How about up to 10^14 Jason :-)
                    Phil quipped:
                    > Wipe that smilie off your post, David.
                    But the smilie was written _after_ studying
                    http://217.35.81.229/spp.html
                    so what joke is on whom, Phil?
                    David (whose humour[?] is known to be perverse)
                  • Phil Carmody
                    ... I ve never liked slapstick. Phil ===== The hottest places in Hell are reserved for those who, in times of moral crisis, preserved their neutrality. --
                    Message 9 of 12 , Sep 2, 2002
                    • 0 Attachment
                      --- djbroadhurst <d.broadhurst@...> wrote:
                      > I wrote:
                      > > How about up to 10^14 Jason :-)
                      > Phil quipped:
                      > > Wipe that smilie off your post, David.
                      > But the smilie was written _after_ studying
                      > http://217.35.81.229/spp.html
                      > so what joke is on whom, Phil?
                      > David (whose humour[?] is known to be perverse)


                      I've never liked slapstick.

                      Phil


                      =====
                      "The hottest places in Hell are reserved for those who, in
                      times of moral crisis, preserved their neutrality."
                      -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
                      to whom this has been incorrectly attributed ever since.

                      __________________________________________________
                      Do You Yahoo!?
                      Yahoo! Finance - Get real-time stock quotes
                      http://finance.yahoo.com
                    • Jason Moxham
                      ... This is what my current code is based on http://www.chalcedon.demon.co.uk/publish.html#41 Not read this yet , but it looks good
                      Message 10 of 12 , Sep 2, 2002
                      • 0 Attachment
                        On Monday 02 Sep 2002 7:49 am, Leonid Durman wrote:
                        > Hello all,
                        >
                        > Jason wrote:
                        > >for composite bases remember to check gcd(n,base)=1
                        > >bases
                        > >2 & 1226150 and n<38,210323 then n is prime
                        > >2 & 305185 and n<72,498253 and sqrt condition then n is prime
                        > >2 & 1121 & 6165 and n<20689,557337
                        > >2 & 463 & 735 & 849 and n<5,486664,348901 then n is prime
                        >
                        > It still best practical results.
                        > I have spent only hour for search. But at the large expenditures of time
                        > and resources it is possible to discover the best values.
                        > Excellent work.
                        >
                        > >for finding SPRP's for a fixed set of bases it is best NOT to use any
                        >
                        > powering
                        >
                        > >at all , I can dig out some referances if your interested , they use a
                        > >backtracking search .
                        >
                        > Yes, certainly. I am interested in any information which can to help,
                        > and I plan to create the high-performance code on an assembler.
                        > I would be interested to discover the best outcomes for values n<2^64. The
                        > sieve here is already less effective, a lot of memory permanently requires
                        > even if to optimize. And for practical researches with prime, SPRP test
                        > would be useful.


                        This is what my current code is based on
                        http://www.chalcedon.demon.co.uk/publish.html#41

                        Not read this yet , but it looks good
                        http://www.bell-labs.com/user/bleichen/diss/thesis.html


                        Jason


                        >
                        > Regards
                        >
                        > Leonid Durman
                      • Jason Moxham
                        ... Well not quite , they have yet to be verifyed 4.5e15=4,503,586,330,870,201=2^52 do have nearly all up to 2^56=7.2e16 , again not verified , missing the
                        Message 11 of 12 , Sep 2, 2002
                        • 0 Attachment
                          On Monday 02 Sep 2002 11:07 am, Phil Carmody wrote:
                          > --- djbroadhurst <d.broadhurst@...> wrote:
                          > > I see that Jason used 2 & x & y ...
                          > > That makes the problem rather easy up to
                          > > n=10^13, since one can pinch the file
                          > > http://www.chalcedon.demon.co.uk/rgep/spsp-13.gz
                          > > How about up to 10^14 Jason :-)
                          >
                          > Wipe that smilie off your post, David.
                          > Jason has all 2 SPSPs up to 4,503,586,330,870,201

                          Well not quite , they have yet to be verifyed
                          4.5e15=4,503,586,330,870,201=2^52

                          do have nearly all up to 2^56=7.2e16 , again not verified , missing the
                          squares , and split up up into many inconvient files...

                          > Pinch is _such_ a 20th century resource...

                          I glad to offer 21st century resources , note: coming soon 22nd century
                          resources and more....

                          jason

                          >
                          > Phil
                          >
                          >
                          > =====
                          > "The hottest places in Hell are reserved for those who, in
                          > times of moral crisis, preserved their neutrality."
                          > -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
                          > to whom this has been incorrectly attributed ever since.
                          >
                          > __________________________________________________
                          > Do You Yahoo!?
                          > Yahoo! Finance - Get real-time stock quotes
                          > http://finance.yahoo.com
                          >
                          >
                          > Unsubscribe by an email to: primenumbers-unsubscribe@egroups.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.