Small geometric progression modulo N

2012-08-10T22:30:55Z

An problem related to integer factorization using the General Number Field Sieve is the following:

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})$?
We also require that determinant $\bigl(\begin{smallmatrix} a_4&a_3&a_2\\ a_3&a_2&a_1\\ a_2&a_1&a_0 \end{smallmatrix} \bigr)$ is not zero.
What is known about such geometric progressions?

Some background (not needed to answer the question): 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.

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.

Motivation: 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: how does the counting argument work?

Initial Thoughts
If I may humbly present some of my naive ideas:
We start off with $2*N^{2/3}$ possibilities for the first term $a$.
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.
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$.

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})$.
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.

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&ar^3&ar^2\\ ar^3&ar^2&ar\\ ar^2&ar&a \end{smallmatrix} \bigr)$ with $ar^4 < 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.

Is my argument sound? How does one go about counting the series to remove?

Small geometric progression modulo N - MathOverflow

Small geometric progression modulo N