Timeline for How to solve Diophantine equations in $F_{p}$?
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 7, 2010 at 1:08 | comment | added | Victor Miller | To amplify on what Bjorn said -- if you have one solution you can use it to rationally parametrize all others via pencils of line. So the real problem is there a fast (i.e. polynomial time algorithm in log of the size of the finite field) algorithm to find one point. It turns out that if you are given a quadratic non-residue (generator of the 2-sylow subgroup of $F^*$) then there is a deterministic poly time algorithm to find a solution. This is still an open problem but van de Woestijne found a clever way around this for diagonal forms. | |
| Apr 7, 2010 at 0:09 | comment | added | Bjorn Poonen | @Pencil: Think about the analogous situation of rational solutions to x^2+y^2=1. If you draw a line of rational slope through (-1,0), it will intersect the circle in two rational points: finding them involves solving a quadratic equation for which you already know one rational solution. The same idea applies to degree 2 equations over any field, the only caveat being that sometimes the quadratic equation to be solved is the equation ax^2+by+c=0 where a,b,c are all zero (which means geometrically that the line is contained in the hypersurface defined by the degree 2 equation). | |
| Apr 7, 2010 at 0:00 | comment | added | Bjorn Poonen | @Pete: Good point! I forgot to write the words "polynomial time" (not to mention "over finite fields"!) It's fixed now. | |
| Apr 6, 2010 at 23:57 | history | edited | Bjorn Poonen | CC BY-SA 2.5 |
polynomial-time, over finite fields
|
| Apr 6, 2010 at 23:37 | vote | accept | Kerry | ||
| Apr 6, 2010 at 23:36 | vote | accept | Kerry | ||
| Apr 6, 2010 at 23:37 | |||||
| Apr 6, 2010 at 23:35 | comment | added | Kerry | I don't really understand the part "the other solutions can be found by drawing lines through the point and intersecting with the quadric hypersurface: there will either be one more intersection point, or a whole line of points", I will read the paper. | |
| Apr 6, 2010 at 23:07 | comment | added | Pete L. Clark | Sorry for the impertinent remark, but a deterministic algorithm for finding all solutions to an equation in the variables $x_1,\ldots,x_n$ over $\mathbb{F}_q$ is obtained by plugging in all $q^n$ possible values and counting how many give solutions. I can well believe the van de Woestijne's algorithm is better than this, but can you say exactly how? | |
| Apr 6, 2010 at 22:03 | comment | added | Kerry | Hi! I really thanks for the link of the paper. I will read it. | |
| Apr 6, 2010 at 21:45 | history | answered | Bjorn Poonen | CC BY-SA 2.5 |