The prime factors of N are both 2 mod 3, where N = 117968734185852909111122793179458044429748833609671492956099236663454458021167483523103665043186849896340566668709082216630299186083868726474403014230450576527498336056399517500373699648384503014218007972984281676376443077883955580519873153351211473492074726331214866950482499437571095445498914388647218496094203506927341398236714690311062488254644318997750013131645597009546941216705983462580669754031513

146Ṁ7582

resolved May 27

Resolved

ALL

N is a number that I generated by multiplying together two large primes. N = 1 mod 3, so therefore the prime factors of N must either: - Both be 1 mod 3 (question resolves to no) - Both be 2 mod 3 (question resolves to yes)

Math

Get

1,000

to start trading!

🏅 Top traders

#	Name	Total profit
1		Ṁ316
2		Ṁ271
3		Ṁ86
4		Ṁ2

16 Comments

13 Holders

58 Trades

Sort by:

Resolving this now, since the factors have been posted in the comments. I can confirm that: 1) I didn't trade in this market 2) The semiprime N was intentionally chosen to be weak. I did this by choosing nearby primes to be the factors, so that Fermat's factorization technique would work on N. (You can do this by choosing one prime at random, then counting up from that prime testing each number as you go until you hit another prime. As Jack has pointed out, some RSA implementations are infamously broken because they choose their prime factors in this way.)

I don't get it. Either somebody factored it successfully, or somebody's *really* misreading the question. Anybody care to explain?

predictedYES 2y

@ScottLawrence the OP has inside information and might be trading.

This is a true point, and I know you aren't saying that he is trading, just that he might be. I would actually be willing to bet (p ~ 70%) that the author is not insider trading on this market.

@jack Somebody is repeatedly purchasing M$1000 of NO. I don't think that's like to be OP, since OP's account is young and they shouldn't have made that much profit. I'm at a loss for what's going on. I guess I shouldn't believe 50% any more.

@ScottLawrence @misha I factorized the number a few days ago. Its prime factors are: 10861341270112679279209781084408132616664706478573420052059037429148686463594724858314951476988493373099046499260459317377023017937899389743308115414828330515658528697949593561502079826641023499547704029 and 10861341270112679279209781084408132616664706478573420052059037429148686463594724858314951476988493373099046499260459317377023017937899389743308115414828330515658528697949593561502079826641023499547708397 You can verify that these are the prime factors and that they are 1 mod 3 on any Unix system using bc (set scale=0 for the modulo operation, %, to work as expected).

@NuñoSempere Welp. I should not have assumed so blithely that the number was too large to factor!

predictedYES 2y

I actually also factored it - I was the first NO bet :) This is actually quite interesting, because N actually is too large to factor! N has about 400 digits, which is about 1300 bits. 1024-bit RSA is considered slightly weak, but that just means that people are worried it might be broken in a few decades, nobody is close to breaking it today. The record is an 828 bit key has been broken with approximately 2700 CPU years of compute. Obviously, that isn't what happened here. However, if you blindly choose prime factors for RSA, a lot of them will be very very weak! RSA implementations include a lot of conditions for the primes they will use to make sure they avoid the known weaknesses. I don't know exactly how the author chose these primes, but evidently they were very weak to standard factorization algorithms. My story is I figured I should at least make a cursory attempt to factor this. I googled "integer factorization calculator", clicked on the first result https://www.alpertron.com.ar/ECM.HTM (ECM is a factorization algorithm), plugged the number in, and in less than a second it gave me the factorization, which I then double-checked by multiplying it out in python.

predictedYES 2y

I suspect that the author deliberately chose a weak semiprime because that is what made this a fun market. It would have been boring if everyone just said "yeah, 50% is the right probability". On that note, there is a number theory result that says that randomly chosen primes are 1 and 2 mod 3 with equal probability. https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions

@jack I also made a cursory attempt, but my cursory attempt consisted of using the unix `factor` command for ~20 hours. Whoops. Well done both of you :)

predictedYES 2y

@ScottLawrence Oh, that's pretty interesting to hear. I looked it up and it seems like the unix factor command uses https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm which I guess is good for factoring small numbers but not intended for something like this.

predictedYES 2y

I was also really surprised that I was able to factor it so easily. Will be curious to hear from the author about how they generated the primes.

predictedYES 2y

@jack cool, it seems that N + 2184^2 is a full square...

predictedYES 2y

Oh right, I just remembered that I had noticed the two prime factors were _extremely_ close. I had vaguely recalled that was weak, and just found a description of the attack: https://fermatattack.secvuln.info/

predictedYES 2y

This is a fun read on the weaknesses of RSA: https://blog.trailofbits.com/2019/07/08/fuck-rsa/

Did you choose the two large primes at random?

🏅 Top traders

Related questions

Related questions