Will someone find the prime factorization of a 1000-digit random number in a week?

Ṁ4.2K

Ṁ450

resolved Jan 6

Resolved

ALL

Unlike the other prime factorization markets, which have been for semiprimes, this market will be for a completely random 1000-digit natural number, to be chosen by me using random.org one day after this market goes live.

Get Ṁ200 play money

🏅 Top traders

#	Name	Total profit
1		Ṁ36
2		Ṁ33
3		Ṁ18
4		Ṁ14
5		Ṁ12

17 Comments

19 Holders

51 Trades

Sort by:

Another one is 15653718611933.

Current progress:

11 x 19853 x 15653718611933 x 318121106057622787788194362736808052194802936828152297069303172117856444015852742531290092225149516366447739264877856555276248778164698443650098053660129377111472196818374143498647923153083758833612654886850758039787723030644440235214407249293071523195465284627808070248397570720008573707872589664011073912682796447196950674342108714113601895549831323575420249670857737934023545851914051255341903370813482425889735368353156497719534651505251470774178968910630093151922245832437169848660148489240423251587220908969298795062392429717286034981680554326982537079383932032487818296136353252160682395247908416356961285523760168271155139554153485656099178485839074194340367576735443813473566874977550031517897571172962983559952969113776346451522997199264545107513530224523645827620072927124209093053389994246732864012542699025932963882701872736475041800765182540350625962434770836713300904819040290969680818146386411587613166360673571772409632085166590911683161448382937604719963106808999

(981 digits in the remaining number)

PS I don't understand how to format this thing, when I use asterisk, Manifold things it should be cursive

predicted NO

@wadimiusz Are you using cado-nfs, or something else? (I’m clueless, just skimmed a little about tools.)

@yaboi69 Nah, just python's sympy module. It's sympy.ntheory.factorint function turns out to have a verbose argument, which is nice! It shows you the progress as it tries to decompose this number.

@yaboi69 but cado-nfs sounds better actually, let me try it

predicted NO

@wadimiusz I see there are few other implementations of that GNFS magic, not sure if they produce fun intermediate output, this one is apparently notable after RSA competitions

@yaboi69 Alright, I'll turn off sympy for the thousand-digit-number and try my luck with cado-nfs and the 250-digit one. (One thing I don't like i that it doesn't seem to show factors as it goes along, it just outputs all at the end of its work, which is lame I think)

@wadimiusz the number field sieve doesn't have any "as it goes along". It only gets one answer at the very end (and I recommend having some idea when "the end" is if you can so you don't say, try to run it on one core on a number that will take it 10 years).

@SeraphinaNix I see. I tried to understand the techinique, but it seems way above my current command of mathematics. The cado-nfs tool does indeed output an ETA as it progresses, and it doesn't look like it will be there even in a week, even for the 250-digit number. But the ETA seems to become shorter, so maybe the initial ETA was too pessimistic? Not sure

predicted YES

There is another factor. Current progress:

```11 * 19853 * 4979778278742921663569523683064842441809888042402056061436817915348285562703193717064237575286423042649176570859389702535247205911095490560595938322479985383222590457789841876477512723882163549997385215159176417316314715745234143021244247073047312259589408847924100507941081375248741813812258433309741510773581611645544634638632822338266555790881263236311311649314839489574095339306762802387989275785100639904840557872809869387621353644899479942147287526113429662902526786922882368509803299288846265247349330126231926483956403059044202011129357807962991077338624548366378826479327076767313267557218158610716800247070814308160341139504142405969426458042730449194243499027844150395410155425360023029909403968868106189670897290562465091122942681791899241648847364595246927000869394973671006629592168853400078023970673547298120746560236581522073707636772105972812767403812093143130681635662460334107112451222507696797104801339958113164121356550893187925098591020470095869197928713493134047233185067```

Among its factors is 11^1.

The remaining number is 98863538167883223786845753679886316997251707305808018987705146073409513276346504864876308582161356665714102461271463764432262778952978774099511163516195149813118088358501730773708060107232592958098088676555129412980796051690133441400762037141208290289628533857837167384154288542813271229614766676498298213387915735998997631480777421881605932116365719030488470173847508386514514771257161915808751092161603004030799595448894336952446733912189375291450099255929919097603864300779983662025124900781464903955626250996082436485986469931204542526951140561489261858403713158717718842094080455061470300813452102898560635305096876459907252642575739185711023471522327607853316186199789917800077815659672537212791396993938512183536323909536619454063781061614575644454566729309437241748260098412290494617293328246551749009889781934509591181460376852957729317712836619878251871267881485170573422512806825013028503494120445304512921621002188420647301291604882459876982327529392813291186478748979190239720423135151

Ok the link is here and the number is

predicted YES

@BoltonBailey As a number 1087498919846715461655303290478749486969768780363888208864756606807504646039811553513639394403774923322855127073986101408754890568482766515094622798678146647944298971943519038510788661179558522539078975442106423542788756568591467855408382408553291193185913872436208841225697173970945983525762433441481280347267073095988973946288551640697665253280022909335373171912322592251659662483828781073896262013777633044338795549937837706476914073034083128205951091815229110073642507308579820282276373908596113943511888760956906801345851169243249967796462546176381880442440844745894907263034885005676173308947973131884166988356065641058979779068333131042821258186745603686386478048197689095800855972256397909340705366933323634018899563004902813994701591677760332089000234022403809659230861082535195440790226610712069239108787601279605502996064145382535022494841202818660770583946696336876307647640875075143313538435324898349642137831024072627120314207653707058646805602823320946203051266238771092636924654486661

@BoltonBailey your random number is: 10711977686400

Salt: 5DIfdsx1UJPkHmSlTSWF, round: 2567303 (signature 875d9bae472b6d1581d7b25f67a30ca30ad721793f9a2221cc02b7da7f5d48ec9e9f1cc54e43c71100b6b89d070c302315edc086e91c8de1b67ceeb140159390e277a18367aa21ce4a7a4e503836d86b05b7f1245551e730ed0c8810f1119ba5)

@BoltonBailey you asked for a random integer between 1 and 281474976710656, inclusive. Coming up shortly!

Source: GitHub, previous round: 2567301 (latest), offset: 2, selected round: 2567303, salt: 5DIfdsx1UJPkHmSlTSWF.

It's been brought to my attention that the randomness bot has a maximum of 281474976710656, so in the interest of generating a number which is still certifiably random, I'll use the bot to generate a seed for random.org to generate 25 strings of length 10 of digits. If the first digit is 0, I'll use the bot to replace the digit.

@FairlyRandom max=281474976710656

@BoltonBailey *100 strings

bought Ṁ20 of NO

Same math as https://manifold.markets/BoltonBailey/will-someone-find-the-prime-factori-f081a7336797#dUveaDmaqJLSpNgCfOQp
Apparently the expectation value for the second largest prime for a random 1000-digit number is about 232 digits, if stack exchange is to be trusted.
So, factoring a random 1000-digit number is (in expectation) about as hard as factoring a 464-digit number that is the product of two 232-digit prime numbers.

It could be that, despite this expectation, there's still a large chance that all the prime factors of a random 1000-digit number are small. I think this is likely not the case, but that's just a guess.