Timeline for Solving modular polynomial equation modulo known factorization of a modulus is easy?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 18 at 22:03 | vote | accept | Mohammed Rahmani | ||
| Jan 17 at 21:59 | comment | added | hardmath | @Mark I'm familiar with Hensel lifting. It requires solving the base case, the polynomial modulo a prime. Sometimes a root exists, and sometimes it doesn't. In any case the OP should clarify if they have the entire solution process in mind or just the piecing together of solutions (modulo prime powers). | |
| Jan 17 at 21:59 | answer | added | Mark Schultz-Wu♦ | timeline score: 3 | |
| Jan 17 at 21:52 | comment | added | Mark Schultz-Wu♦ | @hardmath solving polynomial equations modulo prime powers is easy. The general technique is known as Hensel Lifting, and is a generalization of root-finding methods over $\mathbb{R}$ (Newton-Raphsom iteration) to modular integers. | |
| Jan 17 at 20:59 | comment | added | hardmath | In general $N \gt 1$ an integer will be a product of prime powers $p^k$. The procedure you presumably want explained is how to piece together the solutions of $f(x) \equiv 0 \bmod p^k$ into solutions of $f(x) \equiv 0 \bmod N$. This is generally easy, but it leaves the possibly difficult task of solving for solutions modulo certain prime powers. | |
| Jan 17 at 20:47 | history | edited | Mohammed Rahmani | CC BY-SA 4.0 |
added 3 characters in body
|
| S Jan 17 at 20:46 | review | First questions | |||
| Jan 18 at 9:42 | |||||
| S Jan 17 at 20:46 | history | asked | Mohammed Rahmani | CC BY-SA 4.0 |