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

Re: p-SPRP

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