SQUFOF, Continued Fraction Version

July 8, 2014

Square Forms Factorization, abbreviated SQUFOF, is a special-purpose method for factoring integers. It is commonly used to split small semi-primes in the double-large-prime variants of the quadratic sieve and number field sieve factoring algorithms. We studied the “binary quadratic forms” variant of SQUFOF in a previous exercise; today we study the “continued fraction” variant of SQUFOF.

Although the mathematical basis of SQUFOF is the quadratic forms of Gauss, SQUFOF was discovered by Daniel Shanks while he was investigating the failures of the continued fraction factoring algorithm; you should read his paper, which is as good a demonstration of the process of mathematical discovery as anything I have ever read. Shanks’ algorithm expands the continued fraction of the square root of n, the number being factored, searching among the convergents for a quadratic form that is a perfect square; in this, it differs from the CFRAC algorithm, which combines multiple convergents to assemble a perfect square. We copy the algorithm from the paper by Jason Gower and Sam Wagstaff that provides the standard description of SQUFOF:

[ Note: In the description that follows, be careful to distinguish the symbols and Q; the first one has a circumflex over the Q, the second one doesn’t. Some browsers render the “combining circumflex accent” readably, but some don’t. On the browsers available to me, only one out of four rendered the symbol readably, sorta kinda, and only when I expanded the font to be quite large. If in doubt, look at the program on the next page, where the first symbol is named qhat and the second symbol is named q. ]

The variable N is the integer to factor, S remembers q0, q holds the current qi, P and P’ hold two consecutive values of Pi, and Q hold two consecutive values of Qi, and t is a temporary variable used in updating Q. Finally, B is an upper bound on the number of forms tested for being square forms before the algorithm gives up.

1. Initialize: Read the odd positive integer N to be factored. If N is the square of an integer, output the square root and stop. If N ≡ 1 mod 4, then set D ← 2N; otherwise, set DN. In any case, set S ← ⌊√D⌋, Q̂ ← 1, PS, QDP · P, L ← ⌊2√2√D⌋, B ← 2 · L, and i ← 0.

2. Cycle forward to find a proper square form: Steps 2a through 2e are repeated for i = 1, 2, 3, ….

2a: Set q ← ⌊(S + P) / Q⌋ and P’q · QP.

2b: If Ql, then:

If Q is even, put the pair (Q / 2, P mod (Q / 2) onto the QUEUE; otherwise, if QL / 2, then put the pair (Q, P mod Q) onto the QUEUE.

2c: Set tQ̂ + q · (PP’), Q̂ ← t, and PP’.

2d: If i is odd, go to Step 2e. If Q is not the square of an integer, go to Step 2e. Otherwise, set r ← √Q, a positive integer. If there is no pair (r, t) in the QUEUE for which r divides Pt, then go to Step 3. If r > 1 and there is a pair (r, t) in the QUEUE for which r divides Pt, then remove all pairs from the beginning of the QUEUE up to and including this pair and go to Step 2e. If r = 1 and there is a pair (1, t) in the QUEUE, then the algorithm fails because we have traversed the entire principal period of quadratic forms of discriminant 4N without finding a proper square form.

2e: Let ii + 1. If i > B, give up. Otherwise, go to Step 2a.

3. Compute an inverse square root of the square form: Set Q̂ ← r, PP + r · ⌊(SP) / r⌋, and Q ← (DP · P) / Q̂.

4. Cycle in the reverse direction to find a factor of N:

4a: Set q ← ⌊(S + P) / Q⌋ and P’q · QP.

4b: If P = P’, then go to Step 5.

4c: Set tQ̂ + q · (PP’, Q̂ ← Q, Qt, and PP’ and go to Step 4a.

5. Print the factor of N: If Q is even, set QQ / 2. Output the factor Q of N.

Later, in Section 5.2 of their paper, Gowers and Wagstaff give instructions for using a multiplier m to help find a factor of N, changing the algorithm given above as follows:

Change Step 1 to this: Read the odd positive integer N to be factored. If N is the square of an integer, output the square root and stop. If mN ≡ 1 mod 4, then set D ← 2mN; otherwise, set DmN. In any case, set S ← ⌊√D⌋, Q̂ ← 1, PS, QDP · P, L ← ⌊2√2√D⌋, B ← 2 · L, and i ← 0.

Change Step 2b to: Let gQ / gcd(Q, 2m). If gL, put (g, P mod g) onto the QUEUE. [ Note: If you’re reading the linked version of the Gowers and Wagstaff paper, this formula is erroneously given as (g, B mod g); that error cost me several hours of pain. ]

In Step 5, replace Q by Q / gcd(Q, 2m) before the factor Q is output.

To find a factor, first use multiplier m = 1. If that fails, try another multiplier from the set 3, 5, 7, 11, 3 · 5 = 15, 3 · 7 = 21, 3 · 11 = 33, 5 · 7 = 35, 5 · 11 = 55, 7 · 11 = 77, 3 · 5 · 7 = 105, 3 · 5 · 11 = 165, 3 · 7 · 11 = 231, 5 · 7 · 11 = 385, 3 · 5 · 7 · 11 = 1155, or any other squarefree product of small odd primes.

Your task is to implement SQUFOF with multipliers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2

One Response to “SQUFOF, Continued Fraction Version”

  1. Jan van Delden said

    Step 2b (section 5.2) with multiplier m=1 does not reduce to the routine where multipliers are not used.

    This says (m=1):

    If Q is even: g=Q/2<L or Q<2L
    If Q is odd: g=Q<L

    In contrast to (no multipliers, main routine):

    If Q is even: Q<L
    If Q is odd: Q<L/2

    So I wonder whether section 5.2 should read:

    Change Step 2b to: g<-Q/gcd(Q,2m) g<=L/2 etc. instead of L.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: