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

6-Carmichael record

Expand Messages
  • djbroadhurst
    I have found a 2066-digit 6-Carmichael number. As far as I know, the previous record was 827 digits by Chris Caldwell and Harvey Dubner. My algorithm has a
    Message 1 of 8 , Feb 28, 2002
    • 0 Attachment
      I have found a 2066-digit 6-Carmichael number.
      As far as I know, the previous record was 827
      digits by Chris Caldwell and Harvey Dubner.
      My algorithm has a time-cost scaling like
      digits^7, whereas the Caldwell-Dubner method
      is slower, scaling like digits^8.

      The prime factors are of the form

      p=24*m+1
      q=48*m+1
      r=72*m+1
      s=144*m+1
      t=288*m+1
      u=288*m*Q(m)/d+1

      where d is a proper divisor of the quartic

      Q(m) = (p*q*r*s*t-1)/(t-1)
      = 2*(5971968*m^4 + 518400*m^3 + 15264*m^2 + 191*m + 1)

      with discriminant D=-131*4889. The concrete solution has

      m=5^55*7*17*23*31*47*61*67*79*83*89*97*101*107*113*139*\
      149*151*167*179*227*251*269*307*311*317*331*349*p25*p87

      p25=8857830991926784681130749

      p87=58135625972960605667773529074721763464097\
      8604228948251312373613096541035977392154103019

      Note that m is fully factorized. Crucially, all primes up
      to 367 that are not in m appear in Q(m), thanks to
      algebraic number theory and the CRT. Thus there is a plethora
      of possible choices for d, with no less than 20 values
      d < 52000 that make u prime, namely those in the set

      {292,636,779,888,1824,4541,8159,8943,9909,11124,13416,
      13862,14391,16211,22591,29591,30914,44377,45799,51546}

      The largest 6-Carmichael number, with d=292, has 2066 digits
      and its largest prime factor, u, is titanic, with 1032 digits.

      In all 20 cases, the primality of u was proven by BLS,
      since u-1 was more than 37% factorized, thanks to a large
      number of small primes in m and Q(m), has well as the
      two ECM primes in m, p25 and p87, above, and the factors

      15053*9219467779*3936112849523*58820249374652939513*
      32711792972604332700617729

      found in Q(m) by using ECM up to the p30 level.

      The key to this construction is the use of algebraic number
      theory to separate [*] all the primes up to 367 into those
      for which the quartic Q(m) may have zero residue and those
      for which it may not. The latter are put by hand into m;
      the former appear in Q(m) thanks to a CRT constraint,
      which was implemented before quintuple sieving of
      p,q,r,s,t, with a bitmap ranging over a search space of
      half a billion integers, each of order 10^112, and each
      guaranteeing more than a million trial divisors d.
      Pfgw found that one of the sieved candidates gave 5 PrPs,
      ECM factorized a c112 in the resultant CRT solution
      for m into p25*p87 and pulled 5 primes out of Q(m),
      allowing Pfgw to prove the primality of all 6 Carmichael
      factors for each of the 20 values of d above.

      Finally I remark that Konyagin-Pomerance provable
      prime factors of a k-Carmichael number N, with
      k=5,6,7, are obtainable by a generalization of my
      method that apportions primes, distinguished by an
      algebraic number field, with relative contributions
      (23-3*k):(3*k-13) to m and a polynomial Q(m) of degree
      (k-2). Here, with k=6, one puts a hundred digits
      of each into m and Q(m) and is left with another
      hundred to find by ECM, in order to achieve the
      KP threshold of 30% for u=O(N^(1/2))=O(10^1000).
      With k=5, the balance shifts to 4:1 in favour of m,
      while with k=6 it is the other way round, 1:4 in favour
      of Q(m). In each of the cases k=5,6,7, one is left to
      factorize a composite of order

      log(N)^(k-1)*N^((3*k-13)/(20*k-20))

      resulting from the large integer in m that generates small
      primes in Q(m), via the CRT. Here, with k=6, the composite
      was of size log(N)^5*N*(1/20), i.e. the c112=p25*p87
      in m that gave N=O(10^2000). At k=5, a factorization
      of a composite of size log(N)^4*N^(1/40) is needed;
      at k=7 the cost is higher: log(N)^6*N^(1/15). For
      k<5, BLS provability is automatic, without any ECM work,
      and for k>7 there is no way of achieving even
      KP-provability by working with ECM solely on the more
      tractable m.

      I recently found a 4000-digit 5-Carmichael number,
      thus quadrupling the Caldwell-Dubner record, which
      stood at 1000 digits. For this I used Primo for the
      largest factor, with 2000 digits. If one wished to
      find a 5-Carmichael number with 1+1+1+1+4=8 thousand
      digits, one would not want to invoke Primo at 4
      thousand digits. The above considerations suggest that
      it might be better to try to crack a 220-digit
      composite with ECM and then use KP. Here, the random
      nature of factorization actually helps: while ECM is
      thrashing at a c220 one can be generating another by CRT,
      in the hope that it will be easier to crack. ECPP
      on the other hand is more deterministic: the price
      of a 4k digit Primo proof does not vary as wildly as
      does the price of factorizing a c220 of unknown
      constitution. It was this consideration that lead
      to the present work at k=6, where Primo at 1k digits
      takes merely an hour, so that nothing would have
      lost had the ECM proof-route not paid off even faster
      than that.

      David Broadhurst

      [*] Note that when working with quartics, the Jacobi symbol is
      of no help; instead I used the "polrootsmod" routine of Pari-GP.
    • thefatphil
      ... It appears that the way to succeed with a (N+1)-member problem is to take an off-the shelf N-member pattern ({1,2,3,6,12} in this case) and look for
      Message 2 of 8 , Feb 28, 2002
      • 0 Attachment
        --- In primenumbers@y..., "djbroadhurst" <d.broadhurst@o...> wrote:
        > I have found a 2066-digit 6-Carmichael number.
        > As far as I know, the previous record was 827
        > digits by Chris Caldwell and Harvey Dubner.
        > My algorithm has a time-cost scaling like
        > digits^7, whereas the Caldwell-Dubner method
        > is slower, scaling like digits^8.
        >
        > The prime factors are of the form
        >
        > p=24*m+1
        > q=48*m+1
        > r=72*m+1
        > s=144*m+1
        > t=288*m+1
        > u=288*m*Q(m)/d+1

        It appears that the way to succeed with a (N+1)-member problem is to
        take an off-the shelf N-member pattern ({1,2,3,6,12} in this case) and
        look for single-member extensions.

        The above all makes sense to me.

        However...

        > where d is a proper divisor of the quartic
        >
        > Q(m) = (p*q*r*s*t-1)/(t-1)
        > = 2*(5971968*m^4 + 518400*m^3 + 15264*m^2 + 191*m + 1)
        >
        > with discriminant D=-131*4889. The concrete solution has

        ... discriminants? Wassat? This all goes to show that there's more to
        prime finding than chucking a sieving job at a machine, and just
        PRPing the output. No, actually I do get it. The explanation that
        followed was sublime.

        _Hearty_ congratulations.

        Now you've given pretty much full disclosure of the mathematics behind
        the attack, could you enlighten us what software and languages you
        used for the different stages.
        I'm assuming:
        1) Finding the correct 'parametrisation' was Pari-GP.
        2) Sieving was hand-written in Fortran. (1 byte per candidate, on your
        512MB alpha, I'd bet).
        3) PFGW takes you home.

        > [*] Note that when working with quartics, the Jacobi symbol is
        > of no help; instead I used the "polrootsmod" routine of Pari-GP.

        Hahah! What's wrong with something like:

        for $p (@smallprimes)
        {
        my %hit=(); for(0..$p-1) { $hit{fn($i)%$p}=1; } print keys %hit;
        }
        :-)


        Phil
      • djbroadhurst
        ... Just so. But the sieve is tricky. For each prime that you use to cross out 5 long series of bits you need to do number theory, to work out where each of
        Message 3 of 8 , Feb 28, 2002
        • 0 Attachment
          Phil:
          > I'm assuming:
          > 1) Finding the correct 'parametrisation' was Pari-GP.
          > 2) Sieving was hand-written in Fortran.
          > 3) PFGW takes you home.
          Just so. But the sieve is tricky.
          For each prime that you use to cross out 5
          long series of bits you need to do number theory,
          to work out where each of the 5 series starts.
          And Fortran is not very good at number theory:-)
          So I got Pari to output, line by line (no internal storage)
          a 300MB file of fancy modular data for the
          primes up 10^8 which the Fortran siever read in,
          line by line (no internal storage) and just did the crossing out.
          I cannot easily sieve deeper than 10^8, because of disk
          space limitations, which is a shame.
          If I could go to 10^9 then Pfgw would be
          (9/8)^5=1.8 times faster.
          But then I should not grumble, because what I was doing is
          equivalent to writing a NewPgen that has
          its "k" going up to 10^112, in giant CRT determined steps,
          instead of up to 2^31 in steps of 1 or 2.
          One day, this will get on the Jobling joblist, but not
          real soon, I guess:-)
          David
        • djbroadhurst
          ... Nowt wrong with that. But it get s a bit tricky with large powers of small primes, which I use to achieve balancing. I think that the small factors of
          Message 4 of 8 , Feb 28, 2002
          • 0 Attachment
            Phil:

            > for $p (@smallprimes)
            > {
            > my %hit=(); for(0..$p-1) { $hit{fn($i)%$p}=1; } print keys %hit;
            > }

            Nowt wrong with that. But it get's a bit tricky
            with large powers of small primes, which I use to
            achieve balancing. I think that the small factors of
            p*q*r*s*t-1 (divided, by number, theory between m and Q(m))
            were

            2^17*3^10*5^54*11*13*19*29*103*367#

            but I'm dashed if I can recall where that extra 103 came
            from. I think it must have been something that my CRT
            did not aim for but got by accident.

            By the way, the number theory of Q(m), in this case,
            is equivalent to that of

            ? print(nfinit(5971968*m^4+518400*m^3+15264*m^2+191*m+1).pol)
            *** Warning: non-monic polynomial. Result of the form [nf,c].
            m^4 - 2*m^3 - 8*m^2 - 53*m - 24

            which is typical of the way that Henri cleans things up.

            David
          • Phil Carmody
            ... Homer: [sings] Call Mr. Sieve, that s my name! That name again is Mr. Sieve. ... Hmm, you re an Alpha male, aren t you? Guess what my alpha s been doing
            Message 5 of 8 , Feb 28, 2002
            • 0 Attachment
              --- djbroadhurst <d.broadhurst@...> wrote:
              > Phil:
              > > I'm assuming:
              > > 1) Finding the correct 'parametrisation' was Pari-GP.
              > > 2) Sieving was hand-written in Fortran.
              > > 3) PFGW takes you home.
              > Just so. But the sieve is tricky.

              Homer: [sings] "Call Mr. Sieve, that's my name! That name
              again is Mr. Sieve."

              > I cannot easily sieve deeper than 10^8, because of disk
              > space limitations, which is a shame.
              > If I could go to 10^9 then Pfgw would be
              > (9/8)^5=1.8 times faster.
              > But then I should not grumble, because what I was doing is
              > equivalent to writing a NewPgen that has
              > its "k" going up to 10^112, in giant CRT determined steps,
              > instead of up to 2^31 in steps of 1 or 2.
              > One day, this will get on the Jobling joblist, but not
              > real soon, I guess:-)

              Hmm, you're an Alpha male, aren't you?
              Guess what my alpha's been doing for the last...
              <<<
              t=37552.181720 p=7513047041 c=971461 cr=-2.279847
              >>>
              ...10 hours. Yup - sieving up to 7.5G, getting my candidates to less
              than 1M, and still working at >2 candidates per second.

              Pure wholesome C++ with GMP doing the tricky parts (XGCD etc.).
              The GMP stuff needs to be binned certainly - but that can be
              preparation for the _next_ task, I've already worked out how to
              parallelise 6 primes simultaniously on the 7-year old 21164, and
              maybe up to _14_ primes on a 21264.

              When optimised, your kind of search only need not run at much less
              than half the speed of a primorial newpgen, as it requires 2 large
              reductions rather than one. I think there may be a 1 reduction
              method, but it looked much messier. The 10^112-like terms tend to
              mess things up rather.

              Now all you have to do is guess what I'm aiming for!
              ;-)

              Phil

              =====
              --
              .sig selecter broken, please ignore.

              __________________________________________________
              Do You Yahoo!?
              Yahoo! Greetings - Send FREE e-cards for every occasion!
              http://greetings.yahoo.com
            • djbroadhurst
              I started with a silly idea. In all cases from 4-Carmichael (quadratic field) to 6-Carmichael (quartic), 2 and 5 live on different sides of the great divide.
              Message 6 of 8 , Feb 28, 2002
              • 0 Attachment
                I started with a silly idea. In all cases from 4-Carmichael
                (quadratic field) to 6-Carmichael (quartic), 2 and
                5 live on different sides of the great divide.
                (for 4-Carmichael is simply that Jacobi(-23,5)=-1)

                So I had the idea to split 200 digts each way as follows

                10^100=2^333 in Q(m)
                10^100=5^143 in m

                (a sort of hands and fingers job-:)

                Fortunately, I realized that would give me only
                334 hits at a prime-generating divisor of Q(m).

                As you said: building a small model first sure helps...

                David
              • djbroadhurst
                OK, Phil, your turn to teach, please. ... Please, sir, how does NewPgen economically solve k=1/(-m#) mod p No problem working out -m# mod p, but then how do
                Message 7 of 8 , Mar 1 12:55 PM
                • 0 Attachment
                  OK, Phil, your turn to teach, please.
                  > half the speed of a primorial newpgen
                  Please, sir, how does NewPgen economically solve
                  k=1/(-m#) mod p
                  No problem working out -m# mod p,
                  but then how do you best find the modular inverse
                  Is it just the obvious O(log(p)) Euclid job?
                  In which case I can do it in Fortran, with line-numbering :-)
                  David
                • Phil Carmody
                  ... Yuppers. Fortran schmortran - do it in URL or Turing Machine. You were aware that Fortran is as capable as a Turing machine, weren t you ;-) Phil ===== --
                  Message 8 of 8 , Mar 1 4:51 PM
                  • 0 Attachment
                    --- djbroadhurst <d.broadhurst@...> wrote:
                    > OK, Phil, your turn to teach, please.
                    > > half the speed of a primorial newpgen
                    > Please, sir, how does NewPgen economically solve
                    > k=1/(-m#) mod p
                    > No problem working out -m# mod p,
                    > but then how do you best find the modular inverse
                    > Is it just the obvious O(log(p)) Euclid job?
                    > In which case I can do it in Fortran, with line-numbering :-)

                    Yuppers. Fortran schmortran - do it in URL or Turing Machine. You
                    were aware that Fortran is as capable as a Turing machine, weren't
                    you ;-)

                    Phil




                    =====
                    --
                    .sig selecter broken, please ignore.

                    __________________________________________________
                    Do You Yahoo!?
                    Yahoo! Sports - sign up for Fantasy Baseball
                    http://sports.yahoo.com
                  Your message has been successfully submitted and would be delivered to recipients shortly.