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

Ṁ9.8K

Ṁ1K

resolved Jan 6

Resolved

ALL

Unlike the other prime factorization markets, which have been for semiprimes, this market will be for a completely random 250-digit natural number, to be chosen by me using the Manifold built-in random number generator (or if that doesn't work, random.org) one day after this market goes live.

Get Ṁ200 play money

🏅 Top traders

#	Name	Total profit
1		Ṁ431
2		Ṁ343
3		Ṁ322
4		Ṁ299
5		Ṁ289

25 Comments

44 Holders

178 Trades

Sort by:

i turned off cado-nfs, it takes a while to factorize such bis-ass numbers, but we don't know this number to be semiprime, what if i find smaller factors with old boring sympy? that would make the remaining number feasible to do with cado-nfs maybe?

Not sure yet, but I will probably give up on factorizing this. Looks like it might take a while.

Another one is 26769398086258498369453.

Current progress:

```
7 * 26769398086258498369453 * 51791060666743041244506730040838187584110309989768404712677057871256748104969409191511634445014640751308378729092909686321275325084909963584183228905405182761338306380398398257091880053261025683766065285804817823369571471066537
```

(227 digits in the number left to factorize)

One of the factors is 7^1, so the remaining number is 1386415520297608956879111996355171798158633019844881277122852122646255647554033418080860094521557104882367390765268631851027113636064455936090695962095478346838685751340019886468302642133898447084778379268222415499162184442361506729934228381371294261.

This should be correct the number is

predicted YES

@BoltonBailey 9704908642083262698153783974486202587110431138914168939859964858523789532878233926566020661650899734176571735356880422957189795452451191552634871734668348427870800259380139205278118494937289129593448654877556908494135291096530547109539598669599059827

Ok here is the link and the number is

@BoltonBailey Er, this is 10 strings, hold on a moment

@BoltonBailey your random number is: 156420523076475

Salt: TDtsPwGVUlrk0kKKgaiK, round: 2567298 (signature add01e97cca2d68494b97fa5f17dc0de108382838282c950c97d336b4a7642f0918964e605df9e66bd77d1579403258703a73ac5795b728dc77d8591cd25b41eb6a7fba6ae216a5e026bd513e4cfb45b0bcc73c294c60a63e6b4f828707374cc)

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

Source: GitHub, previous round: 2567296 (latest), offset: 2, selected round: 2567298, salt: TDtsPwGVUlrk0kKKgaiK.

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

bought Ṁ20 of NO

https://manifold.markets/AmmonLam/will-someone-find-the-prime-factori-e9dd2c3f4565 currently at 41% while this harder one is at 78%

predicted NO

@yaboi69 It's not necessarily harder. This one is a random integer, as opposed to a semiprime.

Another market with a bigger number

bought Ṁ25 of NO

Per https://math.stackexchange.com/questions/375270/size-of-largest-prime-factor

I expect this will be about as hard as factoring a .2325*250*2 ~= 116-digit number, which manifold thinks it can do

Not sure about the math:

is factoring a number with second-largest-prime-factor with N digits about as hard as factoring the product of two N-digit primes?
If that's true, how would I take this expectation value and turn it into a probability distribution?

But that's enough that I don't want to be holding NO
(lost M$7 on what I think was a premature understanding)

@citrinitas What from that link suggests to you that this is the probability level?

@citrinitas In fact part of the point of this question is that for large enough values of 250, the market should in theory not be at 100% or 0% until the number is known, let me make another market with a bigger number.

@BoltonBailey oh I guess you are looking at the second answer

bought Ṁ5 of NO

I was looking at this math too, and I think this is a reasonable approach - my initial guess was also that the second-largest prime should be a reasonable first-cut proxy for the difficulty of factoring.

predicted NO

@jack I don't understand this math. The second largest prime factor of a 116 digit semiprime has ~58 digits, not 116.

If the second largest prime factor of this number has 116 digits, wouldn't it be roughly equivalent to factoring a 232 digit semiprime?

predicted NO

@Lorenzo It's already accounted for in the *2 part of the math above. The second largest prime factor of a 250-digit number is expected to have about .2325*250 = 58 digits. Then we multiply by 2 get that it's roughly equivalent to a 116 digit semiprime.

@NeonNuke your random number is: 134793211691492

Salt: wXuvhY7Ac166SeIXDjs2, round: 2564303 (signature 80b42d5d6dba7db533f502cf2d869fa4fd457d48f2d95e5eef133419488995ce5444d1c33c2f38195ccc16cd4f0f18b20b815d46d88ee6ee839777abb23dcfe7e5e362327351b727a5694fd67fd15f21faeac1ffabbe3ac7ded2db87d5b0948a)

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

Source: GitHub, previous round: 2564301 (latest), offset: 2, selected round: 2564303, salt: wXuvhY7Ac166SeIXDjs2.

bought Ṁ10 of NO

@FairlyRandom max=281474976710656

@BoltonBailey your random number is: 1

Salt: TLn93b5rvz5EiKjJHro9, round: 2564291 (signature 8b0d1a24f0a3834b90b9bbd8e868280e892946bfae8622ae8f8f754cd9ba077224d659b43787d79586b2eb60dd9a74180098f6a6d54a1b78b3113da7b2e00a0e7a66ae919032c5f7559d0b44044dbb98c986131251cec31cf56d1f294d5ebc25)