...merely a question about ECM world record?

[GP2]

Originally Posted by Dr Sardonicus

Just by way of practice, I did this with 2^5040 - 1. There weren't many composites left standing.

FactorDB uses color coding. Prime factors are in black text, composite factors are blue. So at a glance, 2^5040 − 1 has only one, 278-digit composite factor.

[Dr Sardonicus]

Originally Posted by GP2

FactorDB uses color coding. Prime factors are in black text, composite factors are blue. So at a glance, 2^5040 − 1 has only one, 278-digit composite factor.

Thanks for the link.

I pursued the "small arms fire" attack on 2^5040 - 1 just to see how far it got me. The result was, the only composite factors left standing were the entire cyclotomic factor PHI(5040,2) (347 digits) and a 168-digit cofactor of the cyclotomic factor PHI(2520,2).

(I had Pari-GP completely factor cyclotomic factors less than 10^80, and factor larger ones up to primelimit. This left five unchecked factors. One of them was prime, and two others were composite, but small enough that factor() cracked them quickly. And then there were two.

Time for the big guns! The C168 cofactor of PHI(2520, 2) has been completely factored. PHI(5040,2) has been whittled down from a C347 to a remaining C278 cofactor.

[DukeBG]

Friends, you don't need to dig that deep into this particular number, this was just an example of a "shattering world record" (according to the original post) being found in a few seconds. I've chosen 5040 because it's 7! and thus the number will have a ton of algebraic factors that'll consist of small divisors.

[lukerichards]

Originally Posted by DukeBG

this was just an example of a "shattering world record" (according to the original post)

For the record, the original post was asking questions, not making claims.

[Dr Sardonicus]

Originally Posted by lukerichards

For the record, the original post was asking questions, not making claims.

As already indicated, for the purpose of "record factors" found by ECM, only prime factors need apply.

Therefore, you want to divide out any small factors before trying ECM.

I don't know what 240,000 digit number you're looking at. If it is of a special form that admits algebraic factors, by all means use that.

I imagine some form of "trial division" can be used to eliminate really tiny factors (i.e. factors in precomputed tables of primes up to some small limit).

If the factors are restricted to be of a special linear form, this fact can be exploited to do trial factorization beyond computed tables of primes.

There are other methods (e.g. Pollard Rho) that might turn up small factors cheaply.

I don't know a reasonable limit L for "my number has no factors below L" as a criterion for when to resort to ECM.

[DukeBG]

Oh, I don't think lukerichards was doing some generic number and getting small composites bundled up into the big composite factor found. So they probably don't need this guidance.

It's just that sometimes during ECM (same goes for P-1/P+1 for that matter) you can find two prime factors of the target size with the same curve. That will result in a twice bigger than expected composite number. Or thrice if you're lucky (i.e. that 106 composite might have been tree factors at the same time in a -t35 search).

[Batalov]

It is clear which number he is factoring -- 3⁵⁰⁴²⁰⁶+1, see

Originally Posted by lukerichards

I'm now wondering again about factoring 3⁵⁰⁴²⁰⁶+1, having discovered last March that 3⁵⁰⁴²⁰⁶+2 is a PRP.

[xilman]

Originally Posted by Batalov

It is clear which number he is factoring -- 3⁵⁰⁴²⁰⁶+1

A cheap and cheerful way of approaching such numbers, which I've used many times in the past, is first to enumerate all factors of the exponent, here 504206. Sort them into numerical order and let's call the list d_i. As 504206 = 2*23*97*113, the list starts with 2, 23, 46, 97, 113, 194, 226 and ends with 252103. Start with N = 3⁵⁰⁴²⁰⁶+1. Then compute gcd(N, 3^(d_i) ± 1) in turn and use a light-weight factoring algorithm to find its small prime factors and a possible large composite. At each step, divide N by the GCD just found and repeat with d_i+1. You are left with a bunch of relatively small prime factors and a short list of relatively large composites. At this point, bring out the heavy artillery, including consulting the Factordb.

Certainly not the optimal approach but easy to implement. My apologies for teaching egg-sucking to grannies who already know all about algebraic factorization

[Dr Sardonicus]

Originally Posted by Batalov

It is clear which number he is factoring -- 3⁵⁰⁴²⁰⁶+1, see

[laughs] Oh, that one again! The first go-round was 11 months ago. The cyclotomic factorization and linear forms were gone through. The unlikelihood of factoring the number was explained.

It had another recent go-round, so this is the third iteration. Lazarus got to come back from the dead once. Jesus is said to be due a second coming. But a third? I'm at a loss as to what to call it. The "bad penny" number?

[GP2]

Would any of these techniques be applicable to larger numbers? Say, trying to find the remaining factors of 2^47684−1 or 2^47684+1

47684 = 2 × 2 × 7 × 13 × 131

If you could somehow make miraculous progress on these, there might be a path to an N−1 proof of primality of (2^95369+1) /3.

But I think the techniques you're discussing are applicable to much smaller exponents and smaller factors, am I right?

[xilman]

Originally Posted by GP2

Would any of these techniques be applicable to larger numbers? Say, trying to find the remaining factors of 2^47684−1 or 2^47684+1

47684 = 2 × 2 × 7 × 13 × 131

If you could somehow make miraculous progress on these, there might be a path to an N−1 proof of primality of (2^95369+1) /3.

But I think the techniques you're discussing are applicable to much smaller exponents and smaller factors, am I right?

The approach I outlined is applicable to all numbers of the form aⁿ±1.

I would be very surprised if the N you mention haven't already had algebraic factors removed.