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

Minimum And Maximum

July 4, 2014

We have today a two-part interview question:

First, write a program that takes an array of integers and returns the minimum and maximum elements of the array. Use as few comparisons as possible.

Second, write a program that takes an array of integers and returns the second minimum and maximum elements of the array; that is, the second-smallest element and the second-largest element. Again, use as few comparisons as possible.

Your task is to write the two programs described above, and state the number of comparisons each makes in the general case; be sure they are proof against malicious input. 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

Moonrise, Moonset

July 1, 2014

We have previously studied the times of sunrise and sunset and the phases of the moon. Today we look at the times of moonrise and moonset.

The standard source for astronomical calculations is the Naval Observatory; they point to a 1989 article in Sky & Telescope for the calculation. The article isn’t online, but the code is: a horribly ugly BASIC program, reproduced on the next page.

Your task is to write a program that calculates the times of moonrise and moonset. 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 3

Raindrops

June 27, 2014

We’re going to try something different today. We often have interview questions here, but always of the type that require writing a program. Today, we will have one of the brain-teaser type of interview question:

How many raindrops fall on the planet every year?

Your task is to estimate the answer to the question posed above. When you are finished, you are welcome to read a suggested solution or to discuss your solution in the comments below.

Pages: 1 2

Busy Beaver

June 24, 2014

Yesterday was Alan Turing’s birthday, so today we will write a program for a turing machine.

The Busy Beaver is a turing machine that performs the maximum work for a given configuration of machine; the concept was invented by Tibor Radó in his 1962 paper On Non-Computable Functions. We won’t look at the underlying theory, although it is fascinating if you have the time. Instead, we’ll be content to implement the first few busy beavers. Here are the two-symbol busy beavers for one, two, three and four states, from Wikipedia; the two symbols are 0 and 1, the states are letters A through D plus the halting state H, and the moves L and R are left and right:

  A
0 1RH
1 unused
  A B
0 1RB 1LA
1 1LB 1RH
  A B C
0 1RB 0RC 1LC
1 1RH 1RB 1LA
  A B C D
0 1RB 1LA 1RH 1RD
1 1LB 0RC 1LD 0RA

Your task is to implement the four busy beavers. 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

Birthday Paradox

June 20, 2014

The birthday paradox, which we studied in a previous exercise, states that in any group of 23 people there is a 50% chance that two of them share a birthday. The BBC recently published an article that shows 16 of the 32 World Cup teams, each consisting of 23 players, have shared birthdays, thus demonstrating the paradox precisely. Today’s exercise asks you to recreate their calculation.

You can obtain the same listing of player birthdays that the BBC used from FIFA. Another source is the player rosters at WikiPedia.

Your task is to demonstrate that the 2014 World Cup rosters honor the birthday paradox. 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

Collinearity

June 17, 2014

Beware: today’s exercise sounds simple but is actually quite complex if you don’t look at it properly.

Your task is to write a function that takes three points in the x,y plane and determines if they are collinear; be sure to handle vertical lines and horizontal lines properly. 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

Over at /r/math, Darksteve writes of “A problem I came up with, and haven’t been able to solve for many years:”

I would like to present a mathematical problem that I came up with some years ago, and haven’t yet found a solution for:

If you take all the numbers that contain the digits 1 to 9 exactly once, and you write down the prime factorization of all those numbers, which one has the smallest biggest prime factor?

To illustrate what I mean, the number 879456123 contains the prime factors 3 7 13 and 491; making 491 this numbers biggest prime factor.

The number 213456789 contains 3 7 13 and 197 as factors, making 197 the biggest prime factor. Out of all the numbers I’ve tried, 213456789 has the smallest biggest prime factor.

Many other number have much bigger biggest prime factors, like 576492813 which contains 3 13 19 and 13649.

But I have not found a way to actually solve this problem, as I am lacking the programming skills, or the algebraic knowledge required. I would therefore greatly appreciate anyone capable of solving this.

Your task is to solve Darksteve’s problem. 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

Balanced Delimiters

June 10, 2014

I heard today’s exercise as an interview question — you have five minutes to solve this task, while I watch — but it could equally be a homework problem:

Write a function to return true/false after looking at a string. Examples of strings that pass:

{}, [], (), a(b)c, abc[d], a(b)c{d[e]}

Examples of strings that don’t pass:

{], (], a(b]c, abc[d}, a(b)c{d[e}]

Your task is to write the function described above. 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

Remove Singleton

June 6, 2014

I’m not sure if this is a homework exercise or an interview questions, but it’s a fun little exercise to get your creative juices flowing on a Friday morning:

Given a string and a character, remove from the string all single occurrences of the character, while retaining all multiple consecutive instances of the character. For instance, given string “XabXXcdX”, removing singleton Xs leaves the string “abXXcd”.

Your task is to write the program given above; be sure to properly test your work. 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

Follow

Get every new post delivered to your Inbox.

Join 630 other followers