Small geometric progression modulo N - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T23:56:03Z http://mathoverflow.net/feeds/question/104444 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/104444/small-geometric-progression-modulo-n Small geometric progression modulo N Ng Yong Hao 2012-08-10T22:30:55Z 2012-08-10T22:30:55Z <p>An problem related to integer factorization using the <a href="http://en.wikipedia.org/wiki/General_number_field_sieve" rel="nofollow">General Number Field Sieve</a> is the following: </p> <blockquote> <p>Let $N$ be a composite. Must there exist a 5-term geometric progression $\lbrace a_0,a_1,a_2,a_3,a_4\rbrace$ (mod $N$) such that each term is $O(N^{2/3})$?<br> We also require that determinant $\bigl(\begin{smallmatrix} a_4&amp;a_3&amp;a_2\\ a_3&amp;a_2&amp;a_1\\ a_2&amp;a_1&amp;a_0 \end{smallmatrix} \bigr)$ is not zero.<br> What is known about such geometric progressions?</p> </blockquote> <p><strong>Some background (not needed to answer the question)</strong>: For factorizations using the Number Field Sieve, one would construct 2 polynomials $f(x)$ and $g(x)$ such that $f(m)\equiv g(m) \equiv 0$ (mod $N$) for some $m$. Usually, one of the polynomial will be of degree 1, the other ranging from 2 to 8 for practical purposes. There exists methods to construct 2 polynomials of similar degree, such that both are non-linear. The problem stated essentially gives one a way to construct 2 cubic polynomials. This method may have some advantages over the traditional linear case. </p> <p>Note that the problem do not ask how can one find the actual geometric progression, as that is believed to be hard and at the same time an open problem. </p> <p><strong>Motivation:</strong> I am posting this problem as the sources I read suggests that such series do exist by "counting argument". The part I am wondering about is: <strong>how does the counting argument work</strong>? </p> <p><strong>Initial Thoughts</strong><br> If I may humbly present some of my naive ideas:<br> We start off with $2*N^{2/3}$ possibilities for the first term $a$.<br> Next, since we seek a second term $b$ bounded by $O(N^{2/3})$, we similarly allow $2*N^{2/3}$ possibilities for it. However, this fixes the common ratio $r=ba^{-1}$ (mod $N$), whence we have no control over the 3rd, 4th and 5th terms.<br> We reason that such an $r$ must exist for each pair of $\lbrace a,ar \rbrace$, as failure would imply that $a^{-1}$ does not exist, which implies that we have found a factor of $N$. </p> <p>If we were to assume that the effect of multiplying by $r$ (mod $N$) results in a random permutation of the integer, the 3rd, 4th and 5th terms each have $(2*N^{2/3})/(2*N)=N^{1/3}$ chance of being bounded by $O(N^{2/3})$.<br> This gives us a grand total of $2*N^{2/3}*2*N^{2/3}/(N^{1/3})^3=4*N^{1/3}$ valid series. </p> <p>Suppose this line of thought holds, the difficult part is to account for determinant not zero. (This is stated as to ensure the series is not a second-order linear recurrence over $\mathbb{Q}$, which is a requirement for the Number Field Sieve to work.) It is clear that if the series is of the form $\bigl(\begin{smallmatrix} ar^4&amp;ar^3&amp;ar^2\\ ar^3&amp;ar^2&amp;ar\\ ar^2&amp;ar&amp;a \end{smallmatrix} \bigr)$ with $ar^4 &lt; N^{2/3}$, such that no modulo reduction happens, the determinant is zero by default. So in some sense the series "must exceed $N$ at some point". My guess is that if we remove all series without the modulo reduction then the remaining probability presumably will tell us that the geometric progression should exist. </p> <p>Is my argument sound? How does one go about counting the series to remove?</p>