3 ms·
Because factoring integers is notoriously hard (which is why RSA is safe), but factoring polynomials is easier, and factoring a polynomial results in finding a
by pdpi 8y ago
Because factoring integers is notoriously hard (which is why RSA is safe), but factoring polynomials is easier, and factoring a polynomial results in finding a divisor for the corresponding integer. Crucially, this relationship is not symmetrical — compound polynomial guarantees compound number, but compound number doesn't guarantee compound polynomial — so the open question was: how often can you use this trick to make breaking RSA easier. What this result proves is that the attack is highly unlikely to work.