mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Pascal's OPN roadblock files (https://www.mersenneforum.org/showthread.php?t=19066)

 chris2be8 2014-12-16 16:42

(934415109937^19-1)/2820811613729985828949629000988975589441958190342138660258526203414155026928 factors as: [code]
prp65 factor: 44927314708522649668507732891092773307491427412268919263422276559
prp88 factor: 2174566304094043214976563938797167396918461392552579181469199206213383589200521755246761
[/code]
Chris

 chris2be8 2014-12-16 21:27

10378063^37-1 won't need GNFS: [code]
********** Factor found in step 2: 3845026093604103084749876919164389056337667747957557187
Found probable prime factor of 55 digits: 3845026093604103084749876919164389056337667747957557187
Probable prime cofactor 39911889779792123684491618958738937200638179178631804242781492861855714086246269236139239946992447663 has 101 digits
[/code]
Chris

 chris2be8 2014-12-19 17:12

(480393499^23-1)/451957020657813395732158958213463532216698390966 is now finished: [code]
prp73 factor: 1237714544754336386081138023774642994715614063968169882159127990605725969
prp80 factor: 84921208424568043586451769556091088605641853147167457323882403321952821638139787
[/code] That's the last one from i_51_2000_101.txt that's in my range.

Chris

 RichD 2015-01-18 05:51

I noticed an update to the Most Wanted Road Block file was posted 12/2014. I completed about a dozen easy ones but the file has been gone for a couple days. Does anyone know if a new update is in the works?

Normally posted here: [url]http://www2.lirmm.fr/~ochem/opn/mwrb2000.txt[/url]

 RichD 2015-02-03 20:12

It's back, with numbers starting as little as C133.

 chris2be8 2015-02-07 17:01

I'll start on the smaller numbers in it (the Brent tables are now taking over a week each which is a bit boring).

Reserving:
51803^29-1
52009^29-1
52363^29-1

Chris

 chris2be8 2015-02-08 08:20

Those 3 are done:

51803^29-1:
r1=1891749304431093647335954041286418823368710289952614483 (pp55)
r2=530985075554255361342181352076505346210048101487273174046836429713565312580227 (pp78)

52009^29-1:
r1=1219738259442035039002950211706444441961282554387 (pp49)
r2=920321995026327977361109450065799563671357831767582385543577597696063990675999223903 (pp84)

52363^29-1:
r1=186933006440408144519158582695824349669613717 (pp45)
r2=7261207925014463547766353803476693766715045620979086322522239641601165192090167578608693 (pp88)

So reserving a few more:
46691^31-1
46757^31-1
46919^31-1
47119^31-1
47869^31-1
47917^31-1
48049^31-1
48397^31-1

Chris

 RichD 2015-02-08 15:31

Here is a list of the smallest numbers in the file (minus Chris’). He has a better scheme for choosing numbers but this is for the rest of us. :smile:

[CODE]126902827 16 C130
183033817 16 C133

13256609706475931 10 C162
1145924053 18 C164
1149989833 18 C164
36529 36 C165
58789 36 C168
46733917 22 C169

84969569171 16 C173
171634701455943275693670846531537378210379003 4 C177
149107399621 16 C179

563035735138626886051 2 C182
3760067 28 C185
28409 42 C188
237250154152941828313706973109892307074156361791 4 C188
4851463 28 C188
29501 42 C188
29567 42 C188
29573 42 C188
29581 42 C188
621011411269 16 C189

39097262657 18 C191
751410597400064602523400427092397 6 C194
828277 36 C199
1394714501 22 C199[/CODE]

 Dubslow 2015-02-08 23:37

About half of those are already factored.

[code]Factored 126902827 16 C130 http://factordb.com/index.php?query=126902827%5E16-1
Factored 183033817 16 C133 http://factordb.com/index.php?query=183033817%5E16-1
Factored 13256609706475931 10 C162 http://factordb.com/index.php?query=13256609706475931%5E10-1
Factored 1145924053 18 C164 http://factordb.com/index.php?query=1145924053%5E18-1
Factored 1149989833 18 C164 http://factordb.com/index.php?query=1149989833%5E18-1
Factored 36529 36 C165 http://factordb.com/index.php?query=36529%5E36-1
Factored 58789 36 C168 http://factordb.com/index.php?query=58789%5E36-1
Unknown 46733917 22 C169 http://factordb.com/index.php?query=46733917%5E22-1
Unknown 84969569171 16 C173 http://factordb.com/index.php?query=84969569171%5E16-1
Factored 171634701455943275693670846531537378210379003 4 C177 http://factordb.com/index.php?query=171634701455943275693670846531537378210379003%5E4-1
Unknown 149107399621 16 C179 http://factordb.com/index.php?query=149107399621%5E16-1
Factored 563035735138626886051 2 C182 http://factordb.com/index.php?query=563035735138626886051%5E2-1
Factored 3760067 28 C185 http://factordb.com/index.php?query=3760067%5E28-1
Factored 28409 42 C188 http://factordb.com/index.php?query=28409%5E42-1
Unknown 237250154152941828313706973109892307074156361791 4 C188 http://factordb.com/index.php?query=237250154152941828313706973109892307074156361791%5E4-1
Unknown 4851463 28 C188 http://factordb.com/index.php?query=4851463%5E28-1
Factored 29501 42 C188 http://factordb.com/index.php?query=29501%5E42-1
Factored 29567 42 C188 http://factordb.com/index.php?query=29567%5E42-1
Factored 29573 42 C188 http://factordb.com/index.php?query=29573%5E42-1
Factored 29581 42 C188 http://factordb.com/index.php?query=29581%5E42-1
Factored 621011411269 16 C189 http://factordb.com/index.php?query=621011411269%5E16-1
Unknown 39097262657 18 C191 http://factordb.com/index.php?query=39097262657%5E18-1
Factored 751410597400064602523400427092397 6 C194 http://factordb.com/index.php?query=751410597400064602523400427092397%5E6-1
Unknown 828277 36 C199 http://factordb.com/index.php?query=828277%5E36-1
Unknown 1394714501 22 C199 http://factordb.com/index.php?query=1394714501%5E22-1[/code]

I'll take 46733917 22, it's been a while since I've done SNFS. How do we report these again?

Edit: That number was trivial to factor, check FDB. I guess I'll move on to
[STRIKE]84969569171^16-1[/STRIKE]
[STRIKE]149107399621^16-1[/STRIKE]
237250154152941828313706973109892307074156361791^4-1

Further edit: Am I understanding the original file correctly that they want things like
[code]6431153252786376633222557484398827575103234510401037466972331882766542894973799781761665760282634830612297990845862767242620344681867295144091118001235847578924950945894251335000113485015904913606610975624250808818995959977875768198390536484358728422066983296897331722705683385149643253983303265978356222910917408491620158206487993226138112983963108215448612537268883667140158709957171091863244503191754264267030908915788919967569523893515125362902482577567211502144283314934803496833^896798-1[/code] to be factored? That seems... like wishful thinking.

 Dubslow 2015-02-09 01:09

All but the last from RichD's post were trivial to factor algebraically, with the last requiring SIQS on a C91.

 wblipp 2015-02-09 01:20

[QUOTE=Dubslow;394943]About half of those are already factored.

[code]Factored 126902827 16 C130 http://factordb.com/index.php?query=126902827%5E16-1[/code][/QUOTE]

This line means that Pascal wants the factors of sigma(126902827^16). 126902827 is a prime, so this is equal to
(126902827^17-1)/126902826, which is currently still a [URL="http://factordb.com/index.php?id=1100000000602744386"]C130 [/URL].

OPN is usually interested in factors of (p^q-1)/(p-1) where p and q are both prime. In most instances that OPN cares about composite q, factors of one of the algebraic factors are sufficient, so the factors for composite q are seldom needed directly.

 Dubslow 2015-02-09 01:27

[QUOTE=wblipp;394960]This line means that Pascal wants the factors of sigma(126902827^16). 126902827 is a prime, so this is equal to
(126902827^17-1)/126902826, which is currently still a [URL="http://factordb.com/index.php?id=1100000000602744386"]C130 [/URL].

OPN is usually interested in factors of (p^q-1)/(p-1) where p and q are both prime. In most instances that OPN cares about composite q, factors of one of the algebraic factors are sufficient, so the factors for composite q are seldom needed directly.[/QUOTE]

I knew I was forgetting something. Man, I've made quite the fool of myself today, haven't I :davieddy:

 RichD 2015-02-09 02:48

Oops! Once you have your head down in a project you seem to forget what others are looking at.

[QUOTE=RichD;394908]
[CODE]13256609706475931 10 C162
[/CODE][/QUOTE]

I'll take this number as:
13256609706475931^11-1

Though, I am a bit over subscribed right now with resources.

 Batalov 2015-02-09 04:47

I am taking 126902827 16 C130 to see if octic is any use (with some tweaking, and on -a side).

... No, no use. Simple quartic x*(x^4)^4-1 is much better. Almost done.

 RichD 2015-02-09 13:40

Remaining composite of 13256609706475931^11-1
[CODE]prp41 factor: 23046603692091333334825230669381594936463
prp121 factor: 7273070015751648094106299851463112565830468965213595036379800222970720956612286015076400002380958567931018120449781474347[/CODE]

 wblipp 2015-02-09 15:37

[URL="http://www.mersenneforum.org/showpost.php?p=394989&postcount=59"]7103^61-1 by NFS@Home[/URL] P73*P159

 chris2be8 2015-02-09 17:03

All the ones I reserved are done. The results are in Factordb so I'll not post them here to save space.

Reserving:
183033817^17-1 (for the smaller system that did the last lot)
22469^47-1 (for my main systems)

Once the second is underway I'll be able to reserve some more for them.

Chris

 Dubslow 2015-02-09 20:51

Dubslow attempts to do useful things, take two.

Thanks RichD for making a simpler list.

[code]
1145924053 18 C164
1149989833 18 C164
36529 36 C165
58789 36 C168
46733917 22 C169

84969569171 16 C173
171634701455943275693670846531537378210379003 4 C177
149107399621 16 C179

563035735138626886051 2 C182
3760067 28 C185
28409 42 C188
237250154152941828313706973109892307074156361791 4 C188
4851463 28 C188
29501 42 C188
29567 42 C188
29573 42 C188
29581 42 C188
621011411269 16 C189

39097262657 18 C191
751410597400064602523400427092397 6 C194
828277 36 C199
1394714501 22 C199[/code]

I guess I'll start with 1145924053 18, which is to say (1145924053^19-1)/1145924052. Just to be clear, need I ECM these, or has that been done before being put on the list?

 Batalov 2015-02-09 22:57

[QUOTE=RichD;394908]Here is a list of the smallest numbers in the file (minus Chris’).
[CODE]...
563035735138626886051 2 C182
[/CODE][/QUOTE]
There is a typo, a line cut short there.
I've done a few of such numbers before, and I can give anyone who wants to do this number the poly.
The real file entry is this:
[CODE]44799264616686550530996315243199966966425091434166776850060158408354539673563035735138626886051 2
38554240555244771684147788725064564814504311491620196795613705424279432517684827556228587498335690427233900622512289362773643459318294309417509353966389207077852814775292681545055967 4407[/CODE]
Now, where did the enormous value come from? It is actually x = (1429^31-1)/1428
You have to use that, to make the usable snfs poly (because you cannot use neither x^2+x+1 nor x^3-1).
After simplifying:
? (a^31-1)^2+(a^31-1)*(a-1)+(a-1)^2
a^62 + a^32 - 3*a^31 + a^2 - 3*a + 3
? a=1429
1429
? a^2*X^6 + (a^2- 3*a)*X^3 + (a^2 - 3*a + 3)
2042041*X^6 + 2037754*X^3 + 2037757
with X=a^10. Note that a quintic poly will not be able to take care of the middle term (unless with a huge coeff.).
The poly is:
[CODE]#opn2000: s(44799264616686550530996315243199966966425091434166776850060158408354539673563035735138626886051^2)
n: 38554240555244771684147788725064564814504311491620196795613705424279432517684827556228587498335690427233900622512289362773643459318294309417509353966389207077852814775292681545055967
m: 35507679231807726011177575666201
# m = 1429^10
c6: 2042041
c3: 2037754
c0: 2037757
skew: 1
type: snfs
lss: 0[/CODE]
With SNFS difficulty of 195, it is relatively easy. Sieve on the -a side. You can also try 3LP, if you want.
You can also try a quartic with X=1429^15.

Similarly, you can factor other sigma(a^2) cofactors.

For sigma(a^4), simply use x^4+x^3+x^2+x+1 poly, -- there is nothing better.

 Dubslow 2015-02-10 03:51

How do you determine to sieve on the algebraic side (or 3LP)?

 Batalov 2015-02-10 03:52

By test sieving.

 Dubslow 2015-02-10 06:45

Okay, allow me a rephrase: what makes you think "Hmm, maybe, for this particular number/polynomial, I should consider testing the opposite of the conventional wisdom"? Or do you test sieve the algebraic side on all your SNFS jobs?

 axn 2015-02-10 08:14

[QUOTE=Dubslow;395071]Okay, allow me a rephrase: what makes you think "Hmm, maybe, for this particular number/polynomial, I should consider testing the opposite of the conventional wisdom"? Or do you test sieve the algebraic side on all your SNFS jobs?[/QUOTE]

When the algebraic poly shows up with large coefficient(s) and/or higher than normal degree.

 Batalov 2015-02-10 08:23

[QUOTE=Dubslow;395071]"...the opposite of the conventional wisdom"?[/QUOTE]
It is elementary, Watson.
If you [I]have[/I] to use an snfs poly of a degree higher than the "optimal degree for the input size" (which was 5 for this difficulty-190 input but we [I]have[/I] to use 6 or 4), then 1) do indeed consider the other side, 2) the more the degree is off (e.g a 230 with an obligatory quartic), the more reason to test uneven limits and/or 3LP. Homework: check why deg-4 poly works worse that deg-6.

Even more generally, any 500 core-hour job deserves a half an hour preparation. "15 minutes could save you 15% or more" on your sieving. A larger job deserves a larger still prep. The side of sieving is just one of half a dozen parameters that one can tune. If you are not doing that, then you are missing all the fun. Trial sieve frequently to get better skills -- except for boring projects (for boring snfs projects no skills are needed).

 chris2be8 2015-02-10 16:41

183033817^17-1 is done:
r1=75638527492663794617660215394226170244578350977509 (pp50)
r2=20977721849008094239599117843558973978221936566053008221323686368946956204920623229 (pp83)

Reserving:
36529^37-1

Chris

 wblipp 2015-02-10 17:34

[URL="http://factordb.com/index.php?id=1100000000348566756"]9343^61-1[/URL] = p63*p106

 Dubslow 2015-02-10 18:23

[QUOTE=axn;395072]When the algebraic poly shows up with large coefficient(s) and/or higher than normal degree.[/QUOTE]

[QUOTE=Batalov;395074]It is elementary, Watson.
If you [I]have[/I] to use an snfs poly of a degree higher than the "optimal degree for the input size" (which was 5 for this difficulty-190 input but we [I]have[/I] to use 6 or 4), then 1) do indeed consider the other side, 2) the more the degree is off (e.g a 230 with an obligatory quartic), the more reason to test uneven limits and/or 3LP. Homework: check why deg-4 poly works worse that deg-6.

Even more generally, any 500 core-hour job deserves a half an hour preparation. "15 minutes could save you 15% or more" on your sieving. A larger job deserves a larger still prep. The side of sieving is just one of half a dozen parameters that one can tune. If you are not doing that, then you are missing all the fun. Trial sieve frequently to get better skills -- except for boring projects (for boring snfs projects no skills are needed).[/QUOTE]

Ahh, thanks. :smile: For now though, I only want to do 10-50 core hour jobs, i.e. let YAFU do all the work.

Meanwhile, (1145924053^19-1)/1145924052 split with P80 and P84 factors.

Nobody else seems to be working from this list; does anyone mind if I just reserve all of it?

[code]
1149989833 18 C164
36529 36 C165
58789 36 C168
46733917 22 C169

84969569171 16 C173
171634701455943275693670846531537378210379003 4 C177
149107399621 16 C179

563035735138626886051 2 C182
3760067 28 C185
28409 42 C188
237250154152941828313706973109892307074156361791 4 C188
4851463 28 C188
29501 42 C188
29567 42 C188
29573 42 C188
29581 42 C188
621011411269 16 C189

39097262657 18 C191
751410597400064602523400427092397 6 C194
828277 36 C199
1394714501 22 C199[/code]

 RichD 2015-02-10 23:18

I believe most are ECMed to about t35 or t40. So once you get above C180 (2/9 * 180 = t40), it might be worth it to run the final level of ECM first. Or you can roll the dice and go directly to SNFS. Others have found a factor to avoid a large NFS job.

Thanks Batalov for the tip. I knew of a couple forms but you provided enough info to make a general statement.
Is there a tips and tricks thread this can be posted in? :smile:
(Thanks for pointing out the typo. I knew something looked funny when I was manually sorting the list but forgot to follow up on the "2" after composing the message.)

You may want to double check the list Dubslow because a couple are spoken for.

In the mean time, some heavy hitters for those so inclined.
[CODE]21767 46 C200
22063 46 C200
22469 46 C201
22679 46 C201
22739 46 C201
23159 46 C201
23687 46 C202
5438347 30 C203
24671 46 C203
24709 46 C203
25037 46 C203
18956983 28 C204
5955749 30 C204
5366319547249 16 C204
26021 46 C204
22199431 28 C206
28793 46 C206
247121218571 18 C206
3253 60 C207
349235516317 18 C208
590713 36 C208
234138894262108061 12 C209[/CODE]

 chris2be8 2015-02-11 17:00

36529^37-1 is done:
r1=58091338511366844622808835606358541710891753351462809858576089771 (pp65)
r2=3096426004556675371903069514609578005304057921553504091410248482067194938553235704204354047244670991 (pp100)

Of those listed by Dubslow the following is done:
36529 36 C165 (above!)

And this has been truncated in his list:
563035735138626886051 2 C182
In mwrb2000.txt it appears in 44799264616686550530996315243199966966425091434166776850060158408354539673563035735138626886051 2
See Batalov's post about it.

I'm happy for Dubslow to do the rest.

Chris

 Dubslow 2015-02-12 02:15

These may take a month or more, is that okay?

With the two mentioned by Chris, I have these left:

[code]1149989833 18 C164
58789 36 C168
46733917 22 C169

84969569171 16 C173
171634701455943275693670846531537378210379003 4 C177
149107399621 16 C179

3760067 28 C185
28409 42 C188
237250154152941828313706973109892307074156361791 4 C188
4851463 28 C188
29501 42 C188
29567 42 C188
29573 42 C188
29581 42 C188
621011411269 16 C189

39097262657 18 C191
751410597400064602523400427092397 6 C194
828277 36 C199
1394714501 22 C199[/code]

There wouldn't really be anything better than the obvious quartics/sextic for the three low power numbers, correct? I'll try the various things that Batalov mentioned for those. (I would hazard a guess that the degree 4 C188 would be the least "well behaved" of the three?)

 Batalov 2015-02-12 03:50

For prime q>13 values, not much can be done except to pay the (p-1) surplus in snfs difficulty and then - a quintic/sextic. But for high q's, p are relatively small, so that's not too much to pay.
For a few composite q (but those are rare, q=15 and 21), there are tricks. q=11, 13 can be "halved".

P.S. I liked the earlier described tricks with "halving" (small p, q=7) cases [URL="http://www.mersenneforum.org/showthread.php?p=370596#post370596"]down to cubics[/URL] (!); that would probably slide only up to 90 (100?) digits only though. Nifty, though. ;-)

 RichD 2015-02-12 05:25

IIRC, q=17 halving doesn’t kick in until somewhere around SNFS-220. So don’t even think about that for these low numbers. The saving is created when the base is large enough, say >p12, where the traditional polynomial gets elevated to a sextic, and that larger poly requires one-bit greater LPB than the octic. (If I said all that correctly.)

 Dubslow 2015-02-12 21:14

[QUOTE=RichD;395131]I believe most are ECMed to about t35 or t40. [/QUOTE]

I'm not so sure about even that:
[code](1149989833^19-1)/1149989832

P40 = 3213055981208391486124934392947803251061
P33 = 851540025603923338207219104468631
P49 = 6001969163083141878388768469774790732583407142943
P42 = 753485494973649196221699984378050106899431[/code]

Lesson learned.

 Dubslow 2015-02-13 03:27

I ([URL="http://mersenneforum.org/showthread.php?p=395400#post395400"]sort of[/URL]) ran ECM on all the others, and reported these to the FDB. It would seem that, at least as far as the FDB knows, little or no ECM has been done.

[code]prp33 = 349157269696963342797035080620271 | 29567^43-1

prp31 = 4427846691936399890015802742591 | 171634701455943275693670846531537378210379003^5-1

prp37 = 1415174572937984635943881666247304821 | 237250154152941828313706973109892307074156361791^5-1
^ Fully factored![/code]

29567^43-1 (CF193) still has a C156, so that looks like SNFS still.

171634701455943275693670846531537378210379003^5-1, CF222, still has a C147... I think that's still SNFS?

 RichD 2015-02-13 05:20

[QUOTE=Dubslow;395401]I ([URL="http://mersenneforum.org/showthread.php?p=395400#post395400"]sort of[/URL]) ran ECM on all the others, and reported these to the FDB. It would seem that, at least as far as the FDB knows, little or no ECM has been done.[/QUOTE]

Finally found the post I was looking for earlier [URL="http://mersenneforum.org/showpost.php?p=383172&postcount=173"]here[/URL].

 Dubslow 2015-02-13 07:20

[QUOTE=RichD;395407]Finally found the post I was looking for earlier [URL="http://mersenneforum.org/showpost.php?p=383172&postcount=173"]here[/URL].[/QUOTE]

That is almost certainly not true of the current batch of numbers. I'm definitely glad I decided to finish ECMing to the original 0.23 I had attempted, I've already found that (84969569171^17-1)/11640830976290) splits as:
[code]
P35 = 27174722980800683612328363916964857
P39 = 368490195799838835682326713093370926377
P100 = 5381496093876794918239577461697358547135704770377871739745150208536620399018626033415340527639882809
[/code]

There's still 14 more to ECM, but it's pretty clear already that these haven't been ECMd to t40. I'd guess t30.

 chris2be8 2015-02-13 08:31

Reserving:
21767^47-1
22063^47-1
22679^47-1
22739^47-1
23687^47-1
29437^43-1

For ECM to T45, then SNFS if necessary.

Chris

 RichD 2015-02-13 16:30

[QUOTE=Dubslow;395409]That is almost certainly not true of the current batch of numbers.[/QUOTE]

You are right. I am trying to interpret the meaning of that post. It didn’t say the numbers were ECMed to t40, just start ECM at t40. That’s why I didn’t bother with numbers until C180 to perform ECM.

Good catch. :smile:

 Dubslow 2015-02-13 20:03

[QUOTE=RichD;395440]You are right. I am trying to interpret the meaning of that post. It didn’t say the numbers were ECMed to t40, just start ECM at t40. That’s why I didn’t bother with numbers until C180 to perform ECM.

Good catch. :smile:[/QUOTE]

I happened to be reading some older posts, and stumbled upon that post from its context -- it was in response to a question about a specific file at a specific time.

By the way, some older posts mentioned various scripts to both parse the relatively dense roadblock files and to check numbers in the FDB before starting work on them. Would people be willing to post theirs?

Finally, more ECM factors:

[code](149107399621^17-1)/149107399620
P41 = 26710960487576079949768373669299633202857
C139 = 2235103488910109947661939213028171125127174997680723090661545701323123822284100156768223195027518635207949822771348015899080261736880797641

(3760067^29-1)/3760066
P37 = 3045509509684144725987510473093336041
P148 = 4186166489605713146158036096510657474413401024347780953303356993463996600310528649365804130589988363389904036136549653876302508962191122828096998241[/code]

That makes 3 of the first 4 on my list of "more ECM" jobs (that I mentioned yesterday) have been at least partially factored by ECM. I also learned from the reading I did that full factorizations are practically useless for OPN, so I won't be NFSing any of the CFs that have been reduced (unless upon request).

Edit: 4 of 5... This is starting to seem incredibly lucky...
[code](28409^43-1)/28408
P39 = 296978085957996408983189599712074177313
P149 = 37362906083966005082435969235437499569403166878650719584880472832288976928794846351610597540137369882527491701462711437445983919474239386830031121107
[/code]

 RichD 2015-02-13 22:59

I received a note from Pascal when the MWRB file was re-instated along with updates to the Txxxx files. He also mentioned a new direction for most wanted and that a post will be forth-coming.

Hopefully, he will stick his head in here soon to make some clarifications.

 Pascal Ochem 2015-02-14 22:06

Thank you all for the factors.

We write N = p^e*m^2 for an OPN.
The latest run took about 12 days to obtain N > 10^2000.
The next goal is m > 10^1000.
This will imply the current bound N > 10^2000 and improve
the bound m > 10^75 used in Pomerance's heuristic argument
[url]http://oddperfect.org/pomerance.html[/url]

We will modify the program to obtain lower bounds on m instead of N.
In the mean time, we already know that the composites from the special prime
(of the form sigma(p^1)) in the txxxx files will be wanted. So we can focus on them.

[QUOTE=Dubslow;395452]
This is starting to seem incredibly lucky...
[/QUOTE]
Great ! I hope your luck will continue.

 RichD 2015-02-14 23:02

I'll take the first 6 from the t1600 file -- of the form sigma(p^1).

These are small enough that GNFS will be quicker than looking for a special form as described in Batalov's earlier post.

 chris2be8 2015-02-15 16:49

Results so far:
22469^47-1 [code]
r1=477543350616705955411438859692611074706486967 (pp45)
r2=311787544632673452514777995938121107370237503335522083125207819545482666084210356615806161047300643981386730564835049227273889590611835652072394331842305173 (pp156)
[/code] I didn't run ECM against this, I had to start one while my GPU ECMed the rest.

22063^47-1
[code]
Found probable prime factor of 42 digits: 224172527254460923097320700373859558360073
Composite cofactor 287082874607048462762709389763338908094261110505314485350456691813225285074870918722983977765387376614106543543221872724766738313640617335066829783399274580841 has 159 digits
[/code] I assume this doesn't need fully factoring.

22679^47-1
[code]
Found probable prime factor of 47 digits: 12422229658754380220560064955215468939831619943
Probable prime cofactor 18387345750741793931996136644297287902304883406907078934763668163525617698634139636567280746621461990390018506570754589945592757980387843588948764777494527 has 155 digits
[/code]
And 29437^43-1 is in LA, ETA about 3 hours.

@Pascal, does your job automatically pick up results from factordb? If so is it worth posting theme here as well?

Chris

 RichD 2015-02-16 14:34

[QUOTE=RichD;395527]I'll take the first 6 from the t1600 file -- of the form sigma(p^1).[/QUOTE]

Done.

Looks like the *2* (C182) has not been claimed. I'll do it next.

 chris2be8 2015-02-16 16:52

Two more results:
29437^43-1 [code]
r1=17407255346082472871143292808345386547997 (pp41)
r2=102961390170911484966305733206846911347633070237205016755503471 (pp63)
r3=27551107793048782479899925721297437513448329366926505446629869370575326960725924864261 (pp86)
[/code] (I should have ECMed it).

23159^47-1 [code]
Found probable prime factor of 44 digits: 12806833559364579769534231363027419918448429
Probable prime cofactor 46739914470997616369452358953972821837916891376917679255479618616521851605018179606094591889214020805633058501450445298862097285377012995349763176580689220349 has 158 digits
[/code]
And reserving:
13513^53-1
I'll run ECM to T50 since it's about SNFS 231. So may need to do soemthing else while the ECM completes.

Chris

 pinhodecarlos 2015-02-16 18:06

Guys, I can host an ecmserver. Got the files here but I don't have a clue on how to set up, how to feed with candidates, etc.

 pinhodecarlos 2015-02-16 18:23

[QUOTE]4) Create an ecmserver.ini file. The minimal format is:
number1
number2
...
In this case names will be assigned to each entry.

A better format (and the save format of ecmserver.ini) is:
name1 N number1
name2 N number2
...

The only limit on the number of entries is memory.
[/QUOTE]So I am trying to create the ecmserver.ini. What should be my entries for OPN? I need a list of
name1 N number1

 wblipp 2015-02-17 14:52

[QUOTE=pinhodecarlos;395610]So I am trying to create the ecmserver.ini. What should be my entries for OPN? I need a list of
name1 N number1[/QUOTE]

There is a wide range of numbers of interest. Do you want to limit the quantity and sizes to things that could be used by NFS@Home in the upcoming Need for Speed? If yes, what SNFS and GNFS sizes? I think we should select from Pascal's "Most Wanted" list, then from his "First Composites" lists. Other sources are possible, too.

 pinhodecarlos 2015-02-18 12:48

Sorry William for the late reply.
We need candidates that passed ECM to t55.

 chris2be8 2015-02-18 16:40

My latest result:

21767^47-1 [code]
r1=82518836895947206027655167455403750447187815354479754439495778799829619381178181 (pp80)
r2=418987829982602215703955385081838625167290709409833286858042023167138009259006589364483379053437868040085589747211632757 (pp120)
[/code]
At least this wasn't an ECM miss.

Chris

 wblipp 2015-02-18 21:11

[QUOTE=pinhodecarlos;395730]Sorry William for the late reply.
We need candidates that passed ECM to t55.[/QUOTE]

To begin with, do you want SNFS 235-250? 260-280? 290-300?

 pinhodecarlos 2015-02-18 21:57

SNFS 235-250

 wblipp 2015-02-19 06:03

1 Attachment(s)
Here are the SNFS 235 to 250 from Pascal's current Most Wanted List. At the top are numbers that I know have had ECM, with the amount known to me in shown in the old ecmserver.ini format. Note that many of these are close to ready for SNFS, but they also are mostly smaller numbers. Below these are the numbers with no ECM that I am aware of - as discussed elsewhere on the board, these appear to have had a t25.

[B]WARNING: the numbers with no ECM indicated are NOT ready for NFS.[/B] These are supplied in response to Carlos' request for setting up an ECM server.

 Batalov 2015-02-19 08:03

At least some of them don't look too hot:
[CODE]Input number is 35721388774678269868793276385502010519079245280791966600623775634479441028590576877407600157534185109866242133461104335120524884711801644809959561805474567956570416303274626598665668789075306314480668798564175314698152705192821 (227 digits)
Using B1=43000000, B2=582162027730, polynomial Dickson(30), sigma=1059591068
Step 1 took 289154ms
********** Factor found in step 1: 3103497524668699026642463582459981
Found probable prime factor of 34 digits: 3103497524668699026642463582459981
Probable prime cofactor 11510042618284852085267177674319753759806922851065905755935787064025440476022205222550848754597499107839883042071856789043801875793887310823019710777879474453013296113881117315041102351913245641 has 194 digits[/CODE]
There would have been some weeping and gnashing of teeth if this one went on into snfs...

 wblipp 2015-02-19 19:40

[QUOTE=Batalov;395812]There would have been some weeping and gnashing of teeth if this one went on into snfs...[/QUOTE]

[B]Yes[/B] - these are in response to Carlos' inquiry about setting up an ECM server, not as current NFS candidates. I added a clarifying warning to the listing message.

 RichD 2015-02-19 20:44

I am passing through 300 @ 11e7 on these.

7487^61-1
7673^61-1
8111^61-1
8447^61-1

 Dubslow 2015-02-20 18:47

I've found these factors, all but that last of which I've previously reported (I'm pretty certain).

[code]prp33 = 349157269696963342797035080620271 | 29567^43-1

prp15 = 953311714314151 | 828277^37-1

prp14 = 50056208995151 | 171634701455943275693670846531537378210379003^5-1
prp31 = 4427846691936399890015802742591 | 171634701455943275693670846531537378210379003^5-1

prp37 = 1415174572937984635943881666247304821 | 237250154152941828313706973109892307074156361791^5-1

prp45 = 258068286408471734706262111416169098030943727 | (1394714501^23-1)/642963384500[/code]

That means of the list I had, I will be NFSing these numbers:
[code](58789^37-1)/913624308
(46733917^23-1)/46733916
(4851463^29-1)/4851462
(29501^43-1)/29500
(29573^43-1)/29572
(29581^43-1)/29580
(621011411269^17-1)/621011411268
(39097262657^19-1)/39097262656
(1394714501^23-1)/642963384500
(751410597400064602523400427092397^7-1)/10167336793420274136744131178987210276
(828277^37-1)/789605213485267733676[/code]

(828277^37-1)/(828276) has a P15 factor, is that sufficient for OPN purposes?

 wblipp 2015-02-20 23:33

[URL="http://www.factordb.com/index.php?query=%28852030810084611^17-1%29%2F852030810084610"]852030810084611^17-1[/URL] = p40 * p200

 RichD 2015-02-22 05:05

[QUOTE=RichD;395858]I am passing through 300 @ 11e7 on these.

7487^61-1
7673^61-1
8111^61-1
8447^61-1[/QUOTE]

Now passing though 800 @ 11e7 - each.
What is needed before sending to NFS?

 wblipp 2015-02-22 17:04

[QUOTE=RichD;396051]Now passing though 800 @ 11e7 - each.
What is needed before sending to NFS?[/QUOTE]

Looking at the previous work I am aware of, the following number of curves at 11e7 will take these to 2/9 of the NFS size.
[CODE]7487^61-1 800
7673^61-1 900
8111^61-1 1600
8447^61-1 2500
[/CODE]

 RichD 2015-02-22 23:13

No factor found

Completed
7487^61-1 - 900 @ 11e7
7673^61-1 - 940 @ 11e7

 chris2be8 2015-02-23 16:48

Latest results:
23687^47-1 [code]
r1=613391699076213734488821449187625123568246684264031203877036914447327934238112453011 (pp84)
r2=2752600617273131914680068011835117691839008409061611587046917660508214756193318780103868517282924506057570788784298867 (pp118)
[/code]
22739^47-1 [code]
r1=11120957135510122019420692775097547194114329388134887019576913771934169092781375657070943 (pp89)
r2=23193141067817412669535425355946619083345113269196169560704536024851011087743535252059183749386299531659073765467 (pp113)
[/code]
Chris

 RichD 2015-02-25 05:00

No factor found

Completed.
8111^61-1 - 1650 @ 11e7

I have one more in the works.
8543^61-1
What would be the curve count @ 11e7 to get it NFS ready?

 Dubslow 2015-02-25 17:48

2/9ths of 240 is 53, and the ECM README suggests:
[code]~ ∰∂ tecm 53

Digits B1 B2 num curves brent-suyama curves
50 43e6 2.4e11 8266 7553
55 110e6 7.8e11 20158 17769[/code]

So I guess ~15K curves?

 wblipp 2015-02-25 19:06

[QUOTE=RichD;396293]
8543^61-1
What would be the curve count @ 11e7 to get it NFS ready?[/QUOTE]

Accounting for the work I'm aware of at 43e6, 3200 @ 11e7 will complete ECM to 2/9 of SNFS size.

 chris2be8 2015-02-26 16:56

Reserving:
13789^53-1

For ECM to T50, then SNFS after I've finished 5443^59-1 and 13513^53-1.

Chris

 chris2be8 2015-02-27 16:39

ECM factored 13789^53-1: [code]
********** Factor found in step 2: 320302056488442727718936202859814090606710271
Found probable prime factor of 45 digits: 320302056488442727718936202859814090606710271
Composite cofactor 562569124272615439614912616658750603769519743789930646231004291957872700291234471275211986009582263544443809683002343372046772621423535724724802513653180056675162926605491 has 171 digits
[/code]
I don't think it's worth fully factoring it, that would be a lot of work for little benefit.

Chris

 wblipp 2015-02-27 17:42

[QUOTE=chris2be8;396550]I don't think it's worth fully factoring it, that would be a lot of work for little benefit.[/QUOTE]
Do you know how much ECM you applied? I try to track these effort levels in case it becomes of more interest at a future date.

 RichD 2015-02-28 03:19

No factor found

Completed.
8447^61-1 - 2700 @ 11e7
8543^61-1 - 3310 @ 11e7

Releasing the five p^61-1 numbers to other SNFS resources. These are beyond my capacity.

 chris2be8 2015-02-28 16:54

[QUOTE=wblipp;396562]Do you know how much ECM you applied? I try to track these effort levels in case it becomes of more interest at a future date.[/QUOTE]

I ran T40 (about 2300 @ 3e6) and 768 curves at 11e6. The numbers get rounded to a multiple of 256 because my GPU does 256 curves at a time.

Chris

 Dubslow 2015-02-28 19:17

[code]58789^37-1 = prp55 = 4053950016570109853137607686401867948266351783258174737 * P113

46733917^23-1 = P45 = 385588009410305972016660003487275137513789383 * P125[/code]

The latter was tested up to t39, according to the Yafu logs.

 chris2be8 2015-03-03 16:53

5443^59-1 done.

5443^59-1 done: [code]
Tue Mar 3 13:15:14 2015 prp59 factor: 15643327990819969353366837067862736320828228961829644936601
Tue Mar 3 13:15:14 2015 prp114 factor: 223126119352093578993275856323583615920317369035639178256997814193027096383679565598632044101612047420927870099049
[/code]
Chris

 chris2be8 2015-03-04 16:36

Reserving:
234138894262108061^12-1
5438347^31-1

Chris

 paulunderwood 2015-03-04 16:42

[QUOTE=chris2be8;397007]
234138894262108061^12-1
Chris[/QUOTE]

[CODE]? factor(234138894262108061^4-1)

[2 4]

[3 1]

[5 1]

[13 1]

[17 1]

[97 1]

[647 1]

[19793 1]

[21997 1]

[498833 1]

[39023149043684677 1]

[106527602622299684602461833129 1]

? factor(234138894262108061^4-234138894262108061^2+1)

[853 1]

[2132125119215893 1]

[226833388169698845353509 1]

[7284932874688379053000718461 1]

? factor(234138894262108061^4+234138894262108061^2+1)

[3 1]

[7 1]

[19 1]

[199 1]

[313 1]

[1087 1]

[2053 1]

[148387 1]

[347341 1]

[1679101 1]

[5526329359153 1]

[113302621770870351937546291 1]
[/CODE]

:smile:

Of course x^12-1=(x-1)*(x+1)*(x^2+1)*(x^2+x+1)*(x^2-x+1)*(x^4-x^2+1) :geek:

 Dubslow 2015-03-04 17:11

[code]
(29501^43-1)/29500<188> = 28321940238536235869285220705204643422823344840276038012609317935261050798624145310443647<89> · 1910005851...69<100>[/code]

 chris2be8 2015-03-05 16:41

[QUOTE=chris2be8;397007]Reserving:
234138894262108061^12-1

Chris[/QUOTE]

Of course I really meant 234138894262108061^13-1 (it's only 1 bit different).

Chris

 Dubslow 2015-03-07 07:57

[QUOTE=Batalov;395074]It is elementary, Watson.
If you [I]have[/I] to use an snfs poly of a degree higher than the "optimal degree for the input size" (which was 5 for this difficulty-190 input but we [I]have[/I] to use 6 or 4), then 1) do indeed consider the other side, 2) the more the degree is off (e.g a 230 with an obligatory quartic), the more reason to test uneven limits and/or 3LP. Homework: check why deg-4 poly works worse that deg-6.

Even more generally, any 500 core-hour job deserves a half an hour preparation. "15 minutes could save you 15% or more" on your sieving. A larger job deserves a larger still prep. The side of sieving is just one of half a dozen parameters that one can tune. If you are not doing that, then you are missing all the fun. Trial sieve frequently to get better skills -- except for boring projects (for boring snfs projects no skills are needed).[/QUOTE]

Yafu is indeed smarter than I:

[code]nfs: commencing nfs on c231: 135251225971675028301856314427098894013341755820007862475449892152177360830401344474492677430599143634934682310798892907998103029838576741664948681309379622324481870922894883397493363191867346935349845226880835800040189833503235012
nfs: searching for brent special forms...
nfs: input divides 751410597400064602523400427092397^7 - 1
nfs: guessing snfs difficulty 197 is roughly equal to gnfs difficulty 140

gen: ========================================================
gen: selected polynomial:
gen: ========================================================

n: 13302522452015357583701135968080036437319319663374419291243618861343524710430605294054302262936050243750561937471265036679213855126781528186354875972627728860462872611198750606338778403195447337
# 751410597400064602523400427092397^7-1, difficulty: 197.26, anorm: 7.00e+36, rnorm: 7.51e+38
# scaled difficulty: 197.26, suggest sieving algebraic side
# size = 7.867e-10, alpha = 2.428, combined = 1.413e-11, rroots = 0
type: snfs
size: 197
skew: 1.0000
c6: 1
c5: 1
c4: 1
c3: 1
c2: 1
c1: 1
c0: 1
Y1: -1
Y0: 751410597400064602523400427092397
m: 751410597400064602523400427092397
nfs: commencing algebraic side lattice sieving over range: 7060000 - 7080000
nfs: commencing algebraic side lattice sieving over range: 7000000 - 7020000
nfs: commencing algebraic side lattice sieving over range: 7040000 - 7060000
nfs: commencing algebraic side lattice sieving over range: 7020000 - 7040000[/code]

I also seem to recall reading code that can heuristically adjust large prime size/count on either side individually, [STRIKE]so I'm just gonna go with it[/STRIKE] eh whatever, I'll try 3ALP and see if that sieves better than 2. Can't hurt to try :smile:

Edit: 2LP and 3ALP sieve within a minute of each other on a 2d7h estimate, while 3LP was a bit over 20 minutes longer. Not too much of a difference all things considered. Yafu defaulted to 2LP of course.

 chris2be8 2015-03-07 19:24

Reserving two more:
3253^61-1
28793^47-1

Chris

 chris2be8 2015-03-08 16:21

Another one done:
(13513^53-1)/13512 [code]
r1=2701240728568321097103929745764223614404589519849075983273741 (pp61)
r2=23311018160915059471156552798139352393690541736335168968861176725080768497383810628348554774364297894273699886767910324607417872869873219041617664941427481 (pp155)
[/code]
Chris

 Dubslow 2015-03-10 20:18

29573^43-1 = P50 = 80693267880221853205441155003132309250521187966781 * P138

751410597400064602523400427092397^7-1 = P58 = 2551178651974343085742851505709898547795401074468355140471 * P136

29581^43-1 = P54 = 403367396549642158779520138897130627225184319665393323 * P135

I've only had one "good" split so far.

 wblipp 2015-03-11 02:59

[URL="http://factordb.com/index.php?id=1100000000314591188"](9743^61-1)/9742[/URL] = P49 * P191 by yoyo@home with B1=43e6

 chris2be8 2015-03-11 16:58

5438347^31-1 is done: [code]
r1=37920510496816878034363927566124588648967059597276882891895212578967589552600589968644878863 (pp92)
r2=305585925883836316479419656225558281001159481762734466934519603266667842230224076339037043608044491646207406099 (pp111)
[/code]
Chris

 chris2be8 2015-03-12 16:39

Reserving:
14731^53-1

For ECM to T50, then SNFS if necessary.

Chris

 chris2be8 2015-03-13 17:21

234138894262108061^13-1 is done: [code]
r1=17639300944729524455026272481214840836818757245394484821295959443899063876597 (pp77)
r2=1538868063148815493092100939405656312131713062296193605425929384675889001044350492723532877253043025172072648749851129602994557362369 (pp133)
[/code]
Chris

 lorgix 2015-03-15 15:03

Reserving 8081^59-1 for snfs.

 chris2be8 2015-03-18 16:58

28793^47-1 done: [code]
r1=33544051776914949679568795880406577028268816509876487958421660407 (pp65)
r2=420275240706747119505979113608863155399752355528203694381543433649 (pp66)
r3=950744783956957770900546413823741272251567659144064380402819229224195885601 (pp75) [/code]
Does anyone know how much ECM has been run against 22927381^31-1? It's the next logical target by ratio of estimated time to factor vs weight in mwrb2000.txt.

Chris

 wblipp 2015-03-18 17:33

[QUOTE=chris2be8;398013]
Does anyone know how much ECM has been run against 22927381^31-1?[/QUOTE]

yoyo@home has completed 9000 @ 43e6 - that's a bit over t50. I doubt substantially more has been done.

William

 chris2be8 2015-03-20 17:00

3253^61-1 done: [code]
r1=26028406412718665195215968768482557561545330039894093751158234886321 (pp68)
r2=7285222609651707227175199305597301053775463744569081715408117197002489848263437695362003943659935859038641921793566794657049104875352914317 (pp139)
[/code]
@wblipp: 22927381^31-1 is about SNFS 229, 2/9 of that is just over 50, so it's had enough ECM to start SNFS.

So reserving 22927381^31-1

Chris

 wblipp 2015-03-21 14:04

[QUOTE=chris2be8;398216]
@wblipp: 22927381^31-1 is about SNFS 229, 2/9 of that is just over 50, so it's had enough ECM to start SNFS.[/QUOTE]

The following may be of interest - they are also ready for SNFS[INDENT]38971^47-1
4283^61-1
[strike]8081^59-1[/strike][/INDENT]

 lorgix 2015-03-21 14:27

[QUOTE=wblipp;398283]The following may be of interest - they are also ready for SNFS[INDENT]38971^47-1
4283^61-1
8081^59-1[/INDENT][/QUOTE]
8081^59-1 should be almost halfway done. See #279

 wblipp 2015-03-23 03:24

[URL="http://factordb.com/index.php?id=1100000000507713904"]12781^59-1[/URL] by yoyo@home to P55 * P184

 wblipp 2015-03-25 02:42

[URL="http://factordb.com/index.php?id=1100000000472873874"]12277^61-1[/URL] by yoyo@home to P53 * C193

 chris2be8 2015-03-28 16:35

14731^53-1 is done: [code]
r1=2981804405629740415341040920468762312960821235686669 (pp52)
r2=1877700255154476983688496023265705956655808103880782293890283169482720959489493001649475060492433967871690588426644391048765602138437865075672010572229683533098023597 (pp166)
[/code]
Nearly an ECM miss. I ran ECM to T50 so just missed it.

Chris

 lorgix 2015-04-07 15:35

8081^59-1 is factored

8081^59-1 = p68*p159

[CODE]p68 = 85839630462797698974834828620081581538314612501215742861165888374467
p159 = 500428573469422206862689889198481594760520559572924159329890040417411087170833125440594291154312668214673357957984481060738231756389811735113165066684925005817[/CODE]

 chris2be8 2015-04-14 16:02

22927381^31-1 is done: [code]
r1=104902527726793664091856191374389891835120907249211677234193513105393814402401 (pp78)
r2=616378534643776533004778820402012950680364613059637582050184700720413704722570589728763033316316878519935093575256301653177293322672783062755331 (pp144)
[/code]
That took rather longer than I expected. I don't think there are any more in my range in the roadblocks file.

Chris

 wblipp 2015-04-19 00:53

[URL="http://factordb.com/index.php?id=1100000000314577168"]9787^61-1[/URL] as P51 * P190 by yoyo@home

 RichD 2015-06-17 22:26

[url="http://factordb.com/index.php?id=1100000000601550116"]5955749^31-1[/url] as p51 * p67 * p87.

All times are UTC. The time now is 15:24.