Timeline for Solving solutions to systems of polynomial equations over $\mathbb Z$
Current License: CC BY-SA 4.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23, 2018 at 2:45 | history | undeleted | user124864 | ||
| Oct 3, 2018 at 23:18 | history | deleted | user124864 | via Vote | |
| Oct 3, 2018 at 22:56 | history | edited | Turbo | CC BY-SA 4.0 |
added 246 characters in body
|
| Oct 3, 2018 at 22:52 | comment | added | Turbo | @FrançoisBrunault For me I need to look in $\mathbb Z$ and I posted $m$ thinking it could simplify. However being in Char $m$ other trivialities may arise. The formulation for factoring would be $x_1x_2-Nx_0^2=0$ and this does not look like amenable to producing two additional homogeneous equations so that $x_0=1$ and product of coordinates of roots $\neq0$ holds. Hope there is way to this formulation. | |
| Oct 3, 2018 at 22:48 | history | edited | Turbo | CC BY-SA 4.0 |
added 28 characters in body
|
| Oct 3, 2018 at 22:42 | history | edited | Turbo | CC BY-SA 4.0 |
added 28 characters in body
|
| Oct 3, 2018 at 22:35 | history | edited | Turbo | CC BY-SA 4.0 |
added 118 characters in body; edited title
|
| Oct 3, 2018 at 22:25 | comment | added | Turbo | @FrançoisBrunault I think we could think that way if it helps. | |
| Oct 3, 2018 at 16:49 | comment | added | François Brunault | It seems you are interested in the solutions in Z/mZ rather than in finite extensions. Solving systems of polynomial equations is a rather broad topic and there is abundant literature about it, you could start with en.wikipedia.org/wiki/… If you want to know about the complexity, you may want to specify what are the parameters (number of variables/polynomials, their degrees, the modulus $m$...). | |
| Oct 3, 2018 at 15:13 | history | edited | Turbo | CC BY-SA 4.0 |
deleted 19 characters in body; edited title
|
| Oct 3, 2018 at 15:08 | history | edited | Turbo | CC BY-SA 4.0 |
deleted 19 characters in body; edited title
|
| Oct 3, 2018 at 15:02 | history | edited | Turbo | CC BY-SA 4.0 |
deleted 19 characters in body; edited title
|
| Oct 3, 2018 at 15:01 | comment | added | Turbo | @FrançoisBrunault Oh I see then. Then I guess $O((\log m)^n)$ is unlikely if $m$ is non-prime. How does getting solutions in finite extensions help here? Is there illustrative example? | |
| Oct 3, 2018 at 14:43 | comment | added | François Brunault | $(x,y,z)=(p,q,0) $ is a common root. Regarding elimination theory, if one is careful enough it does provide the solutions in finite extensions e.g. finite fields $\mathbb{F}_p[x]/(T)$ where T is an irreducible polynomial. I now understand your concern is also about efficiency. It makes sense in Z/mZ since this is a finite object. | |
| Oct 3, 2018 at 14:11 | history | edited | Turbo | CC BY-SA 4.0 |
added 139 characters in body
|
| Oct 3, 2018 at 13:51 | history | edited | Turbo | CC BY-SA 4.0 |
added 190 characters in body
|
| Oct 3, 2018 at 13:44 | comment | added | Turbo | @FrançoisBrunault No definitely not my intent. Being a computer scientist I like to look at finite things and not infinite objects like $\overline{\mathbb F_p}$ and I think $\mathbb Z_m$ is right non-trivial object. | |
| Oct 3, 2018 at 13:42 | comment | added | François Brunault | It is reasonable to assume $m=p$ is prime to start with. In this case classical elimination theory (with resultants) will give you the common roots in $\overline{\mathbb{F}_p}$ (I'm not sure the most efficient method however). Regarding the equation $xy=0$, you can always artificially add variables e.g. consider $xy=xz=yz=0$, but I assume that is not what you intend. | |
| Oct 3, 2018 at 13:35 | history | edited | Turbo | CC BY-SA 4.0 |
added 50 characters in body
|
| Oct 3, 2018 at 13:33 | history | rollback | Turbo |
Rollback to Revision 2
|
|
| Oct 3, 2018 at 13:30 | history | edited | Turbo | CC BY-SA 4.0 |
added 11 characters in body
|
| Oct 3, 2018 at 13:28 | history | undeleted | user124864 | ||
| Oct 3, 2018 at 13:28 | history | deleted | user124864 | via Vote | |
| Oct 3, 2018 at 13:17 | comment | added | François Brunault | If you have one homogeneous polynomial in two variables, say $f(x,y)=xy$, then findind the non-trivial roots mod $m$ amounts to factor the integer $m$. Maybe you could clarify your setting and what you wish to know. | |
| Oct 3, 2018 at 12:35 | history | edited | Turbo | CC BY-SA 4.0 |
deleted 8 characters in body
|
| Oct 3, 2018 at 12:23 | history | asked | Turbo | CC BY-SA 4.0 |