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

Re: [PrimeNumbers] Re: Infallible isprime(p) routine for 0<2^32

Expand Messages
  • Phil Carmody
    ... Good to know that these hashes can work. It s a useful insight that I d not thought of. ... I ve not programmed for an intel architecture machine for half
    Message 1 of 37 , Mar 11, 2013
    • 0 Attachment
      --- On Tue, 3/12/13, David Cleaver <wraithx@...> wrote:
      > You can see a good post about using a single spsp test to prove any number <
      > 2^32 prime/composite over on the mersenneforum:
      > http://www.mersenneforum.org/showthread.php?p=182647
      > In that post, he has a hash table of size 1024 that works on all numbers < 2^32.

      Good to know that these hashes can work. It's a useful insight that I'd not thought of.

      > Warren, I'm curious, would you time this code against yours
      > to see which one comes out faster?

      I've not programmed for an intel architecture machine for half a decade, but I'd be surprised if the mixed integer/floating point implementation wasn't the fastest mulmod.

      > Someone else was able to get n < 2^64 down to 4 spsp tests, (3 fixed, and one
      > into a hash).  I didn't see anyone reduce it to 3 spsp tests for n < 2^64.
      > Hopefully something like that will show up some day soon.

      Conditional on the Feitsma list being complete.

      I notice from the stats at:
      that large proportions of them are semiprimes. How many of them fall to N*issquaremod()+issquare() tests, which is nearly as cheap as trial division (on failure, success is a little more costly)? I've not got the list, I have no idea how many trivially factorised numbers can be found - I'm just brainstorming as nobody's mentioned this test recently ("our" DJB of course has used it in the past). Yes, I know it might sounds dumb to throw a crappy (no disrespect, Pierre) factorisation algorithm at a primality test, but these are numbers with a special form, perhaps that can be exploited.

      If 3 * SPSP tests is close (I don't know if it is), then the combination of a bit more pruning from issquare()s and the sqrt(-1) test I mentioned previously might just be enough to push it over the edge into doability. (As I've mentioned before, there's an equally simple cubert(-1) comparison test for p=3n+1 candidates.)

      But deep down, once you've transformed the Lucas sequence into the efficient form (see C&P), the BPSW test is still where it's at.

      () ASCII ribbon campaign () Hopeless ribbon campaign
      /\ against HTML mail /\ against gratuitous bloodshed

      [stolen with permission from Daniel B. Cristofani]
    • David Cleaver
      ... Apologies, my Pari/GP script-fu is definitely not on par with DJB s. I just wanted to provide a script so that people could plug and chug an r,p pair to
      Message 37 of 37 , Mar 14, 2013
      • 0 Attachment
        On 3/13/2013 5:47 AM, Phil Carmody wrote:
        > No I couldn't. That's so overly verbose and redundant it makes me twitch, I can
        > barely bring myself to repeat it!
        > "lift(Mod(p*s, lift(znorder(Mod(2,s))))) == 1" is just
        > "p*s % znorder(Mod(2,s)) == 1"
        > Having 3 exit conditions to the loop is overkill too.

        Apologies, my Pari/GP script-fu is definitely not on par with DJB's. I just
        wanted to provide a script so that people could plug and chug an r,p pair to see
        what psp's would be generated. Also, I didn't know that the % (mod) operator
        still worked in Pari. I thought everything had to be done with Mod(). Thanks
        for that insight.

        > The latter worries me a bit, as it might imply wasted effort. I'm trying to
        > picture how these duplicates arise. Given a n, the maximal prime factor p|s is
        > uniquely defined, and r as order_2(p) is uniquely defined. Therefore n can only
        > appear with pair (r,p)?

        And apologies here too, I mis-remembered a statement from his Category S page
        and mis-spoke by applying it to the Category E psp's.

        On 3/14/2013 11:02 AM, WarrenS wrote:
        > 2. Consulting the Cunningham project pages,
        > http://homes.cerias.purdue.edu/~ssw/cun/index.html
        > every Mersenne-form number 2^r - 1 now is fully factored if
        > r<929. Apparently the first two open cases are r=929 and 947
        > yielding 214 and 217 digit numbers to factor.

        An update here: M929 has been factored, and a group of people have already
        started factoring M947. You can find the factor for M929 here:
        And, you can see who is factoring which Cunningham number here:
        And more importantly, you can find all known*1 factors for all important*2
        numbers in the online factor database here:
        Once there, you can type in 2^929-1, and it will show you all the factors of
        that number and that it is Fully Factored (FF). Currently, you can type in
        2^947-1 and see that it is a CF, composite number, with factors known, but not
        yet fully factored.

        *1 = All known factors that have been stored into the factordb.
        *2 = All numbers that people are interested in and store in the factordb.

        Also, the factordb stores prime numbers too. Below 300 digits it will just
        prove the number prime, and above that it will accept Primo certificates and
        verify them locally.

        -David C.
      Your message has been successfully submitted and would be delivered to recipients shortly.