...merely a question about ECM world record? - Page 3

DukeBG · 2019-03-22, 19:23

it has.
[offtop]splitting all the algebraic numbers for 2^n-1 is part of the project i'm doing. it's at about n=1.35M right now. The 2^n+1 forms are caught up with all the known (i.e. in fdb for M(2n)) factors at about 180K-200K. The 2^(2n-1)±2^n+1 are on par with the M(8n-4) they are part of. Catching up the 2^n+1 is one of the next steps.[/offtop]

Dr Sardonicus · 2019-03-23, 13:40

Quote:

Originally Posted by xilman

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

This should work fairly well. It has the merit of using only integer arithmetic.

The computation of cyclotomic factors using only integer arithmetic is a slight elaboration of this idea. It was one of several topics thoroughly discussed in the original thread Factor-finding algorithms (and software) devoted to 3^504206 + 1.

lukerichards · 2019-03-23, 14:18

Quote:

Originally Posted by Dr Sardonicus

This should work fairly well. It has the merit of using only integer arithmetic.

The computation of cyclotomic factors using only integer arithmetic is a slight elaboration of this idea. It was one of several topics thoroughly discussed in the original thread Factor-finding algorithms (and software) devoted to 3^504206 + 1.

Indeed, I was going to say thanks to xilman for the helpful response. Whilst I was aware of those approaches, it's always nice to have a response from someone providing useful advice. At the very least it will remain here for future record, if anyone else is looking for similar queries.

Dr Sardonicus · 2019-03-24, 13:54

There is one issue raised in this thread I would like to see resolved: I ask the OP to please post the C106 disclosed by ECM. It might be instructive to see whether its factors were already found by other methods.

To summarize the results of the original thread devoted to factoring N = 3^504206 + 1, Factor-finding algorithms (and software):

1) Algebraic factorization produces a number of prime factors; in particular, those dividing the cyclotomic factors corresponding to the smaller divisors of 504206. Some of these were listed in existing tables.

2) Trial division and ECM disclosed a few larger factors, up to about 30 decimal digits IIRC.

3) There remained a number of very large composite factors, which were clearly and repeatedly described as being far beyond the capabilities of current theory and technology to factor -- even partially, but sufficiently to provide a proof that N + 1 is prime. The OP was advised that, absent new theoretical tools, significant further progress in factoring N is unlikely.

I do apologize for my unnecessarily scornful tone in my "bad penny" post a few pages back.

NOTE: The OP has PM'd me, informing me that he has re-read the original thread on this topic. I for one find this a most encouraging development. I hope that, in future, I will be able to remember threads I have started on a particular topic, so I can re-read them before starting a new thread on the same topic, and so avoid asking questions that have, in effect, already been asked and answered.

lukerichards · 2019-03-24, 16:32

It wasn't intended to be a post on the same topic - it was intended to be a thread about ECM world records.

I'd like to just clarify my PM - re-reading it last night wasn't the first time in the past fortnight!

I will post the C103 (I know I said 106 earlier but I was counting by hand in a hurry!) but all of the factors thereof were known factors already on FactorDB.

lukerichards · 2019-03-25, 08:23

Quote:

Originally Posted by lukerichards

It wasn't intended to be a post on the same topic - it was intended to be a thread about ECM world records.

I'd like to just clarify my PM - re-reading it last night wasn't the first time in the past fortnight!

I will post the C103 (I know I said 106 earlier but I was counting by hand in a hurry!) but all of the factors thereof were known factors already on FactorDB.

http://factordb.com/index.php?query=...5478708738770+

Fully factored with previously known factors.

lukerichards · 2019-03-25, 20:32

Hi M344587487, there is another thread which I started to discuss the tone of debate. If it's okay with you, I'll reply to you there, so that this thread can actually be of more useful resource to those interested in ECM world records/

The irony is that those complaining about me complaining - and doing so by saying I'm not interested in an engaging discussion - are actually massively detracting from the engaging discussion about ECM.

Uncwilly · 2019-03-26, 16:32

All non-ECM posts moved to this thread: https://mersenneforum.org/showthread.php?t=24213

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sieving freakishly big MMs (was "World record" phone number?)	davieddy	Operazione Doppi Mersennes	282	2019-06-24 07:57
World record sized double-check?	Siegmund	PrimeNet	6	2016-05-09 22:39
World Record Factorial Prime Found	rogue	Lounge	8	2012-03-02 16:41
70 billion pixels Budapest (world record)	R. Gerbicz	Science & Technology	0	2010-07-28 01:50
Question about record prime using Elliptical Curve method	jasong	Factoring	0	2006-02-28 04:00

2019-03-22, 19:23	#23
DukeBG Mar 2018 81₁₆ Posts	it has. [offtop]splitting all the algebraic numbers for 2^n-1 is part of the project i'm doing. it's at about n=1.35M right now. The 2^n+1 forms are caught up with all the known (i.e. in fdb for M(2n)) factors at about 180K-200K. The 2^(2n-1)±2^n+1 are on par with the M(8n-4) they are part of. Catching up the 2^n+1 is one of the next steps.[/offtop]

2019-03-24, 13:54	#26
Dr Sardonicus Feb 2017 Nowhere 1001000100011₂ Posts	There is one issue raised in this thread I would like to see resolved: I ask the OP to please post the C106 disclosed by ECM. It might be instructive to see whether its factors were already found by other methods. To summarize the results of the original thread devoted to factoring N = 3^504206 + 1, Factor-finding algorithms (and software): 1) Algebraic factorization produces a number of prime factors; in particular, those dividing the cyclotomic factors corresponding to the smaller divisors of 504206. Some of these were listed in existing tables. 2) Trial division and ECM disclosed a few larger factors, up to about 30 decimal digits IIRC. 3) There remained a number of very large composite factors, which were clearly and repeatedly described as being far beyond the capabilities of current theory and technology to factor -- even partially, but sufficiently to provide a proof that N + 1 is prime. The OP was advised that, absent new theoretical tools, significant further progress in factoring N is unlikely. I do apologize for my unnecessarily scornful tone in my "bad penny" post a few pages back. NOTE: The OP has PM'd me, informing me that he has re-read the original thread on this topic. I for one find this a most encouraging development. I hope that, in future, I will be able to remember threads I have started on a particular topic, so I can re-read them before starting a new thread on the same topic, and so avoid asking questions that have, in effect, already been asked and answered.

2019-03-24, 16:32	#27
lukerichards "Luke Richards" Jan 2018 Birmingham, UK 2⁵·3² Posts	It wasn't intended to be a post on the same topic - it was intended to be a thread about ECM world records. I'd like to just clarify my PM - re-reading it last night wasn't the first time in the past fortnight! I will post the C103 (I know I said 106 earlier but I was counting by hand in a hurry!) but all of the factors thereof were known factors already on FactorDB.

2019-03-25, 20:32	#29
lukerichards "Luke Richards" Jan 2018 Birmingham, UK 2⁵×3² Posts	Hi M344587487, there is another thread which I started to discuss the tone of debate. If it's okay with you, I'll reply to you there, so that this thread can actually be of more useful resource to those interested in ECM world records/ The irony is that those complaining about me complaining - and doing so by saying I'm not interested in an engaging discussion - are actually massively detracting from the engaging discussion about ECM.

2019-03-26, 16:32	#30
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 9,787 Posts	All non-ECM posts moved to this thread: https://mersenneforum.org/showthread.php?t=24213