The prime factors of N are both 2 mod 3, where N = 117968734185852909111122793179458044429748833609671492956099236663454458021167483523103665043186849896340566668709082216630299186083868726474403014230450576527498336056399517500373699648384503014218007972984281676376443077883955580519873153351211473492074726331214866950482499437571095445498914388647218496094203506927341398236714690311062488254644318997750013131645597009546941216705983462580669754031513
Basic
15
Ṁ7582resolved May 27
Resolved
NO1D
1W
1M
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)
This question is managed and resolved by Manifold.
Get
1,000and
3.00
1,0003.00Sort 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.)
@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).
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.
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 :)
@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.
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/
This is a fun read on the weaknesses of RSA: https://blog.trailofbits.com/2019/07/08/fuck-rsa/