## Project Euler Factoring Challenge

Primes, divisors, arithmetic, number properties, ...
yourmaths
Posts: 31
Joined: Mon Aug 25, 2014 11:00 am

### Project Euler Factoring Challenge

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
yourmaths
Posts: 31
Joined: Mon Aug 25, 2014 11:00 am

### Re: Project Euler Factoring Challenge

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
yourmaths
Posts: 31
Joined: Mon Aug 25, 2014 11:00 am

### Re: Project Euler Factoring Challenge

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
kenbrooker
Posts: 187
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

### Re: Project Euler Factoring Challenge

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;
..."
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

### Re: Project Euler Factoring Challenge

Haven't tried it, but can surely recommend the book "The Joy Of Factoring" (Samuel Wagstaff Jr.)
49.157.5694.1125