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

Re: Crump penalty for too much factorization

Expand Messages
  • jkcmagic
    Thanks for sharing the comments and analysis David! Your point is valid, but may be an oversimplification. The probability you mention appears to be the chance
    Message 1 of 178 , Nov 12, 2009
      Thanks for sharing the comments and analysis David!

      Your point is valid, but may be an oversimplification.

      The probability you mention appears to be the chance a cofactor is prime and not the probability ECM will completely work under a given range. The FAQ at ElevenSmooth suggests the probability an L-digit number will completely factor after eliminating factors between 10^a and 10^b is:
      h(L,a,b)=sum(k=1,10,(exp(-log(b/a)) * (log(b/a)^k)/k!) * (exp(c)*b / (L-k*(b-a)/log(b/a))))

      Your logic still applies and the probability is in favor of the single 600-digit number completely factoring before two 300 digit ones given the same ECM curves but not that bad. And this doesn't take into account that GMP-ECM appears to run about 3 times faster on numbers of 300 digits than 600 digits.

      It's all academic I think anyway because the bottleneck appears to be SNFS at 200 digits (perhaps taking ~10 days each to finish on a quad core).

      - Joe Crump


      --- In primeform@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
      >
      >
      >
      > --- In primeform@yahoogroups.com,
      > "Jens Kruse Andersen" <jens.k.a@> wrote:
      >
      > > Congratulations on retaking the record for k=9.
      >
      > The k=10 record, by Joe and Michael (the brothers Crump)
      > is rather intriguing: it has too *much* algebraic factorization.
      >
      > In essence, they proceed from the observation that
      > x^2*(2*x^2-5)^2 - n is algebraically factorizable for
      > 8 of the 10 values n=0...9 :
      >
      > for(n=0,9,f=factor(x^2*(2*x^2-5)^2-n)[,1]~;if(#f>1,print([n,f])))
      > [0, [x, 2*x^2 - 5]]
      > [1, [2*x^3 - 5*x - 1, 2*x^3 - 5*x + 1]]
      > [2, [x^2 - 2, 2*x^2 - 4*x + 1, 2*x^2 + 4*x + 1]]
      > [3, [x^2 - 3, 2*x^2 - 2*x - 1, 2*x^2 + 2*x - 1]]
      > [4, [2*x^3 - 5*x - 2, 2*x^3 - 5*x + 2]]
      > [6, [2*x^2 - 3, 2*x^4 - 7*x^2 + 2]]
      > [8, [2*x^2 - 1, 2*x^4 - 9*x^2 + 8]]
      > [9, [x - 1, x + 1, 2*x^2 - 2*x - 3, 2*x^2 + 2*x - 3]]
      >
      > The factorizations for n=0,2,3,9 involves terms with
      > no more than 33% of the digits of the target.
      > So if you are prepared to run SNFS up to (say) 200
      > digits (with a suitable cubic for x) you can reach
      > 600 digit targets, in these cases, as they remark.
      >
      > The factorizations for n=6,8 are useful: they reduce
      > the digits in the GMP-ECM part of the work from 600
      > to 400 digits, for these two targets.
      >
      > But then comes the snag: the factorizations for n=1,4
      > are strongly counterproductive: each splits a 600-digit
      > target into a pair of 300-digit targets. It is clearly
      > much harder, on average, to achieve complete factorizations
      > of a pair of numbers of length L digits than for a single
      > number of length 2L. Suppose that you are prepared to
      > run ECM to a depth of d << L digits. Then the probability
      > of factorizing both parts, each with length L, is
      >
      > P_both = (exp(Euler)*d/L)^2
      >
      > while the probability of factorizing a target with
      > no algebraic factorization is
      >
      > P_single = exp(Euler)*d/(2*L)
      >
      > This hang-up happens twice, at n=1 and n=4.
      > Hence the "penalty" for too much algebraic factorization
      > is an *inefficiency* by a factor of roughly
      >
      > (P_single/P_both)^2 = (exp(-Euler)*L/(2*d))^2
      >
      > With, say, L=300 and d=30, this is a factor of about 8.
      >
      > So the challenge in polynomial selection is this:
      > to get 4 good multi-SNFS targets (here at n=0,2,3,9)
      > plus a pair of GMP-ECM easements (here at n=6,8)
      > without paying the (say) 8-fold penalty for a
      > pair of counterproductive factorizations (here at n=1,4).
      >
      > It's a neat puzzle, to which I have, as yet, no solution.
      >
      > In any case, I am staying, at present, with my
      > "25% or 100%" strategy, based on Prouhet-Tarry-Escott,
      > for 8 or 9 consecutive factorizations, as in
      >
      > http://users.cybercity.dk/~dsl522332/math/consecutive_factorizations.htm
      >
      > David (with thanks to Jens and Joe, for stimulus)
      >
    • djbroadhurst
      ... Yes. Moreover the proof is rather easy. Let C be a Carmicahel number and let p be its largest prime factor. Then p-1|C-1. and hence p-1|(C/p)-1. Thus p
      Message 178 of 178 , Feb 25, 2010
        --- In primeform@yahoogroups.com,
        Devaraj Kandadai <dkandadai@...> asked:

        > Are all Carmichael numbers " quadratically smooth"?

        Yes. Moreover the proof is rather easy.

        Let C be a Carmicahel number and let p
        be its largest prime factor. Then p-1|C-1.
        and hence p-1|(C/p)-1. Thus p < C/p,
        and C is quadratically smooth.

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