3 ms·
The way positional number systems work, each position corresponds to a power of the base — e.g. 415 = 4 * 10^2 + 1 * 10^1 + 5 * 10^0. A slightly more complicate
by pdpi 8y ago
The way positional number systems work, each position corresponds to a power of the base — e.g. 415 = 4 * 10^2 + 1 * 10^1 + 5 * 10^0. A slightly more complicated way to say this is 415 = 4 * x^2 + 1 * x^1 + 5, where x = 10. Ignore the x = 10 part for a bit, this is your polynomial. You can factor this polynomial normally without changing the fact that substituting x = 10 yields the original number. Because of this, it follows that the factors of the polynomial must also be divisors of the original number when you substitute the variable for the appropriate value!
- amelius 8y agoBut why is it useful to turn the base of the number system into a variable? Why go through polynomials when you can factor integers directly?
- pdpi 8y agoBecause 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.