Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Indeed, having a fast way to multiply in Z[x] gives you a fast way to multiply in Z and vice versa. In the reverse direction, you can encode the polynomial f = 2x^2 + 6x + 3 as 30602, and 30602^2 = 936482404 tells you that f^2 = 4x^4 + 24x^3 + 48x^2 + 36x + 9 (of course, on a computer you do this in binary as opposed to decimal).

This correspondence is often exploited in both directions. If you ask a sufficiently sophisticated computer algebra system (SageMath, for example) to multiply two large polynomials with integer or rational coefficients, chances are that it will reduce the problem to multiplying two large integers, then reduce that problem to multiplying two large polynomials (but different from the ones you started with), and then proceed using recursive polynomial and integer multiplications to compute that product... (i.e. going through a sequence of transformations Z[x] -> Z -> Z[x] -> ...)



Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: