Page 1 of 1

Project Euler Factoring Challenge

Posted: Thu Mar 23, 2017 7:43 am
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]

Re: Project Euler Factoring Challenge

Posted: Sat Jun 03, 2017 6:22 am
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"]

Re: Project Euler Factoring Challenge

Posted: Fri Nov 02, 2018 11:05 am
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.

Re: Project Euler Factoring Challenge

Posted: Sat Nov 03, 2018 11:55 pm
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...