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

p-SPRP

Expand Messages
  • Leonid Durman
    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
    Message 1 of 12 , Sep 1, 2002
    • 0 Attachment
      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.


      Leonid Durman
    • 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 2 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 3 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 4 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 5 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 6 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 7 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 8 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 9 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 10 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 11 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 12 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.