# 45-digit factor of (M+2)23209 by ECM by yoyo@home!

21 views
Skip to first unread message

### bearnol

unread,
Dec 5, 2010, 4:07:42 AM12/5/10
to Mersenneplustwo
Congratulations! (and thanks!) to user [P3D] Crashtest of yoyo@home,
who today found the following 45-digit factor:

128201605404515119370139202836664201936768339

http://www.rechenkraft.net/yoyo/show_user.php?userid=18820
[P3D] Crashtest

random seed = 1292328207
iter = 1000
Bmax = 2000
error_shift = 1000
precision = 10000

N[0] = 128201605404515119370139202836664201936768339
a = 0
b = 89688413221901148323265285010785799341246162
m = 128201605404515119370116568715250501262461267
q = 2223291254715649492350652805622697
P = (1965754593, 60889907444088140269567387611684054357943591)
P1 = (0, 1)
P2 = (53898277912729453733086466028166174057829105,
99992884604099290066056253233347269766285331)
N[1] = 2223291254715649492350652805622697
a = 0
b = 517136918933228623427518117209413
m = 2223291254715649580335686599749543
q = 87107074056883833949344277
P = (3421911252, 1602842038559204797474188390599531)
P1 = (0, 1)
P2 = (1088055996380113964229767495009419,
788744077462490401593545836496284)
N[2] = 87107074056883833949344277
a = 0
b = 5202092132633676772984237
m = 87107074056902004187893139
q = 53197211956017391
P = (2362625119, 84577898739301293212944978)
P1 = (0, 1)
P2 = (33468624707842766025076354, 18137103533850782215747782)
N[3] = 53197211956017391
a = 0
b = 26179771598127550
m = 53197211605949373
q = 13302628558627
P = (2223124758, 18253021777148979)
P1 = (0, 1)
P2 = (4607961748771082, 44289788572053441)
N[4] = 13302628558627
a = 0
b = 9072964657831
m = 13302635814493
q = 1297944757
P = (1377122123, 11800405242477)
P1 = (0, 1)
P2 = (7213009280011, 9725731475168)
N[5] = 1297944757
a = 0
b = 185543736
m = 1298016769
q = 831529
P = (1186518069, 990249340)
P1 = (0, 1)
P2 = (208628686, 90959236)
proven prime
GP/PARI CALCULATOR Version 2.3.5 (released)
i386 running darwin (ix86 kernel) 32-bit version
compiled: Mar 1 2010, gcc-4.0.1 (Apple Inc. build 5490)
(readline v6.1 enabled, extended help available)

Copyright (C) 2000-2006 The PARI Group

PARI/GP is free software, covered by the GNU General Public License,
and
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 4000000, primelimit = 500000
? (2^23209+1)%128201605404515119370139202836664201936768339
%1 = 0

? isprime((2^23209+1)/
(3*4688219*27665129*128201605404515119370139202836664201936768339))
%2 = 0

### bearnol

unread,
Dec 6, 2010, 6:09:59 AM12/6/10
to Mersenneplustwo
Details of the lucky curve:

Desmond:~ james\$ /Applications/sage/sage ; exit;
----------------------------------------------------------------------
| Sage Version 4.3.2, Release Date: 2010-02-06 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: def FindGroupOrder(p,s):
....: K = GF(p)
....: v = K(4*s)
....: u = K(s^2-5)
....: x = u^3
....: b = 4*x*v
....: a = (v-u)^3*(3*u+v)
....: A = a/b-2
....: x = x/v^3
....: b = x^3 + A*x^2 + x
....: E = EllipticCurve(K,[0,b*A,0,b^2,0])
....: return factor(E.cardinality())
....:
sage:
FindGroupOrder(128201605404515119370139202836664201936768339,1403722985)
2^2 * 3^2 * 11 * 13 * 31 * 53 * 227 * 967 * 29411 * 1043173 * 1363273
* 1577143 * 1046754883

GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is 1035398473...202142921 (6973 digits)
[Sat Dec 04 23:43:35 2010]
Using special division for factor of 2^23209+1
Using B1=11000000, B2=27942074176, polynomial Dickson(12),
sigma=1403722985
dF=11520, k=19, d=120120, d2=17, i0=75
Expected number of curves to find a factor of n digits:
20 25 30 35 40 45 50 55 60 65
3 7 27 126 710 4685 35276 296128 2773516 2.9e+007
Step 1 took 6727688ms
Estimated memory usage: 1664M
Initializing tables of differences for F took 6921ms
Computing roots of F took 55422ms
Building F from its roots took 50969ms
Computing 1/F took 20656ms
Initializing table of differences for G took 16141ms
Computing roots of G took 47187ms
Building G from its roots took 51156ms
Computing roots of G took 47812ms
Building G from its roots took 51016ms
Computing G * H took 12578ms
Reducing G * H mod F took 17734ms
Computing roots of G took 47891ms
Building G from its roots took 51391ms
Computing G * H took 12750ms
Reducing G * H mod F took 17922ms
Computing roots of G took 48000ms
Building G from its roots took 51563ms
Computing G * H took 13562ms
Reducing G * H mod F took 18922ms
Computing roots of G took 48282ms
Building G from its roots took 51046ms
Computing G * H took 12828ms
Reducing G * H mod F took 19453ms
Computing roots of G took 48906ms
Building G from its roots took 51235ms
Computing G * H took 12859ms
Reducing G * H mod F took 17672ms
Computing roots of G took 47734ms
Building G from its roots took 51203ms
Computing G * H took 12735ms
Reducing G * H mod F took 19515ms
Computing roots of G took 48594ms
Building G from its roots took 51797ms
Computing G * H took 12672ms
Reducing G * H mod F took 17703ms
Computing roots of G took 48375ms
Building G from its roots took 51203ms
Computing G * H took 12703ms
Reducing G * H mod F took 17907ms
Computing roots of G took 47625ms
Building G from its roots took 51390ms
Computing G * H took 12641ms
Reducing G * H mod F took 17531ms
Computing roots of G took 48094ms
Building G from its roots took 51718ms
Computing G * H took 12969ms
Reducing G * H mod F took 17703ms
Computing roots of G took 48344ms
Building G from its roots took 51906ms
Computing G * H took 12891ms
Reducing G * H mod F took 17937ms
Computing roots of G took 48391ms
Building G from its roots took 51687ms
Computing G * H took 12922ms
Reducing G * H mod F took 17781ms
Computing roots of G took 48438ms
Building G from its roots took 51672ms
Computing G * H took 12562ms
Reducing G * H mod F took 17656ms
Computing roots of G took 48469ms
Building G from its roots took 51469ms
Computing G * H took 12750ms
Reducing G * H mod F took 17687ms
Computing roots of G took 48438ms
Building G from its roots took 52187ms
Computing G * H took 13000ms
Reducing G * H mod F took 18141ms
Computing roots of G took 48469ms
Building G from its roots took 51781ms
Computing G * H took 12688ms
Reducing G * H mod F took 18062ms
Computing roots of G took 48266ms
Building G from its roots took 51500ms
Computing G * H took 12672ms
Reducing G * H mod F took 17797ms
Computing roots of G took 47859ms
Building G from its roots took 54719ms
Computing G * H took 15109ms
Reducing G * H mod F took 20125ms
Computing polyeval(F,G) took 134750ms
Computing product of all F(g_i) took 2375ms
Step 2 took 2745297ms
********** Factor found in step 2:
128201605404515119370139202836664201936768339
Found probable prime factor of 45 digits:
128201605404515119370139202836664201936768339
Composite cofactor
8076330013773812721335682586203468987903476611312174817810671138885879907190501214729222179358153314450555782293831278069831967669747325700728546543084688362893989226438656320051344768750705915710660188240800536459142685373676574749669521683428263578979744812984182569257795877440713224078320103690189877157218133977102110922194119567233807397046694633663986665529090797522557204009448303855288422638416970615068250232695517304214961577708269313478068698406858140253958744049075618421224184544768661786339167941791545414672267233330847453746797093062847210406624773270114454167565908219578097131847873221156284789351465884979599577330931331058568013635651444048279591613078691006453952252157684392096259124946366620539422040286238460875917735086585838525363885936001305654709437971174710215331642923021603864457705464362981232385098285698508776926685229065657022641160166968182341229299718147551811380556733815196725631426840528987312031535168193421436301636495007124373734369657250449512001641318974872573482039674417706683727910606015583354593527933709396822732731738739355912892736067496319788921087302041686909694444289599523323459790965043177087363802141481185627974621901786154398362003188788219323948781516036902552208660673150070327701264481856903027347470327016094600332898860310212346642289333748452082492869738015779521149637813120436386973843012987454323965963796953054797028923028021211238228794278697573677255647212201893619758383796459783073696313240547397588892965323921170583906426444227416130593801255273607123178777851197716508648272807384492403697537441152025712387237973735645684968991144057247425976640100172908255160071462487884197326304232035612533757369037268884284040258521476286554966351072275213970677519306885341553649840268759427464038078773470782227592952209006050189161656864384911842931074624352945263612177704278049683112397720483347694370402526655825931903275343397008429824066355655971336003490998793754066720450757329368888874623127677972030749971503928135051943768963793542421076319992423232373629701602644100548363143132384808005470492687986557476443832709414952738878162200331409604533296248272604527933620185963162572407629697459042584827140544698757647278772816210188726698788507886717506338925498803132831639508361281519004514140539506945012461242195723376338900240395924205375736767724879072981634995313161005412729346170335547573918726856402797655388294304562378222765138842582605269351688135785912907222412606276712762091913560507324920595069919486771672516749558256712114354149966497153598582652780063553898685118263559663206859638466388308833506004345162806652462267446538716565366350835960466713767200660601998042076245183204330786249597111433048268351169250664828229533717020100655118664516894195116157614735770683216056950032762860624336189716000127577607160540396605905351466640825330651738494658144383931886487256761154771053612667831764280124317550633744854361643163341440879923590079466553632631343459235859071230279688275287400627097683941487451211606065796164918259169414173569653181454672890711462821820620430979859960216339825840713898636843239646140933142163953974665416756049469214417566099321492077597426049242090359837115587688892954103957699018877155121867605767292010814106531743106371892857170122183045484285109947107169650689248493227376810605967987895343555902446554689635699507149776832989962514880131919938668874482679335917947894235771715496345236326069200061002273544029669716241260163773970080402129595065306743343131920668494886858070023926083724919847998992657246407302531878346621549382026661756312160983489191035456187969039426644696569240172091696666268523893269379848635078527619622950607982879147817225198195116099849010947474017231427022889627814194532452427350473766880191946384132504985914733114325365691790811128128316290521487426406174572185857906084229800132922760759947226067325769772891111589475240268390147096073186245398457842458552227465323278981663556873174974365543577094483016056421019125637342318238919928281564513994033853475280169618329584948445419711289412379040299115806589751842332558838074122189049214340358994213055296766006236796409762980204706879791067468756156985263851575878002154196427806047774888141567385234427751098353496680327415740078794549953315972958244518344157848543865276180740794010639211138643835940693149918972700604922801127950760318264946605901801468380049181891585224679746194443218946273479349507208249415754559225294546017228983071962754754796228880273445882925509917305229046290897368790235724296911199525174615671527319103069932780826741286301168047028068107107107902904194771423092239207321534281112078856719828013426531766301911310608641454552005761404248450574289821449300454290149175645550336305409993913229314753019942647176404950562614911313207704035647512305234545163428281817382678878413994366671935712409486427184387753237047121286370287793845792194590413034741500481849358859560890547021400186504437460261311365794914276531294174236367114413768600738833551996819490200309218556242752332853878360312714051829745179516895070591763457884850117775130953074548943339828231747081675005469739424286028687821766565294071119154296170856656789495762385710996683453221757714074802692243069995433697588734042443259745182587343247872128019777635955259396403679429523779690519305887203094083425267747834629401040516548020893840647215312497209441610783754402881204625905911247126079869748271868435252134715735610657582569310111715913789671216204737567946133309566773657930973191923738724960832112136945826847767602950288014488040008950345239742049829066735975192318204436616469577972357824469384303324093935458311674934726466482453859265782210798619029866495087847429414407305772494583790403390582190861327045111223943170447287690781920973109812453222323444888059868148761646155400172852338177511199529197729037468470566833552883017080506704516931619403021419618562657043378012087305845486981794304285120398532787447221000418988565486657478348507422190725249897668929950513327063385379920900587922503436322162083932365113075743806386629524831327668037243710867518421166148554782898169360447137528861739611461355449784602299960713539938067206494948610969136469728229305291641303483370820433782700070435023422706168903180881041757240172634335924629705230061852856810641841439257572453853684228287368606650477247085525684979969733380119623888109030095645026676977581627350389750363780734333881874951746633312688411805058537668618590830363507559981367943629894462801166721672744969633962340852335624450692833633678157897371876506278250536109387791416733076259190460068786679107374248725802921060310202241286465316286097208591274029406216909118106023831908208074839583456986090046203631518659556629408452148107715295962400579506103001260801392142430631765341508601874795980329289578095976253329328868833159432768646022637094896877311371473932621814147067379386790706066874835967415759661522509506110917134884339
has 6928 digits
Reply all
Reply to author
Forward
0 new messages