Sorry, an error occurred while loading the content.

## Re: Crump penalty for too much factorization

Expand Messages
• 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)
>
• ... 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.