Project Euler Factoring Challenge

Primes, divisors, arithmetic, number properties, ...
Post Reply
yourmaths
Posts: 22
Joined: Mon Aug 25, 2014 10:00 am

Project Euler Factoring Challenge

Post by yourmaths » Thu Mar 23, 2017 7:43 am

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

yourmaths
Posts: 22
Joined: Mon Aug 25, 2014 10:00 am

Re: Project Euler Factoring Challenge

Post by yourmaths » Sat Jun 03, 2017 6:22 am

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

yourmaths
Posts: 22
Joined: Mon Aug 25, 2014 10:00 am

Re: Project Euler Factoring Challenge

Post by yourmaths » Fri Nov 02, 2018 11:05 am

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

kenbrooker
Posts: 77
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Project Euler Factoring Challenge

Post by kenbrooker » Sat Nov 03, 2018 11:55 pm

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

Post Reply