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

Re: [PrimeNumbers] p-SPRP

Expand Messages
  • 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 1 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 2 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 3 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 4 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 5 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 6 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 7 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 8 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 9 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 10 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.