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

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

Expand Messages
  • Phil Carmody
    ... A selfridge is the cost of a single (S)PRP test - i.e. a modular exponentiation modulo p with Omega(lg(p)) mulmod steps. Optimising the squarings into
    Message 1 of 37 , Mar 12, 2013
    • 0 Attachment
      --- On Tue, 3/12/13, WarrenS <warren.wds@...> wrote:

      > From: WarrenS <warren.wds@...>
      > Subject: [PrimeNumbers] Re: Infallible isprime(p) routine for 0<p<2^32
      > To: primenumbers@yahoogroups.com
      > Date: Tuesday, March 12, 2013, 3:48 AM
      >
      > > Blowing my own trumpet: While no one knows a
      > counterexample to the 1+2 selfridge BPSW, I have yet to find
      > a counterexample > 10^13 to:
      > >
      > > (L+2)^(n+1)==2*x+5 (mod n, L^2-x*L+1), minimal x>=0
      > >
      > > which can be done in 2 selfridge. Coupled with a 2-sprp
      > test it makes a 1+2 selfridge test, but with the power of 4
      > selfridge; it has an implicit, free base 2*x+5 prp test.
      > This makes it stronger than BPSW!
      >
      > --you've got to stop describing this stuff in mysterious
      > language nobody but you can understand.  Well, maybe
      > somebody follows, but I at any rate, have no idea what you
      > are saying nor why this "can be done in 2 selfridge."
      >
      > If you are right, it is worth stating it in a comprehensible
      > manner...

      A "selfridge" is the cost of a single (S)PRP test - i.e. a modular exponentiation modulo p with Omega(lg(p)) mulmod steps.

      Optimising the squarings into explicit sqmods rather than mulmods can sometimes be cheaper, and other optimisations ran reduce the cost of the mulmods that you need to do (e.g. your windowning can sometimes help, but sometimes the mulmods can be free, so your windowing is of no use there). However, these are changes only change the multiplicative constant by a small factor.

      If you perform the O(1) transformation documented in Crandall & Pomerance, a Lucas test can be performed in 2 selfridges. If you don't, depending on how messy the quadratic is, it can cost 3, 4 or more. There's the same variability in possible optimisations (e.g. windowing, explicit sqmods, free mulmods) available for this procedure that's available for the PRP test, and in the same kinds of scenarios, so the small changes in multiplicative constant don't affect the ratio between the two costs. So we say a Lucas costs 2 Selfridges.

      The claim that the Lucas tests contains a PRP test I have not verified. I'm sure David would be able to attack that far more efficiently than I would.

      Phil
      --
      () 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:
        http://homes.cerias.purdue.edu/~ssw/cun/page125
        And, you can see who is factoring which Cunningham number here:
        http://homes.cerias.purdue.edu/~ssw/cun/who
        And more importantly, you can find all known*1 factors for all important*2
        numbers in the online factor database here:
        factordb.com
        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.