4 ms·

Can anyone provide a deeper (Algebraic? Number theoretical?) explanation of the polynomial/prime connection? I'd never heard of it before and it's interesting.

ljcn 8y ago
Think about units, tens, hundreds, ..., and stare at step 3 in the article.
daveFNbuck 8y ago
In their example of 1111, this binary representation means 2^3 + 2^2 + 2^1 + 2^0. So plugging in 2 to the polynomial x^3 + x^2 + x + 1 gives you the original value. If the polynomial is factored, plugging 2 in still gives you the same value, but now you have at least 2 integers that multiply to give you the original value, so you've found a factor.
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 ago
  But 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 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.
convivialdingo 8y ago
Here's my layman's take - basically it's similar to how computers convert binary integer representations to integers. For instance, a binary number of 0b1111 could be represented as 2^3 + 2^2 + 2^1 + 2^0 = 15, or 8+4+2+1=15. You now have a typical polynomial which can also be factored algebraically and quickly using something like Mathmatica. Not all of these binary conversion type polynomials can be factored however as they're irreducible. There's a lot of shifting around in big numbers when you compare the normal binary conversion and what is algebraically viable to be factored. In my conjecture - it's not clear to me the exact mathematical connection between the normal binary conversion and the perfect polynomial factors we're searching for. I believe it still may be possible to find these unknown polynomial factors by migrating some of the polynomial terms through redistribution of higher value terms and/or performing some sort of hard search. So instead of 2^4+2^1, you can rewrite as 2^3+2^3+2^1, for example. The factors are exponentially smaller and the search space is reasonable considering that it's basically possible to reduce the polynomial to a large matrix. I gave up on this path a year ago, so I may be a bit off in my recollection. I was using SymPy (a computer algebra system) but the speed was an issue.
- pdpi 8y ago
  > I believe it still may be possible to find these unknown polynomial factors by migrating some of the polynomial terms through redistribution of higher value terms and/or performing some sort of hard search. You start with a fairly obvious representation of the integer as a polynomial. If that doesn't give you some sort of factorisation, then any information that allows you a better guess at a factorable polynomial is also information that helps you outright factor the original number.
  - deleted 8y ago
    [deleted]
throwawaymath 8y ago
This is a half hour 3Blue1Brown video: https://youtu.be/NaL_Cb42WyY https://youtu.be/NaL_Cb42WyY If you're willing to watch at least the first half of it, I think it'll give you a very intuitive grounding for 1) why integers have unique polynomial representations, and 2) why that's related to (semi)prime factorization.
openasocket 8y ago
Essentially they are both integral domains: https://en.wikipedia.org/wiki/Integral_domain https://en.wikipedia.org/wiki/Integral_domain The space of integers and polynomials have a lot of things in common. They have well-defined addition and multiplication operations, they have a zero value and a one value (for integers it is literally 0 and 1, for polynomials it's the constant function returning 0 and 1, respectively) that obey the usual laws (x + 0 = 0, x1 = x, x0=0, etc). They also both have no zero divisors, i.e. if a*b = 0, then either a=0 or b=0. From just those basic notions you can define divisibility and factorization in a way that applies to both polynomials and integers. In a very deep way, any property or concept you define on the integers can (often, but of course there are exceptions) be extended to apply to polynomials. There might be some category-theoretic way to formally state that relationship, I'm not sure.

ljcn 8y ago

Think about units, tens, hundreds, ..., and stare at step 3 in the article.

daveFNbuck 8y ago

In their example of 1111, this binary representation means 2^3 + 2^2 + 2^1 + 2^0. So plugging in 2 to the polynomial x^3 + x^2 + x + 1 gives you the original value. If the polynomial is factored, plugging 2 in still gives you the same value, but now you have at least 2 integers that multiply to give you the original value, so you've found a factor.

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 ago
But 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 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.

convivialdingo 8y ago

Here's my layman's take - basically it's similar to how computers convert binary integer representations to integers. For instance, a binary number of 0b1111 could be represented as 2^3 + 2^2 + 2^1 + 2^0 = 15, or 8+4+2+1=15. You now have a typical polynomial which can also be factored algebraically and quickly using something like Mathmatica. Not all of these binary conversion type polynomials can be factored however as they're irreducible. There's a lot of shifting around in big numbers when you compare the normal binary conversion and what is algebraically viable to be factored. In my conjecture - it's not clear to me the exact mathematical connection between the normal binary conversion and the perfect polynomial factors we're searching for. I believe it still may be possible to find these unknown polynomial factors by migrating some of the polynomial terms through redistribution of higher value terms and/or performing some sort of hard search. So instead of 2^4+2^1, you can rewrite as 2^3+2^3+2^1, for example. The factors are exponentially smaller and the search space is reasonable considering that it's basically possible to reduce the polynomial to a large matrix. I gave up on this path a year ago, so I may be a bit off in my recollection. I was using SymPy (a computer algebra system) but the speed was an issue.

pdpi 8y ago
> I believe it still may be possible to find these unknown polynomial factors by migrating some of the polynomial terms through redistribution of higher value terms and/or performing some sort of hard search. You start with a fairly obvious representation of the integer as a polynomial. If that doesn't give you some sort of factorisation, then any information that allows you a better guess at a factorable polynomial is also information that helps you outright factor the original number.
- deleted 8y ago
  [deleted]

throwawaymath 8y ago

This is a half hour 3Blue1Brown video: https://youtu.be/NaL_Cb42WyY https://youtu.be/NaL_Cb42WyY If you're willing to watch at least the first half of it, I think it'll give you a very intuitive grounding for 1) why integers have unique polynomial representations, and 2) why that's related to (semi)prime factorization.

openasocket 8y ago

Essentially they are both integral domains: https://en.wikipedia.org/wiki/Integral_domain https://en.wikipedia.org/wiki/Integral_domain The space of integers and polynomials have a lot of things in common. They have well-defined addition and multiplication operations, they have a zero value and a one value (for integers it is literally 0 and 1, for polynomials it's the constant function returning 0 and 1, respectively) that obey the usual laws (x + 0 = 0, x1 = x, x0=0, etc). They also both have no zero divisors, i.e. if a*b = 0, then either a=0 or b=0. From just those basic notions you can define divisibility and factorization in a way that applies to both polynomials and integers. In a very deep way, any property or concept you define on the integers can (often, but of course there are exceptions) be extended to apply to polynomials. There might be some category-theoretic way to formally state that relationship, I'm not sure.