mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Gratuitous factors thread (https://www.mersenneforum.org/showthread.php?t=10029)

wreck 2014-02-16 12:13

10^2027-1 is factored.
c1968 = p49 * p1919
p49 = 4496515564174639116528388812244676150431195718893
B1=3e6, sigma=2191480116
group order is
2^2 * 3 * 5 * 149 * 193 * 2113 * 4201 * 6427 * 16871 * 32917 * 67231 * 482947 * 1289447 * 1964659

chris2be8 2014-02-20 16:26

An unusual ECM result for (116^71-7)/46854423138630224010282520369129: [code]
Run 703 out of 3523:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=3926278574
Step 1 took 500ms
Step 2 took 412ms
********** Factor found in step 2: 153692108423546986372071001022228131831
Found probable prime factor of 39 digits: 153692108423546986372071001022228131831
Composite cofactor 52373918890355377030824523221626875006022115553024839776165140839655448132791 has 77 digits
[/code]
And when my script factored the C77:
prp31 factor: 1333700123532999428968902812057
prp47 factor: 39269636379440210387358897325729223312732627663

So ECM found the 39 digit factor insted of the 31 digit factor.

Chris

jcrombie 2014-02-21 18:10

nice p-1
 
So, this is a long ways from being a [URL="http://www.loria.fr/~zimmerma/records/Pminus1.html"]record[/URL] p-1 factor, but it's a personal best.

[CODE]ecm -pm1 -v -inp 969_286p1 3750e3
GMP-ECM 6.4.3 [configured with GMP 5.0.2, --enable-asm-redc] [P-1]
Running on Octacore
Input number is 522043814947752047600367170046886481848261758236831409442604320478419298722564629752964057546876115411501699194416496466571866828241806286381258361900145700740373450668082555451834278602136134333798386756495943831606093073946373449277596900538220768032574619483969004814173108709679961404593927397015209890173070726573297591951077045751133836635634531636268359960017391306785013505260852575778405776784661879535963752752916977068007061182566902500576789222938667932385478572752575747764652823867677128441005234112668599270241696481062760215365162924180056095171283438857734189877347491656567296431378418181410526089586226961428379167794573058330536446775826678390022840837743998897874795339721457124149211406949201601 (717 digits)
Using mpz_powm
Using B1=3750000, B2=19982359468, polynomial x^1, x0=4243987324
P = 255255, l = 85221, s_1 = 46080, k = s_2 = 2, m_1 = 4
Probability of finding a factor of n digits:
(Use -go parameter to specify known factors in P-1)
20 25 30 35 40 45 50 55 60 65
0.28 0.082 0.018 0.003 0.00042 5e-05 5.3e-06 4.9e-07 4e-08 3e-09
Step 1 took 17893ms
Computing F from factored S_1 took 6140ms
Computing h took 296ms
Multi-point evaluation 1 of 2:
Computing g_i took 728ms
TMulGen of g and h took 3532ms
Computing product of F(g_i) took 176ms
Multi-point evaluation 2 of 2:
Computing g_i took 728ms
TMulGen of g and h took 3681ms
Computing product of F(g_i) took 172ms
Step 2 took 15521ms
********** Factor found in step 2: 1021654943410755608715412267216656035949624133193
Found probable prime factor of 49 digits: 1021654943410755608715412267216656035949624133193
Composite cofactor 510978602232304494218931626077050086185869188765963375546795258441834714795154060784201005337743567585480700660419087264141674139853641552082788393794945258739234105491837743084148871110751126170032215284507144149605515532860078478067919659859107215511311868996243682294966198389746512280661948619607851162624836514102906342647259558586033184473260249240246720249361268411400509094505153970078362083128317605603251520566000252307076744982850980264838395076407537797987738531787122006557276992670063183589434293152856367376795022880669346486037674893429078431180217662650903247900886090371596820636510660180618485329549492240744169854665754583680867277288547645753347257 has 669 digits
[/CODE]

Here's the prime - 1 factorization:

[B]2^3.11.13.4219.11699.50101.129763.505691.743179.1053727.7027743727[/B]

lorgix 2014-02-21 18:26

[QUOTE=jcrombie;367471]So, this is a long ways from being a [URL="http://www.loria.fr/~zimmerma/records/Pminus1.html"]record[/URL] p-1 factor, but it's a personal best.

[CODE]ecm -pm1 -v -inp 969_286p1 3750e3
GMP-ECM 6.4.3 [configured with GMP 5.0.2, --enable-asm-redc] [P-1]
*
*
*
Step 2 took 15521ms
********** Factor found in step 2: *
Found probable prime factor of 49 digits: *
Composite cofactor * has 669 digits
[/CODE]Here's the prime - 1 factorization:

[B]2^3.11.13.4219.11699.50101.129763.505691.743179.1053727.7027743727[/B][/QUOTE]
That's certainly nice for such a big number.

lorgix 2014-03-09 15:22

Two ECM hits:

521^103-1: c167 = p57*p111
9371^59-1: c162 = p55*p107

Details are in factordb.

prgamma10 2014-03-09 15:32

[QUOTE=lorgix;368664]
521^103-1: c167 = p57*p111[/QUOTE]
Brent-Suyama extension in action :)

lorgix 2014-03-09 15:36

[QUOTE=prgamma10;368665]Brent-Suyama extension in action :)[/QUOTE]
Yes, I noticed that too. g[SUB]2[/SUB] > 10^14.

unconnected 2014-04-30 11:53

Lucky hit on 394680:i2488 - P50 with B1=3e6.

[quote]GMP-ECM 6.4.3 [configured with GMP 5.0.5, --enable-asm-redc] [ECM]
Input number is 33941504643605215833598135818378409046634927719720027401045020846305903957312959350644460581551661345947405126902256499 (119 digits)
<...>
Run 298 out of 300:
Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=1930087548
Step 1 took 13803ms
Step 2 took 6119ms
********** Factor found in step 2: 16516227863294964177719630683173366755847603082903
Found probable prime factor of 50 digits: 16516227863294964177719630683173366755847603082903
Probable prime cofactor 2055039741794524594346143752701072004387454756407714950005628073836933 has 70 digits
[/quote]

fivemack 2014-06-03 09:56

On aliquot 2232:1120 N=107038661343427382265466252252343932604919903390095312295966128974556735023367658969226022550646952854207533676557681744555648156003822740235110881

while running 1620 curves at B1=1e8 (45 on each of 36 threads Opteron 6168)

[code]
Using B1=100000000, B2=776268975310, polynomial Dickson(30), sigma=3816759987
Step 1 took 420170ms
Step 2 took 4857ms
********** Factor found in step 2: 89189751628105800003969811272863379755636475437414219651
Found probable prime factor of 56 digits: 89189751628105800003969811272863379755636475437414219651
Probable prime cofactor 1200122877230851808963072794936871780581600575282102948430404621643304098435026010646646731 has 91 digits
[/code]

Group order is 2^7 · 3 · 7 · 78839 · 688999 · 1745137 · 2824067 · 3809137 · 7335851 · 43982311 · 100847777 so it would have showed up in step 1 if I'd used the more conventional B1=110M

Sergiosi 2014-06-07 12:56

Just in time before running GNFS on it:

N=14664552920490852505516218769770198614873187681871408943552619635845898067349007530355033222690406514214482743381283899516488939915980559577001537 (aliquot)

[CODE]
Using B1=43000000, B2=240490660426, polynomial Dickson(12), sigma=3993597464
Step 1 took 111091ms
Step 2 took 32406ms
********** Factor found in step 2: 157292757241951178001169133208343763169913905588704783
Found probable prime factor of 54 digits: 157292757241951178001169133208343763169913905588704783
Probable prime cofactor 93230948313363944246534504566388381593784220097986133117112173495537746909483070958239205039 has 92 digits
[/CODE]

Batalov 2014-06-21 06:26

A convenient coincidental number from Cunnigham's extension base-7: 7,861M.
861 is divisible by 7 (of course, it is an "M") and also by 3.
In pari/GP:
[CODE]? factor(7^21*N^42+1)
...
[COLOR="Purple"][117649*N^12 - 117649*N^11 + 67228*N^10 - 16807*N^9 - 2401*N^8 + 4802*N^7 - 2401*N^6 + 686*N^5 - 49*N^4 - 49*N^3 + 28*N^2 - 7*N + 1 1][/COLOR]

[117649*N^12 + 117649*N^11 + 67228*N^10 + 16807*N^9 - 2401*N^8 - 4802*N^7 - 2401*N^6 - 686*N^5 - 49*N^4 + 49*N^3 + 28*N^2 + 7*N + 1 1]

? t=(7*N^2+1)/N

? ? (117649*N^12 + 117649*N^11 + 67228*N^10 + 16807*N^9 - 2401*N^8 - 4802*N^7 - 2401*N^6 - 686*N^5 - 49*N^4 + 49*N^3 + 28*N^2 + 7*N + 1)/N^6 - (t^6)
(117649*N^10 - 33614*N^9 + 16807*N^8 - 38416*N^7 - 4802*N^6 - 9261*N^5 - 686*N^4 - 784*N^3 + 49*N^2 - 14*N + 7)/N^5
? (117649*N^12 - 117649*N^11 + 67228*N^10 - 16807*N^9 - 2401*N^8 + 4802*N^7 - 2401*N^6 + 686*N^5 - 49*N^4 - 49*N^3 + 28*N^2 - 7*N + 1)/N^6 - (t^6)
(-117649*N^10 - 33614*N^9 - 16807*N^8 - 38416*N^7 + 4802*N^6 - 9261*N^5 + 686*N^4 - 784*N^3 - 49*N^2 - 14*N - 7)/N^5
? (117649*N^12 - 117649*N^11 + 67228*N^10 - 16807*N^9 - 2401*N^8 + 4802*N^7 - 2401*N^6 + 686*N^5 - 49*N^4 - 49*N^3 + 28*N^2 - 7*N + 1)/N^6 - (t^6-7*t^5)
(-33614*N^8 + 67228*N^7 - 38416*N^6 + 28812*N^5 - 9261*N^4 + 4116*N^3 - 784*N^2 + 196*N - 14)/N^4
? (117649*N^12 - 117649*N^11 + 67228*N^10 - 16807*N^9 - 2401*N^8 + 4802*N^7 - 2401*N^6 + 686*N^5 - 49*N^4 - 49*N^3 + 28*N^2 - 7*N + 1)/N^6 - (t^6-7*t^5-14*t^4)
(67228*N^6 - 19208*N^5 + 28812*N^4 - 5145*N^3 + 4116*N^2 - 392*N + 196)/N^3
? (117649*N^12 - 117649*N^11 + 67228*N^10 - 16807*N^9 - 2401*N^8 + 4802*N^7 - 2401*N^6 + 686*N^5 - 49*N^4 - 49*N^3 + 28*N^2 - 7*N + 1)/N^6 - (t^6-7*t^5-14*t^4+196*t^3)
(-19208*N^4 - 5145*N^2 - 392)/N^2
? (117649*N^12 - 117649*N^11 + 67228*N^10 - 16807*N^9 - 2401*N^8 + 4802*N^7 - 2401*N^6 + 686*N^5 - 49*N^4 - 49*N^3 + 28*N^2 - 7*N + 1)/N^6 - (t^6-7*t^5-14*t^4+196*t^3-392*t^2)
343
? (117649*N^12 - 117649*N^11 + 67228*N^10 - 16807*N^9 - 2401*N^8 + 4802*N^7 - 2401*N^6 + 686*N^5 - 49*N^4 - 49*N^3 + 28*N^2 - 7*N + 1)/N^6 - (t^6-7*t^5-14*t^4+196*t^3-392*t^2+343)
0
[/CODE]
So there we go, with f = (7^41+1)/7^20 and
g = t^6-7*t^5-14*t^4+196*t^3-392*t^2+343
the difficulty is only 207.8

So, it takes only a couple of hours to solve on a small cluster.
It factors as p80 * p95.

P.S. A tiny improvement (using shift) is
[CODE]? t=x+2
x + 2
? (t^6-7*t^5-14*t^4+196*t^3-392*t^2+343)
x^6 + 5*x^5 - 24*x^4 - 36*x^3 + 128*x^2 - 32*x - 41
[/CODE]
This last poly has a slightly better Murphy E.
[CODE]t skew 2.82, size 2.470e-10, alpha 2.267, combined = 6.034e-12 rroots = 6
t1 skew 2.56, size 2.470e-10, alpha 2.267, combined = 6.180e-12 rroots = 6
[COLOR="DarkOrchid"]t2 skew 1.80, size 2.470e-10, alpha 2.267, [B]combined = 6.248e-12[/B] rroots = 6[/COLOR] <=====
t3 skew 1.17, size 2.470e-10, alpha 2.267, combined = 6.152e-12 rroots = 6
t4 skew 1.64, size 2.470e-10, alpha 2.267, combined = 6.081e-12 rroots = 6
[/CODE]


All times are UTC. The time now is 10:17.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.