Gratuitous factors thread - Page 3

Batalov · 2008-07-18, 16:37

Fresh from the oven. Very gratuitous:

(4·10^207-1)/3
= 13333.......3333 <207 threes>
= 227 · C205
= 227 · p100 · p106

p100 = 3999406295062729501331514001724671368377647689512510156551098073080765712556308639257272683646862107
p106 = 1468646766913267291096484238457962531138809604380942950365724174756132537097046980347507927618050634373797

Sergey

FactorEyes · 2008-07-18, 23:13

Quote:

Originally Posted by Batalov

p100 = 3999406295062729501331514001724671368377647689512510156551098073080765712556308639257272683646862107
p106 = 1468646766913267291096484238457962531138809604380942950365724174756132537097046980347507927618050634373797

Sergey

That's a pair of monster factors. Impressive!

Batalov · 2008-07-18, 23:47

Thank you. (I did all ecm up to the t50, but then - one can never be prepared for such a great split.)

My thanks go to Jasonp for the msieve (need I say more!) and to Greg for the fantastically effective sievers. This could have been a month job, but with Greg's sievers I was able to squeeze it into the 2,5-day weekend on 8-cpu's ...and then a 3,5-day Lanczos.

This is of course within the framework of Makoto Kamada's Factorizations of near-repdigit numbers

You're right, the c200's are no longer what they used to be.

Sergey

schickel · 2008-08-07, 06:02

Continuing in the spirit of this thread, here's a factorization that came up in my factoring. I'm doing work on aliquot sequences and while factoring a number in the sequence starting from 483570 I ran into a c109 that had a very nice split:

Code:

N=3916544839567831037197929061130658865990153512796321700002919410571148541456293739142265233087865070538878483
  ( 109 digits)
Divisors found:
 r1=1195853321473814365126729514302766586119987697269752141 (pp55)
 r2=3275104704932319522075280744447318143325990375356349663 (pp55)

First time I've had a 50/50 split in the factoring I've done....

nuggetprime · 2008-08-21, 19:02

Question: is a p51 by ECM after about 560 curves at B1=11M lucky?

Code:

GMP-ECM 6.2.1 [powered by GMP 4.2.2] [ECM]
Input number is 10594028369831114716682888330845541566105401124620505895213725128397891350870967330967394277735211887867089454105665163 (119 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=861666340
Step 1 took 46698ms
Step 2 took 25614ms
********** Factor found in step 2: 495436223298434385356722609135189152207142936793249
Found probable prime factor of 51 digits: 495436223298434385356722609135189152207142936793249
Probable prime cofactor 21383233343940664218943433891745463379743409952464040968535330972587 has 68 digits

--nugget

xilman · 2008-08-22, 08:08

Quote:

Originally Posted by nuggetprime

Question: is a p51 by ECM after about 560 curves at B1=11M lucky?

Code:

GMP-ECM 6.2.1 [powered by GMP 4.2.2] [ECM]
Input number is 10594028369831114716682888330845541566105401124620505895213725128397891350870967330967394277735211887867089454105665163 (119 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=861666340
Step 1 took 46698ms
Step 2 took 25614ms
********** Factor found in step 2: 495436223298434385356722609135189152207142936793249
Found probable prime factor of 51 digits: 495436223298434385356722609135189152207142936793249
Probable prime cofactor 21383233343940664218943433891745463379743409952464040968535330972587 has 68 digits

--nugget

Fairly lucky, yes. What's the integer? Could it have been done more quickly by SNFS?

Paul

nuggetprime · 2008-08-22, 10:28

The integer is the cofactor of (4·10^163+17)/3. I think snfs would have taken a bit longer on my machine.

--nugget.

Batalov · 2008-08-22, 20:08

Quote:

Originally Posted by nuggetprime

The integer is the cofactor of (4·10^163+17)/3. I think snfs would have taken a bit longer on my machine.

--nugget.

Well, it's really outside the 2/7 rule to ECM so deep, and it would have only taken you 2-3 days on any computer to SNFS it. The 560 curves already took 11 hours (I took your own timings, Step 1+2 * 560), and given that that was definitely lucky - if you ran for the full 11e6 ECM and wouldn't have found the factor (in about 2 days) - you would have been better off (by that same time in a parallel universe) with an almost finished SNFS.
But that's just my 2 cents, I may be wrong. --S

nuggetprime · 2008-08-22, 20:22

@Batalov: I maybe forgot to mention that I've used a quad-core machine(Q6600) with all for cores ECMing. So it took just about 11/4=~3hrs. Anyway, I didn't know of the 2/7 rule and Snfs/Gnfs might have been more efficient(using all cores,optimized 64-bit siever).

henryzz · 2008-08-22, 21:37

i think the 2/7 rule applies to optimal cpu selection
as far as i am aware intels are worse than amds for nfs but amds are worse for llr than intels
i dont know if there is anything like that with ecm

Batalov · 2008-08-24, 00:37

I am well known as a politically incorrect person im my circles. (hopefully not here ...yet).

But the following might offend some people, as well as also sound bitter (towards any record-holders), which it isn't. When I am listening to other people, I hear when the are helping me by criticizing me. Even if it is insulting in form. That's one lesson I think I was happy to acquire from life - people are helping me by criticizing me or my work. They are not helping me by keeping silence (or laughing behind my back).

So here goes.

Some of the ECM and/or QS records are in existence only because they were the wrong method to use. In 2008, if one spends six months for a QS on a 120-digit number, yeah, that's a record size for QS in some communities. But it's a wrong method! They could have been done with the number in 2 days with GNFS. Same here. If one doesn't get past these 2/7 (of digit size or for GNFS), 2/9 (of SNFS complexity for SNFS) rules early enough in their learning process, they may well get amazing fits of ECM luck but will the get to snfs-230 or gnfs-156 or whatever... No, their computers will be loaded with tons of ECM for years... It is a lottery as opposed to a deterministic, if boring (and seemingly long) process. Listen, I am guilty of the same! ...don't reach for your revolver. I got into P.Z.'s top 50 ECM table by luck leaving the ECM on a 143-digit number overnight with B1=110m and got a 56-digit factor on a 82-nd curve or something like that... I had no intention (and or resources) to finish a 110m ECM run - I simply got lucky. Did it for just one night before doing GNFS-143, which I was not ready for back then.

Looking back, was there any sense in running B1=110m curves on a 143-digit number? Nope. Could have never finished. Just got lucky. This is also the only XYYXF number in the ECM record tables, unless it is gone (it was 48th at arrival). Most importantly, I learned absolutely nothing by finding that factor, while by doing a competent GNFS I could have gotten ready to bigger jobs back then.

Ok, just look for good ideas in what I just wrote, not for hidden insults. There are none! (At least none intended.)

Peace! --Serge

2008-07-18, 16:37	#23
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 89×113 Posts	Fresh from the oven. Very gratuitous: (4·10^207-1)/3 = 13333.......3333 <207 threes> = 227 · C205 = 227 · p100 · p106 p100 = 3999406295062729501331514001724671368377647689512510156551098073080765712556308639257272683646862107 p106 = 1468646766913267291096484238457962531138809604380942950365724174756132537097046980347507927618050634373797 Sergey Last fiddled with by Batalov on 2008-07-18 at 16:41

2008-08-07, 06:02	#26
schickel "Frank <^>" Dec 2004 CDP Janesville 2·1,061 Posts	Continuing in the spirit of this thread, here's a factorization that came up in my factoring. I'm doing work on aliquot sequences and while factoring a number in the sequence starting from 483570 I ran into a c109 that had a very nice split: Code: N=3916544839567831037197929061130658865990153512796321700002919410571148541456293739142265233087865070538878483 ( 109 digits) Divisors found: r1=1195853321473814365126729514302766586119987697269752141 (pp55) r2=3275104704932319522075280744447318143325990375356349663 (pp55) First time I've had a 50/50 split in the factoring I've done....

2008-08-22, 10:28	#29
nuggetprime Mar 2007 Austria 456₈ Posts	The integer is the cofactor of (4·10^163+17)/3. I think snfs would have taken a bit longer on my machine. --nugget. Last fiddled with by nuggetprime on 2008-08-22 at 10:53

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Gratuitous OPN factors	wblipp	Factoring	463	2019-05-30 07:19
Ungracious Factors Thread	FactorEyes	Factoring	2	2011-04-09 05:45
Missing factors at the 'Known Factors' page	MatWur-S530113	PrimeNet	11	2009-01-21 19:08
JasonG's gratuitous C++ thread	jasong	Programming	16	2006-11-07 01:03
Gratuitous hardware-related banana thread	GP2	Hardware	7	2003-11-24 06:13

2008-07-18, 23:47	#25
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 89·113 Posts	Thank you. (I did all ecm up to the t50, but then - one can never be prepared for such a great split.) My thanks go to Jasonp for the msieve (need I say more!) and to Greg for the fantastically effective sievers. This could have been a month job, but with Greg's sievers I was able to squeeze it into the 2,5-day weekend on 8-cpu's ...and then a 3,5-day Lanczos. This is of course within the framework of Makoto Kamada's Factorizations of near-repdigit numbers You're right, the c200's are no longer what they used to be. Sergey

2008-08-22, 20:22	#31
nuggetprime Mar 2007 Austria 2×151 Posts	@Batalov: I maybe forgot to mention that I've used a quad-core machine(Q6600) with all for cores ECMing. So it took just about 11/4=~3hrs. Anyway, I didn't know of the 2/7 rule and Snfs/Gnfs might have been more efficient(using all cores,optimized 64-bit siever).

2008-08-22, 21:37	#32
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 178F₁₆ Posts	i think the 2/7 rule applies to optimal cpu selection as far as i am aware intels are worse than amds for nfs but amds are worse for llr than intels i dont know if there is anything like that with ecm

2008-08-24, 00:37	#33
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 89·113 Posts	I am well known as a politically incorrect person im my circles. (hopefully not here ...yet). But the following might offend some people, as well as also sound bitter (towards any record-holders), which it isn't. When I am listening to other people, I hear when the are helping me by criticizing me. Even if it is insulting in form. That's one lesson I think I was happy to acquire from life - people are helping me by criticizing me or my work. They are not helping me by keeping silence (or laughing behind my back). So here goes. Some of the ECM and/or QS records are in existence only because they were the wrong method to use. In 2008, if one spends six months for a QS on a 120-digit number, yeah, that's a record size for QS in some communities. But it's a wrong method! They could have been done with the number in 2 days with GNFS. Same here. If one doesn't get past these 2/7 (of digit size or for GNFS), 2/9 (of SNFS complexity for SNFS) rules early enough in their learning process, they may well get amazing fits of ECM luck but will the get to snfs-230 or gnfs-156 or whatever... No, their computers will be loaded with tons of ECM for years... It is a lottery as opposed to a deterministic, if boring (and seemingly long) process. Listen, I am guilty of the same! ...don't reach for your revolver. I got into P.Z.'s top 50 ECM table by luck leaving the ECM on a 143-digit number overnight with B1=110m and got a 56-digit factor on a 82-nd curve or something like that... I had no intention (and or resources) to finish a 110m ECM run - I simply got lucky. Did it for just one night before doing GNFS-143, which I was not ready for back then. Looking back, was there any sense in running B1=110m curves on a 143-digit number? Nope. Could have never finished. Just got lucky. This is also the only XYYXF number in the ECM record tables, unless it is gone (it was 48th at arrival). Most importantly, I learned absolutely nothing by finding that factor, while by doing a competent GNFS I could have gotten ready to bigger jobs back then. Ok, just look for good ideas in what I just wrote, not for hidden insults. There are none! (At least none intended.) Peace! --Serge