Project Euler Factoring Challenge

Primes, divisors, arithmetic, number properties, ...
Post Reply
User avatar
yourmaths
Posts: 34
Joined: Mon Aug 25, 2014 11:00 am

Project Euler Factoring Challenge

Post by yourmaths »

As far as I'm aware there's no problems in Project Euler that require us to factor really big numbers. And yet, some of the more recent factorisation algorithms are really fascinating!

So here it is - The Project Euler Factoring Challenge:

Code: Select all

pefc=[6,
21,
781,
1081,
31747,
312017,
3180883,
53011019,
423481477,
8020357561,
27361689547,
385585252651,
2480598412349,
36680211084547,
430619146089523,
4387113459392471,
84504102936879827,
929614751064817841,
1589943936863275811,
30065589282440207347,
627581157410503278779,
6460533273041647556707,
18727139270270281586861,
583000674719608140771679,
2674614303118714040786411,
47649781758789527486467679,
230747860605351030025316741,
3831113822959985538041795789,
12363300212245841670672172283,
348728478870129910955353039057,
2748771354596093406592559538869,
66605442167220135732862447482193,
300725655829406037777805524900713,
4362425723503840894945871353417523,
71917200668260236023216316994258861,
234749858170904357899298529662712683,
2890259356471892883447335821713760163,
10739649486911360559968359475485477151,
989876318090184728217053520186831698299,
6871637524605188783392741737854006086813,
27089973293126805321007054616073657420383,
969383022491879171025227199911024972960107,
5925630590047470004976299285809197824176989,
38954790748594902066688020379617460257100241,
987947820105143748734312664503182724680745597,
2307309705159761711916313999401710457588310099,
32708901765145455558340663851063774679488605177,
207376539625288800486849811688863167530767942241,
5641293239922491256981273294213545232181803840817,
19715889667641452087397036843443383075798902746603,
160709232717600578324813722365813726765257143263763,
3282697434055023189188252227304941834608623951012903,
40612699772787115584031910144435893456751056193886811,
110293621459087237068302181824777854680548285167606379,
6255482185381604848581277765602399737777258068945364513,
25797720317293356611711986114505405773230049108078830623,
215956815058192998823669646542574726562156080188089972157,
1037863202699589614044292701020716725508563148212479555871,
29073261610896669149152993974840490938186490347816567840421,
392385020864701281937803148334938150556306047946592455164019,
2328631717230004117988043125711191981900472950772545881597859,
44652243778565255952583998804511973220958661160142455982299251,
275233510402281583194679770817479772662401491434621661808720797,
2124109990523727564670877384384002241553204051028285042091818733,
30642898257835405806394111698784255000454596718690868009519035863,
661933787263747830300868954958946211267593158424203628437817892187,
6503482774496320749426104016767087274688707369388969706649056930929,
13332617856395521019092284745730598836248917224695510603765686623569,
280667118365776585703853411630479435760928682736633252219224565461317,
4235641968332179605799038006975981571470813257718719791021213660576777,
11830816307509138570873188409481041900061548379011703237141942395359101,
353031321831398629500361247052986557384321356223440618525233526278809601,
7598853162079982338493924343219655550836483292940407273793345899254049051,
17132245244346804882985363261323334748000925122913112971384768102462264677,
163386947049477850663243436020094868764217642321614952984785801876515297729,
6800198077345692925660950623141174778195963573117820896297634744565512838887,
25251777350362402399501703909776270377655964722208459387170252651035359776493,
132670760721108961198434684311813121742860305976933567215077375056392941517267,
3561728775821844423030180497549632100601035422805531094415668042702317679046579,
16355641787819352341324766885644791750816411106350918160707054350115793246637829,
866421023717598351533467743262660850707904244899647824631413685897185949786917971,
2291279092249542126197572311569873902355843070538266416348040561656752478025311333,
66577036002007471478770090682570639322512658464290214227267044735559793183815615231,
134057351219063677022767395640503111282059342879312979831854153953832337177837808583,
3600434463336783683141465470420418920169448492722409475842973180036236327622175819701,
65481315436770682767066926630391711780666728130998835416549501629265224008813498098837,
783141076339213862962326651124562077996186616135315232996950836237189796646033797860049,
3863112331583550310152227081271565069597865883513637484199471553081026897964689156707977,
16042349608610275390651390787230147757230260432865954972929164164783456367833661187041257,
476384449027758443718948859805745403687520659600020717859834762440663873745777797460907413,
5480069020047243319990278015391971171162522855204699373896137249708204253192299428027349933,
87328268424745521631822709322327272150093450165083375999306052494785002602945069734999298331,
259474447047487535721346139191291259671951442399697598621099312579232352831769540822692187439,
3287930223607304263792974856089871155184234950179740250860880489736491640064736850769226338747,
41963099440616173886889801685525377853308997641227112264768230854565831278443699625515854547761,
652358354518786719561425752676425097247352071558291342167415732884946972536700806099672566902187,
7845470584730032474460230055437040718255008499016665097187634594481224239540657512099915635696461,
25615805883838546390578912301059060454901193573687001373238876245059156418930199330185845786105583,
111016278126643052049362718938785781608929864261352126344149354292208052430263313662589096741309097,
5263767869119490199423696018384248438553111048575754761142757035812091021640474859304394862606870179]
Last edited by yourmaths on Thu Nov 02, 2017 11:59 pm, edited 1 time in total.
level = lambda number_solved: number_solved // 25
Image
User avatar
yourmaths
Posts: 34
Joined: Mon Aug 25, 2014 11:00 am

Re: Project Euler Factoring Challenge

Post by yourmaths »

Here are some 1-minute benchmarks from different methods I've tried:
Trial factoring can factor 18 digits in less than one minute, but quickly becomes infeasible.
The continued fraction method is a good way to get into the more complex methods. With CF I can factor the 34-digit number in 1 minute.
I didn't do too much testing but Pollard's rho method is somewhere in between TF and CF.
Quadratic sieve (best reference for this is Crandall & Pomerance (2005) Prime Numbers - A Computational Perspective, 2nd ed.) uses the square-congruence ideas of the CF method but with a sieve to find smooth numbers in the sequence x^2-n.
My implementation of the basic method could factor PEFC-38 in a minute.
Using multiple polynomials speeds things up a bit and I reached PEFC-42 in a minute.
My best effort so far, letting MPQS run for a few hours yesterday, is the 60-digit number.
If you reach a milestone, you can prove it here without publishing the factors by encrypting a message with RSA encryption:

Factor n=pq.
Choose an exponent (s=65537 is recommended).
Calculate t (which you keep secret) as the multiplicative inverse of s (mod (p-1)(q-1)).
Encode your message in ASCII-256 encoding, which gives you a hexadecimal number m (less than n).
The encrypted message is e = m^t (mod n), and can be recovered as m = e^s (mod n).
So, for example, using the 60 digit number and s=65537:
171937828367791270424657163604042577121889123309089592035814

[Martin Gardner described the historical context of this in the book "Penrose Tiles to Trapdoor Ciphers"]
level = lambda number_solved: number_solved // 25
Image
User avatar
yourmaths
Posts: 34
Joined: Mon Aug 25, 2014 11:00 am

Re: Project Euler Factoring Challenge

Post by yourmaths »

I thought more people would get into this, but anyway I factored the 80 digit number with the quadratic sieve.
I started coding the number field sieve algorithm but have gotten stuck on the square root problem.
level = lambda number_solved: number_solved // 25
Image
User avatar
kenbrooker
Posts: 187
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: Project Euler Factoring Challenge

Post by kenbrooker »

Well you can discount the people who ask for help with a Project Euler problem,
who ask for a PM and then never read the PM sent...

Of course, in the classic logical conundrum,
one can never prove the "never"...

My strange way of expressing...
Empathy...
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Project Euler Factoring Challenge

Post by Oliver1978 »

Haven't tried it, but can surely recommend the book "The Joy Of Factoring" (Samuel Wagstaff Jr.) :wink:
49.157.5694.1125
arthur_vause
Posts: 2
Joined: Sun May 09, 2021 10:49 pm

Re: Project Euler Factoring Challenge

Post by arthur_vause »

Encrypting with the private key is better described as signing the message.

Here is my signed message for PEFC-60
243893928059915482638243477660211453200292945495503186499283
arthur_vause
Posts: 2
Joined: Sun May 09, 2021 10:49 pm

Re: Project Euler Factoring Challenge

Post by arthur_vause »

and here is a signed message for PEFC-100
1331055815941314859959994909863767360729889849296787714219291391269421735171719112435000290662111673
Cot-O-Bus
Posts: 7
Joined: Thu Sep 27, 2018 10:18 am

Re: Project Euler Factoring Challenge

Post by Cot-O-Bus »

Code: Select all

1[2, 3]
2[3, 7]
3[11, 71]
4[23, 47]
5[53, 599]
6[509, 613]
7[353, 9011]
8[1423, 37253]
9[17207, 24611]
10[8317, 964333]
11[74567, 366941]
12[412109, 935639]
13[507673, 4886213]
14[646979, 56694593]
15[7486733, 57517631]
16[7979501, 549797971]
17[93313837, 905590271]
18[220017409, 4225187249]
19[875530589, 1815977599]
20[4263980003, 7051062449]
21[8276100289, 75830540411]
22[68246598031, 94664546797]
23[89310793529, 209685061909]
24[94199494537, 6189000032167]
25[335318851211, 7976331463201]
26[672880795897, 70814596061207]
27[8428557369511, 27376910482931]
28[23852325732497, 160618040602237]
29[18882920285081, 654734544529843]
30[35701478268571, 9767900260228867]
31[565442989307279, 4861270555257211]
32[6992580108344891, 9525159688586723]
33[3223361586963641, 93295662840198193]
34[6517582323781717, 669331894372239719]
35[78068777331454643, 921203112518634527]
36[94861897772141947, 2474648554204270289]
37[955187317150486921, 3025856085583411403]
38[690853012931861669, 15545491277998673779]
39[12164783966281825391, 81372289128513073589]
40[69188130822612353743, 99318155338276193491]
41[155214040701837309077, 174533007262957842979]
42[624092280750856489163, 1553268727063243384289]
43[741778971855696735007, 7988404652700539047427]
44[486229629017672115361, 80116036588093405196081]
45[11593460503448743520863, 85215955996163162208419]
46[2589990784696414467113, 890856337710951665770523]
47[88910726940140125138819, 367884763636754330812883]
48[40788165958449336274219, 5084233006125895840178339]
49[875008847940108369601171, 6447127081289377098125227]
50[498214569488837375750113, 39573089337531289546278731]
51[8725210051938281196753701, 18418952868865256523560663]
52[9622694308527138977052857, 341141194846651712705139679]
53[62460376623284992758554873, 650215416050611105822129907]
54[162006298147662961534078379, 680798356114269925462632001]
55[884938253219132109354385549, 7068834647644728045862340837]
56[3104750819826529186780127833, 8309111363318601174261496631]
57[6464608769296315731283667527, 33406014619767977976509193691]
58[14710295689496410787843385881, 70553524185149782512873804791]
59[94150117929786256821442473253, 308796868768432697951610205057]
60[39421192386093472047395636629, 9953656830611802825206716455911]
61[727867404241379363925482567189, 3199252643628166305180713635031]
62[458531878649578884360486090937, 97380892927380469208704052522123]
63[3415368434413464193169022137723, 80586769974510410131368932535239]
64[4548567055652600267727703793743, 466984429279557669640283909308931]
65[46662565812440731617747251584751, 656691241133287323855850627209113]
66[810890207711289596689491696905401, 816305069378052714265133924702387]
67[946521109282908291933116721745037, 6870932629725933492269132524236917]
68[197011373479860909515998740329347, 67674356159739280236223530088009627]
69[4417390179220487604386566385585821, 63536863844638772355208236781951177]
70[25564626240618352625299184212909661, 165683704055190937633172985408160157]
71[87228216193452187344640955870974097, 135630611558891678971334805280818733]
72[52175981030146063355895592085775653, 6766165481918305976958596406278649517]
73[1966367408182896044568942556952383151, 3864411671215614823312069187667330901]
74[268183664817333015176603265609592213, 63882508489158092800525034390247568529]
75[7902151785428012351203610133440427049, 20676260275178725371543389901483535321]
76[9691523483356511421480751339265237557, 701664510128241260100399870878888091691]
77[36203296038898125721768310173639072583, 697499402353613962548950482544759305771]
78[142932319534614356979476107531433764639, 928206868489108072592014885989352872653]
79[564752467190379102198321212480288303399, 6306707775074099957821700726470207644821]
80[165637868829717929314334788648604360573, 98743372535380651891479163660917717292073]
81[9068008571721173791731515834581025179889, 95547000961110180953507738622752030820739]
82[31367100496463199318275570921784114743963, 73047207296316582999479039899207123188991]
83[82921184179197338134153188249545009911859, 802895383863920176177856617324959236181509]
84[291598950252602649547271357893408684342609, 459731940402851830555284142129108626862487]
85[884390277976945264830319112967853707652301, 4071092314100089687207491392936226819147401]
86[6980483016364475775531064321406272929669269, 9380628143247626383106469557842435077583873]
87[8830956590119444645763021645062233031317119, 88681341409313999532626120376886270051063471]
88[12731016533054193281577395418842968932996013, 303440995583781781491810273451105385366817229]
89[42663201302377687335978873012264178616301473, 376023109351529370711120556859804195680136009]
90[48435197925151591488174600168792924983337173, 9835501235360492551341988644255500707523346881]
91[647919850803488937604007989790865866210817107, 8457942773710945677039796998914589157963550719]
92[9077975601559447831359216140842000850747616869, 9619795454147723471820390903218643346293180799]
93[6893111773071568944638667992518902730962484759, 37642570669047164551915348014140661342632292521]
94[3497311814704378519831338318498894966735013213, 940130705470203289407319968700233272681807292919]
95[46411319026719023476788374728484367187068268477, 904156579054734320833107356434386966518776092293]
96[787090113863853722558408326159429140048751613369, 828822955628722176566956331479129034470870536323]
97[941035986372988771441608530447451457477703207989, 8337056922731118441428012263719455536009471045049]
98[4393469713594724861083508651848667439123440197033, 5830427328217488569665092376116450319608444059351]
99[4461338841721493165952255054961858921178847139487, 24884072262891668570893091984506881987793068655031]
100[16000153885248190368140425723854046858313442786127, 328982327724521129153755819343477339645858578119277]
99 result computed in 39h, 41min, 10 s.
100 result computed in 48h, 51min, 10 s.
themusicman
Posts: 1
Joined: Tue Oct 26, 2021 12:27 pm

Re: Project Euler Factoring Challenge

Post by themusicman »

Hey folks... my first post on here, and... I am once again loving the challenges.

I registered on Project Euler dot net a few years ago and have recently returned to wanting to learn Python - hence diving once again into the challenges. I managed to complete up to challenge 17 a few years ago and now find myself starting this time around on challenge 18.

You guys amaze me with your expertise and knowledge! Whilst you are coding advanced stuff that I will never get to, here's me trying to figure out how to get the pyramid of numbers provided in challenge 18 into variables within my Python code :D

So... I am assuming that I would need to create a single list, with the format something like this... (this is the first three rows of data in challenge 18)

numericData = [[75], [95, 64], [17, 47, 82]] etc....

Is this correct?

Sincere apologies for the noob question, just after some initial guidance. Cheers all, hope you can help.
John
Post Reply