There are a few important observations about Shanks' SQUFOF algorithm. First, in the original continued fraction expansion, we started with pseudo-square . However, it is possible to start with any integer such that is a quadratic residue of , so that can be found such that . If we choose , and or , such that is odd, then we have . In Theorem 2 of section 6, I prove that if and is not a quadratic residue, then this sequence of pseudo-squares and residues will provide a factorization of . However, this is not a complete description of the numbers that this sequence provides a factorization for. For example, for , a factorization is immediate when we evaluate , even though and , for which a factor of is found on the 2nd step but for which is a quadratic residue.

Figure 3 provides an example of applying this shortcut normally. Although performing SQUFOF without the shortcut would take about the same number of steps in this example, the time saved is more significant for many other numbers. Also observe that if we continue the expansion after the factorization is obtained, the sequences repeat, except in the opposite order and paired differently (Figure 4). After inverting, this last fraction will be the same as the fraction we started with, so the entire process repeats from here. Lemma 3 defines this symmetry more explicitly.

Based on this symmetry, any fast test to determine whether or not the continued fraction expansion is in the correct direction, that is, whether or not it has not passed the factorization yet, would provide a faster factorization algorithm by performing a binary search (Figure 5).

I provide one example of this algorithm:

, ,

Letting the indices refer to the related step in the standard continued fraction expansion we obtain^{5}:
.

We proceed by using NUDUPL to perform composition of quadratic forms, reducing the results by use of the continued fraction expansion.

, which is in the wrong direction.

and
are reversed.

Converting back to continued fractions:

we obtain the factor :

The decisions for this example of whether or not a form was reversed were determined by merely comparing with the actual continued fraction expansion. However, ideally this can be done without doing the entire expansion.

I conjecture based on empirical evidence that in the process of expanding the continued fraction expansion that if , , and is not a power of , then the continued fraction expansion is in the correct direction, that is, it has not passed the factorization yet. If or is a power of , no information is provided. As an intuitive explanation of where this conjecture comes from, observe that this always happens in Shanks' SQUFOF algorithm if you reverse the step (same as not taking the conjugate of the numerator according to Lemma 2). In the first example, if we had ignored we would have found on the 8th step, with . Taking the square root of and not taking the conjugate of the numerator, and then inverting, we obtain , so that , and .

The condition that is extremely rare, but it is possible to find a multiple such that in the expansion with unchanged, replaced by and replaced by , this condition is met. For notation, let . Since using instead of produces the same sequence in the opposite direction, it is necessary to relate this sequence to the original sequence in order to extract useful information. From this, I have found so far that if and , then the original expansion is in the correct direction. Finding multiples such that the second condition is satisfied can be accomplished by using continued fractions to find the convergents of , where .

Although most of the multiples do not cause the sequence to satisfy the first condition, it empirically appears to be possible roughly of the time, regardless of the size of . If this is true, even this crude result could provide a polynomial time factorization algorithm, a very significant discovery, by merely attempting the test an average of times for each test. Thus, the runtime would be roughly . However, polynomial time factorization could be possible even without this frequency of response, since all that is required for polynomial time factorization is that the time required for this test of direction be a polynomial function of the number of digits. In other words, the frequency with which the test provides an answer needs to be bounded below by the reciprocal of a polynomial. Even if this were not possible, it is hopeful that the algorithm would provide a valuable tool to number theory.

David Joyner, wdj@usna.edu, 2004-02-23