Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
The determinant must be nonzero mod $N$, or just over the integers? –  Brendan McKay Aug 11 '12 at 14:36
    
Just over the integers. –  Ng Yong Hao Aug 11 '12 at 14:48
    
This is problem 005:02, proposed by Peter Montgomery at the Western Number Theory meeting in December 2005. Online at ma.utexas.edu/users/goddardb/WCNT11/problems2005.pdf –  Gerry Myerson Dec 13 '12 at 6:17
    
@GerryMyerson Actually that was how I found this problem, I saw one of his posts online. Do you happen to know if there are any attempts on it? –  Ng Yong Hao Dec 13 '12 at 18:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.