Current Research

There are a few important observations about Shanks' SQUFOF algorithm. First, in the original continued fraction expansion, we started with pseudo-square $Q_0 = 1$. However, it is possible to start with any integer $Q_0$ such that $N$ is a quadratic residue of $Q_0$, so that $P_0$ can be found such that $P_0^2 \equiv N \pmod {Q_0}$. If we choose $Q_0 = 2$, and $P_0 = \left\lfloor \sqrt{N}\right\rfloor$ or $\left\lfloor \sqrt{N}\right\rfloor - 1$, such that $P_0$ is odd, then we have $x_0 - b_0 = \frac{\sqrt{N}-P_0}{Q_0}$. In Theorem 2 of section 6, I prove that if $N \equiv 1\pmod 4$ and $-1$ is not a quadratic residue, then this sequence of pseudo-squares and residues will provide a factorization of $N$. However, this is not a complete description of the numbers that this sequence provides a factorization for. For example, for $N = 35$, a factorization is immediate when we evaluate $\lfloor \sqrt{N} \rfloor = 5$, even though $35 \equiv 3\pmod 4$ and $377$, for which a factor of $13$ is found on the 2nd step but for which $-1$ is a quadratic residue.

Figure 3: example of first shortcut

8cm

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.

Figure 4: example of symmetry

8cm

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

Figure 5: intended algorithm using quadratic forms to perform a binary search of the continued fraction expansion

I provide one example of this algorithm:

$N = 2035153$, $Q_0 = 2$, $P_0 = 1425$
Letting the indices refer to the related step in the standard continued fraction expansion we obtain⁵: $F_2 = (1132, 839,-294)$.

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

$F_2*F_2 = (696, 1399, -28) = F_{11}$

$F_{11}*F_{11} = (81, 1403, -206) = F_{27}$

$F_{27}*F_{27} = (739, 545, -588) = F_{55}$

$F_{55}*F_{55} = (696, 457, -656) = F_{119}$

$F_{119}*F_{119} = (576, 1207, -251)$, which is in the wrong direction.

$F_{119}*F_{55}$ and $F_{119}*F_{27}$ are reversed.

$F_{119}*F_{11} = (24, 1415, -343) = F_{135}$

$F_{135}*F_2 = (246, 1019, -1013) = F_{140}$

Converting back to continued fractions:

$$\frac{2 \cdot 246}{\sqrt{N}-1019} = \frac{\sqrt{N}+1019}{2026} = 1+ \frac{\sqrt{N}-1007}{2026}$$

$$\frac{2026}{\sqrt{N}-1007} = \frac{\sqrt{N}+1007}{504} = 4 + \frac{\sqrt{N}-1009}{504}$$

$$\frac{504}{\sqrt{N}-1009} = \frac{\sqrt{N}+1009}{2018} = 1 + \frac{\sqrt{N}-1009}{2018}$$

we obtain the factor $1009$: $2035153 = 1009 \cdot 2017$

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 $Q_i\vert Q_{i-1}$, $(Q_i)^3 \nmid Q_{i-1}$, and $Q_i$ is not a power of $2$, then the continued fraction expansion is in the correct direction, that is, it has not passed the factorization yet. If $(Q_i)^3\vert Q_{i-1}$ or $Q_i$ is a power of $2$, 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 $16$ we would have found $49$ on the 8th step, with $x_8-b_8 = \frac{\sqrt{1353}-31}{49}$. Taking the square root of $49$ and not taking the conjugate of the numerator, and then inverting, we obtain $\frac{7}{\sqrt{1353}-31} = \frac{\sqrt{1353}+31}{56}$, so that $Q'_0 = 7$, $Q'_{-1}=56$ and $7 \mid 56$.

The condition that $Q_i\vert Q_{i-1}$ is extremely rare, but it is possible to find a multiple $k$ such that in the expansion with $Q_i$ unchanged, $P_i$ replaced by $kP_i$ and $N$ replaced by $k^2N$, this condition is met. For notation, let $Q_i = Q'_0$. Since using $-k$ instead of $k$ 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 $Q_{i+3}\vert Q'_1$ and $Q'_0\vert Q'_{-1}$, 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 $\frac{\sqrt{N}-R_i}{Q_i^2}$, where $R_i \equiv \sqrt{N} \equiv P_i - \frac{P_i^2-N}{2P_i} \pmod {Q_i^2}$.

Although most of the multiples do not cause the sequence to satisfy the first condition, it empirically appears to be possible roughly $2\%$ of the time, regardless of the size of $N$. 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 $50$ times for each test. Thus, the runtime would be roughly $c(\log{N})^{c'}$. 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.