Timeline for Final step in Coppersmith?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 9, 2019 at 14:57 | comment | added | François Brunault | That's the idea, but you need to delve into the references mentioned in the wiki page if you want to see actual algorithms. That being said, I will let other people give references since I don't know what is the best one. | |
| Jan 9, 2019 at 12:27 | comment | added | Turbo | @FrançoisBrunault If you possibly post a precise reference for explicit algorithms to identify $0$ dimensionality and mathematical expertise needed then it will be nice. Thank you. | |
| Jan 9, 2019 at 12:25 | comment | added | Turbo | @FrançoisBrunault There is no explicit algorithm on wiki. It just gives general idea that we know and I have written above and so does not help. | |
| Jan 9, 2019 at 11:55 | comment | added | Turbo | $$\vdots$$ Keep proceeding till you get $x_1$. Looks like there will be $d_nd_{n-1}\dots d_2d_1$ possible choices of roots. Is this correct method or is there simplification? | |
| Jan 9, 2019 at 11:54 | comment | added | Turbo | @FrançoisBrunault So if I can reduce to univariate then I can find integer roots? It seems that if there are $n$ roots to be found and there and $n$ non-homogeneous equations then we have to reduce to $n-1$ equations in $n-1$ variables,$\dots$, $2$ equations in $2$ variables and $1$ equation in $1$ variable. 1. First we reduce to say $x_n$ variable equation of degree $d_n$ and get potentially $n$ solutions. 2. Then you substitute all possible solutions back in equation with two equations in $2$ variables solve for all possible $x_{n-1}$. $$\vdots$$ | |
| Jan 9, 2019 at 11:47 | comment | added | François Brunault | You could start here en.wikipedia.org/wiki/… The point is that it is easy to compute the integral roots of a univariate polynomial en.wikipedia.org/wiki/Rational_root_theorem | |
| Jan 9, 2019 at 11:38 | comment | added | Turbo | @FrançoisBrunault The way iacr.org/archive/eurocrypt2007/45150361/45150361.pdf defines in $2.6$ matches definition there. OK. Assume the polynomials have random coefficients in some bound. Then I believe they are algebraically independent as per definition in math.SE and irreducible with high probability. OK. Suppose they are algebraically independent as per definition and irreducible then what is the procedure to test $0$ dimensionality and find system integer roots? | |
| Jan 9, 2019 at 10:31 | comment | added | François Brunault | Algebraic independence is explained in the math.SE question. Otherwise, how do you wish to define algebraic independence of a system of equations? | |
| Jan 9, 2019 at 10:08 | comment | added | Turbo | @FrançoisBrunault Sorry example there uses $f_1=x_1+x_2$ and $f_2=x_2^2-x_2^2$. These are not algebraically independent as their gcd is $x_1+x_2$. | |
| Jan 9, 2019 at 8:16 | comment | added | François Brunault | This is not always the case, see here: math.stackexchange.com/questions/250824 Establishing 0-dimensionality is not obvious in general, but can be done using Gröbner bases or resultants. So if your system indeed is 0-dimensional, you can determine the algebraic solutions (and also the integral solutions, because there is an algorithm to compute the integer roots of a single-variable polynomial). Otherwise, the algorithm will fail. | |
| Jan 9, 2019 at 3:52 | comment | added | Turbo | @FrançoisBrunault Sorry I was under opinion if we had $n$ non-homogeneous algebraically independent polynomials in $n$ variables the common solution had to be $0$-dimensional. Am I wrong in this and if so what else I need to guarantee $0$ dimensionality? | |
| Jan 8, 2019 at 19:59 | comment | added | François Brunault | I mean, finitely many complex solutions (in other words, the algebraic set defined by your system is $0$-dimensional). | |
| Jan 8, 2019 at 19:07 | comment | added | François Brunault | I realize that for resultants or Gröbner bases to work, you need to assume that your system of polynomial equations has only finitely many solutions. Is it the case? Otherwise, your question amounts to find the integral points on some algebraic variety, which is hard even in the case of curves. So unless you provide more details, I cannot answer your question. | |
| Jan 8, 2019 at 15:16 | comment | added | Turbo | @FrançoisBrunaulth Thank you. If I need to compute integer roots what modifications I need? Is it possible for you to provide full post with references? I will appreciate it. | |
| Jan 8, 2019 at 14:18 | comment | added | François Brunault | Resultants are defined for polynomials over arbitrary rings and always give an upper bound for the set of common roots. Good methods for computing resultants exist but they are not straightforward (e.g. theory of subresultants, Gröbner bases...). | |
| Jan 8, 2019 at 4:42 | history | asked | Turbo | CC BY-SA 4.0 |