Hastads Attack

[@DanielGoodrick]

@ 5:00, I didn't get where 559, 1603 and 433 came from WRT CRT. I also couldn't get the sum 15625.

[@JeffSuzukiPolymath]

These come from our solution to the Chinese Remainder theorem. This is a little hard to typeset in a KZbin comment, but I'll try my best here (I'm actually working on updating the cryptography videos, but the Chinese Remainder Theorem videos are a few weeks off...I do have an older version of the Chinese Remainder Problem available that might help: kzbin.info/www/bejne/pXywioGBl6t7eKc Roughly speaking, to solve: x = a mod p x = b mod q x = c mod r (where "=" is "congruent" and p, q, r are relatively prime), we need to solve a set of congruences; the 559, 1603, and 433 are the values that work to make the congruence true (that's the part that's rather hard to typeset). Notice that if we add the three factors together, then since the second and third are products of 629, the sum will have the same remainder mod 629 as the first. Likewise, because the first and third are multiples of 2173, the sum of all three will have the same remainder mod 2173 as the second; and so on. So the sum will solve the Chinese Remainder Problem.

[@metarealm]

@@JeffSuzukiPolymath i think it should have been 558

[@DSieh]

clear and neat

[@Swamy456]

The smallest solution is not 15625 it's 12018.

[@Jinzo-]

if you run crt from sympy module in python, it will show 15625 is the smallest solution