8/ I just realized this can be simplified a little bit, you can choose k=n to get (7.8 choose 3) = 1 / P(24 tortoises beat all 3 teams of 5 hares)

7/ That works if t/m is an integer, *but it also gives the correct answer* when t/m isn't an integer! So it's a sensible way to combinatorially define binomial coefficients like (7.8 choose 3) =  (7 choose 3) / P(4 tortoises beat at least 3 out of 7 teams of 5 hares) = 51.272

6/ A troll solution: there are (n choose k) ways to pick the last k teams from hares. The tortoise team is t/m of a hare team, so there are ((n+t/m) choose k) ways to pick the last k teams from anyone, so P(tortoises beat at least k teams) = (n choose k) / ((n + t/m) choose k)

5/ That non-integer binomial coefficient ((n + t/m) choose k) is a bit weird - you can treat it as either (n + t/m) * (n + t/m -1) * ... * (n + t/m - k + 1)/k! or Γ(n+t/m+1)/(Γ(k+1)Γ(n+t/m-k+1)) But what does it actually *mean*?

4/ The remaining (n-1)*m+t participants can be permuted arbitrarily, so we can induct to get P(tortoises beat at least k hare teams) = prod_{i<k} (n-i)/(n-i+t/m) = (n)_k / (n + t/m)_k = (n choose k) / ((n + t/m) choose k) where (a)_k = a(a-1)...(a-k+1) is the falling factorial

3/ A real solution: The tortoises beat at least one hare team if and only if a hare comes last. This happens with probability nm/(nm + t) = n/(n + t/m). Remove that entire hare team.

2/ What's the probability that the tortoises win? More generally, what’s the probability that the tortoises beat at least k hare teams? I am told this has practical applications for Shapley values in game theory (cc @maxresnick)

1/ What does (7.8 choose 3) mean? A riddle, a real solution, and a bad but maybe not so silly solution: There are n teams of m hares, and one team of t tortoises. The participants race, and finish in a random order. Teams are ranked by their slowest member.

PS hmu if you're around for the Science of Blockchain conference!

9/ 128 bits seems just out of reach, maybe with some careful parameter tuning and enough time or with a more advanced factoooring method it can be done. I'd love to hear if anyone was able to make this work! cc @samczsun @paradigm_ctf

8/ How well does this work in practice? Since we can keep generating new numbers to factor, we can try until we find one with 'weak' enough primes. I was able to factor random products of two 110 bit primes a few times in python with this method (with the two stage variant).

7/ This is why using a 'strong prime' matters. The method is called 'Pollard's p-1 Algorithm'

6/ How can we find such a c? Remember from Fermat's Little Theorem that 2^{p-1} ≡ 1 (mod p), and so 2^k ≡ 1 (mod p) whenever p-1 divides k. So, if we multiply a bunch of small prime powers together, we might get lucky and have p-1 divide their product.

5/ Suppose that n = p*q and that we can find a number c such that c ≡ 1 (mod p) but c ≢ 1 (mod n). Then p divides c-1 and p divides n, so p divides gcd(c-1, n). Since p divides the gcd, and c < n, we must in fact have gcd = p, and we've found a factor!

4/ Two observations: (a) the runner generates new primes every run, and (b) the runner calls getPrime. From the documentation, there's another function called getStrongPrime that tries to ensure not all factors of p-1 are small. Why does this matter? https://t.co/FIqsNAJHEd

3/ I didn't solve the harder version. From what I've heard, the intended solution wasn't to actually factooor the number - but there is a weakness in how it's generated. How close can we get?

2/ First, the unintended backdooor solution - python's subprocess run leaks the FLAG environment variable, so we can read it with forge cheatcodes and base 256 encode it into the two uints that the runner helpfully prints for us:

1/ Trapdooors, Backdooors, and Maybe Actually Factoooring some paradigm CTF notes (pic related)

6/ Thanks to @wardbradt for discussion, and for help with forge and testing. cc @transmissions11, @boredGenius

5/ This gives us an initial estimate within a factor of ~3 of the true square root, which is still good enough that just seven iterations of the Babylonian method suffice.