Is there a way of finding prime factors of 6521405-digit numbers?

Question

I am trying to make a compression algorithm which works by getting all the prime factors of an integer representation of the file. My code looks like this:

import sys
from primefac import primefac


f = open("root\\dance.gif", 'rb')
#dance.gif is a gif of a goose doing a fortnight dance
file = f.read()
sys.set_int_max_str_digits(len(file)*16)
dec = int.from_bytes(file)
factors = list(primefac(dec))
print(factors)

dec has the value:

79438624904391989773959844854674018295894398840322576258908210197728318464666973416074235832057620462925110151609429266994829152389057428189287839469566203214981521549094696177798467493665879999405709251750415744941994376627260910532858909206771362696051343680428259164715730168231456328726993156928787447157681883285400856525926457913415311307507852370111782347662690793892207750705829219602729060561701958894789593771468326773032854364406049819301643540763898737160776773091487571359788869314446471664083888009218650387901638972370949969356221896862617788343549400158812448114415816861791838183092022623360655365645992372682498499649291296082803282628166469719393218314001006712815725001441606625128121983570099340627295855463356549742461129632766657832992255672970873406757301812998937358707344228625233173074047336252673272389879215811871593687212724012560061048634873590480217445505437182914294198020233947373235689904653737417209559889107986894394076646314003150702191591806050893372098711880913521719737144257171821584542906487096328683480879709714252310075296328409336945724480225767282597642952377577030594413386977576051445406122810677666483611964076073285212465394490864875882176687416834284063276843590577592896355607844314895475821203544363695122898171801429935287141104339758627170065150485816609895770119150022167244074647958476337585870085309934076000516463165747143375864771205866526517181041846727720489712313665980887292931988597727001153133795842788589583937438043266054731447399720365529991694374200326977818422061575969648306149783251150166140439180964354437421849982583835073829241544630138896497735077004845190338693431671782173596655861767383960425433497744697298506659198636234092245052453206163111450959800534472664864244198791665345831356169729188108245007013424939224148239666568989197340336706368596509280680793158432727268972674514446637013700355290943611130127469774137186637754616361505809499020207619440517715211297000153942771755169442987794601173514631236857066456991168221084347658997785186619378534344414306562047282763000520637404740275220220698129636333243502269571651631960489589977431773812147129765464130494947766897562642154411774799441218120314436039124491021745748795515039056434519961502587232149441805408452298919836005773620842025577185184878202940034721177639752468171333726426453642388556303597332997869560105491589325718518533974011361687905268624070386123367889224285691696915612346267829072940459278048216553603455413468601297932405213213006107624109212958511123516965858399242210603928814451689998964166224549045273172158186694787018300907503524108551835463635171688121718809800035842670568098711591640720582813836449938399058682244517118358361049556328334498365215914421819015565675097600820938767853208625008287992022675456726964492294539640778116679789826206926439126854568462836394527681321057709477812644382234009060314564887404752088863688199627706021129045104126055998079100005039960680990406210896559025755780229624918742477369413846436240741741264916641190164513775414214933101112842445998257622919963087757702082628622532773213286537394321409237922147333539377734759655840546419671928882066469656283672805281441108144089225099267769508245241473385985853187903288455191297824966244598907412924308383422330430825965088255483064264683479546767000365387483572798915825973612513047878013743779926147982806659591481776419124736184720879450497073441367653235964166235116218153058843553357344535528752094969104893080020479049650995311399164440642031426751839227466633863679093224214343225382116277790321935532265990712316876899801392712438070924420920125383818109579752756741404201537709971381618404126390286400071534851430578930406382924031484935012870211085011312316016083005901369492083162619199352578716375691016747349772727913993331278469920772665504053185738482140636561795056322548711985703383746497979210108145275118634188981360197155561152789870373335807257451789945352270417267038952647141281509983127427179226722277349846710631284364412782344802983227600477208130274888852923410664798204014510833839581921242395190297617160282219741210083612035738979042698263131892079162738207435514929098550598835776042232166038134837776731854198598268918821147168010121848356741637335309538292936595547768289737983700656722334440481846696493754972809224810827604038576062034074808276277855676359753385641345835531187152688646742930322995680522273370024141871854935427845326231434466774736079359704868126376154877281507125376596027476766852781630707313428825601503367335939951089351700849727948798163524324898429631665106108450987936366299624562979917120316858697969727658836733093214736720239402264856865372977674412398701023753947868774185610578104766587381702053876347650110864711880412368048524341359166617704948340657485069968167892526843441651580036388853305676465830208129022686453699510056309067613984782779263616692030251702760074629596834134435547011604098360779768711542848139880398516036288154787298536798872594552958894355394706285828848183563937587195062500717164699274273810896393614730739507488891390816647352112861935186464040992074728896428672430220424073828686567666424396759962289293362428604918884857595454048941834254232347137596419971928410175812999546490065504086677985746227116391512149582359196856145104103154115851169033754050481592898365885421585011800650602499246206590384309662121650313499101143987419809244558313911559598516992933437149262049017837939430620745310669753780384531406810654560232504425636935471810972550768675169563790323477579235316705994032978214701288038520904365171741344981621996828198940072675741838179124218683478040106650889579368303138856552126896890234724331379220350402242315705903850187369154442623211766501049416657358247859344077012977426184735804534581178200823489206719207110679502056129743079468448936417275764777472062790985877693744280318559699455375797277882798621217189591573532025605514753054112887459627640907387362020956053195581774054342807365948775273719576431883054003441514928093435552841927716210525720960638401501716520822863773380783304715395379786955115121786990282516228040111344170986071804891276393235057514336105214773481487858387475620264772856991560556984766631500605001907578290161930596932152743295254720772485455278406157591940895327978987112794764277770732413798710859302995187501118689973145239584571941308269053898443973636195853688190093310158351701681918260843907298612668837025322671406000560803528477075101408959641218342138281603458466522847929552824139404965882319308775765275132978233813054255157419256790419885472065684978256146888679761908179625394433327594722087598043930237955012573396699698529113586958352684025221341000088521905664784424565986502753266797446429169970430286751095549279568574304362718751012911031152341343069240731344937984496774081971296762191934681265023211736700182952420547523854729759037704349114782214200518452670869990626365458287054448613199055420298183292886405606791340753096826559518654911068242267381439023274210411160615161274283047829173018148751439448355345656426932026446469525926325512611238139789872347330061044825107695656551143196833185649148208798130138563664617717196719312056471509632647070751395818543154996658866310810010790642763421558454792531109575401359019370381317554584364093716558063444566195179807365377637918179126092980580674296761027850713305779102344376349418001645117651842750641356138624235187082435713427799104527475769482056077334451059746599594662382870585356587336567345310556817914535068192407964184185479151053646694732818308857123204305376030212439793403364884913018885459753459247930525406717037422341173976341888075755234968372516141951400175124132378593503954658456550935099927598170675586598197063609913541708332628372824348910596127047699632022472840886477285076599836934735024557431297269995479328784510259532735886406122527677046292971674942360803078951125454300674765917796242919263752722199541896051464521313724691325547425381359303189961843464334474291327450672238871175593010759398399510253842697725643299890432631446407969544001743010411265594736280178332413018845438131761314482993595076203991392683183093086080613352666497792133704095304945805787622520406368522702741361708642095093380251011901278980681269730148259380488767009604222793524402793857775120353010138187909398434536284282335619534108270556359223687080996393851759744298386658386397373987568819247168540519386343028134626503193418826100927853973640915701271769682517803587646662514538115779550181814457505520234126976416750262089754949464019665419413813813984412456329787887288384956879125790011183229737306771525833003560808478391088744821111389921561628965828697310060414313285729207147130949179795293051515937110191626467364237781550827552428313112593109187428890144042512728072730846412626558378968044629957509151007308119540368796588828760520911467530304311950578977204080127398514503559265373319777366368935470227956342759174892993033815980872842432808451817245831981097007199362979448508444822197938718988034884997589463846941810742441839140843676873600654416678542687166737618973907018205503613081780566346726627564135974454930146630497691734053974858788872093361685185018800626133057261119056123888162527812784435916999455380118700366840126200508459065572780262120007271437679971376695129814959129917983436830193422407225046021670110422935062128923617739294814820142836324504540444608406734715640645653584850730410546372241429850626579110340501444429594623740101371435410285116661039973666554158736010747953096503543281655677746677699666714708514873203650483545919717147159598287737582266006268608347347883333698988830315945964266006074839666050313708487792859145274875816876431614679471434006057497850494974936451961344252354574932207041789340301221722013778584213511475145029709231480316996463801150770887919059827438651869326187868487107050001902662599834027842101898573469650257030509214426735908621974563926802418361087960587137399520886629142200938657272137919949931876517493306027347032763280643550726460379855116851520559971659947390865621862521943739003556543986449277598370367676409189246956646366593559728279037726129665301107853324847705382332902521097353653478102685064845037148621312994881341392874169819407910923748782647425465388468193104086998194397386416593486341926579204060019256834790736565138684383297550321901978416230220995419381224556456757855643021931718825885827577040002746526053441795709355431390812658430363486342036054078420972182869082332604376133083215031683722454559150261284400328838268000339654172442335814126070472563173406172814815202305362984732604947349752171060561857514110486888660828815410164636064559482415171023124421515551674358302138182646603439945029492225123204426960614734874408829360633467327330410340740882011553606907615703308696064805254498614476974931739320513159784350893801793953030678291744112599392243458188330437002533217671275765940596718306537313502060202606695366699434675106160086594141603197100525153670903490809835612301409500866084278240662866494941417307466184526845199616994627029902116685667297433069813544295245486058653790429506742568539167954054739894302382057345323948746936316048255773383520003995196377068612608123359639219260688262598868209993407352420494826632874861931255317403144684995943196707930008901156164341611739201956922271779832177693873380364177733702829922107624134686438527820847158894176955886650085132036712408168057439912394327790331717860215536629456245815405120760653595905689079663346430298199840661500355880556893436438890982343179248095977942544342706268482547122866265657749919014539752577421910567042216505800907313446083779162581315565667086051541490348067412472662023696382505894848146134021818624455603655013757454356097552593499423200882550158663304682396107233029789232679442402105333500069806588186167580168716280476459589242355348889032846478339433768210604120657378066072196252367593524120868730637755108777518053495593627204620685456502437020494954678893763190564494449343695517078459308251690020240439820155711835540509653301961681608103832569514737023063897580864949422326911541609461237436901633496445882475961208618002504998397120640733516109628616565938766595764410304827638138147924862553684593369309403487219422171389695469230208638212721450514643881728876097024432208992636649226290885173912885510913223232888802152868588585226133530435964950414093133402937750301851848508009189670188048169414052664641050395608353965610124138542444461667672618535457257102344924933461145751377384154166623733002174648124730256567312690505473068823665363596116794811699853662540727894256159725430482920826799635525503704572895168947036625869866148619583759587820120380485300842875544196615332816891915786765026189763329670443271334549

And I would like to find the factors in under a year.

Answer 1

Factoring large numbers is hard. Very hard in fact. Interestingly, the security of the RSA cryptosystem (which is a very common encryption scheme used about everywhere) is based on the difficulty of factoring a large number N into prime numbers. If you were to find an efficient algorithm to factor large numbers into primes, you would have thus broken RSA encryption (and would be able to become very rich by selling this knowledge to a government agency of your choice).

As such, the answer to your question is: No, its not (currently) possible to efficiently factor large integers into prime factors. There is scientific research happening which may enable quantum computers to help with that by using Shor's_algorithm in the future (and there are already results for smaller integers), but right now, its not possible.

Wikipedia has a nice overview about the challenges and current known algorithms for integer factorization.

Answer 2

As others have already answered your prime factoring question, I'm going to answer your original compression problem: does prime factoring even helps to get some compression? (Spoiler: it does not)

You seem to have a somewhat magical understanding of compression — as some collection of magic tricks that somehow make a file shorter. In reality, compression has some good theory behind it.

Compression relies on the fact, that the input data does not have a uniform probability — some data are more likely than others. Compression assigns shorter codes for a more frequent data, and rare data gets longer codes. Ideally, a data with probability p will be compressed to bits.

Compression relies on knowing your data. There is no such thing as "general purpose compression". Most of supposedly "general purpose" compression algorithms (LZW, Deflate, LZMA, etc) are actually dictionary-based compressors. They work well on the data that have a lot of repeating "words" (text, computer programs), they fail on data that does not have that (sound, video).

Most compression algorithms follow this structure:

1. Process data in such a way, that frequent things become visible. For example:

   • For text, you can search it for dictionary words, and process them as if they were one symbol.
   • For music, you can synthesize a sound from the previous data, and encode the difference between the real sound and synthesized. Small difference is expected to be frequent.
   • For video, it is common to construct a frame with pieces of previous frames, and then encode the difference. Again, small difference is expected to be frequent.

2. Count the probabilities

3. Use one of entropy coding algorithms to assign binary codes according to probabilities.

You can use this plan to design your own custom compression schemes.

Why prime factoring is a bad compression

1. To store primes require as many bits as storing the original number, if not more. When you multiply two numbers of exactly X and Y bits - you get a result of either (X+Y) or (X+Y-1) bits. In first case you get no compression, in the second case - you actually get larger by 1 bit!
2. But your problems don't end there - you now have to store separators between primes! An ideal separator has a length of , where X is a length of a thing it separates. So, we again gain some bits.
3. But what if instead of storing primes, we would store an index of that prime in a prime list? Good news - it actually shaves some bits! Bad news - we only recover some bits we lost on stage 2: prime counting function is approximately . In bits, it would be

As you can see, factoring the number into primes has no compression benefits.

Can prime factoring compress at least something?

There is a rare case, when prime factoring can actually achieve compression. When a number contains the same prime multiple times - we can store a number of repeats instead of that prime multiple times.

Unfortunately, this case is very unlikely - prime powers are quite rare, and they are even more rare for big primes or big powers. The chance that a random file contains a big prime power is almost zero.