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

Re: [PrimeNumbers] p-SPRP

Expand Messages
  • 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 1 of 12 , Sep 2, 2002
      --- 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 2 of 12 , Sep 2, 2002
        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 3 of 12 , Sep 2, 2002
          --- 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 4 of 12 , Sep 2, 2002
            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 5 of 12 , Sep 2, 2002
              --- 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 6 of 12 , Sep 2, 2002
                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 7 of 12 , Sep 2, 2002
                  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.