Cunningham's table

factorization number theory randomized

In 1925 Allan Cunningham and Herbert Woodall published tables of prime factorisations of numbers of the form b^k ± 1. They are still being extended: for base 2 the table now covers exponents up to 1500. You are to restore the start of the table yourself, for the numbers 2^k − 1 and 2^k + 1 with exponents up to a hundred.

The number 2⁶⁷ − 1 was factored by Frank Nelson Cole in 1903, and by his account it took “three years of Sundays”. You have a few seconds for the whole table.

Input

The first line holds the number of queries t (1 ≤ t ≤ 199). Each of the next t lines holds an exponent k and a sign, - or +: factor 2^k − 1 (2 ≤ k ≤ 100) or 2^k + 1 (1 ≤ k ≤ 100). All queries are distinct.

Output

For each query, the factorisation on a line: prime factors in increasing order separated by “ * ”, with a repeated factor written as p^e. For example, 2⁶ − 1 = 63 is written as 3^2 * 7.

Examples

Example 1

Input

Output

3^2 * 7
23 * 89
641 * 6700417
179951 * 3203431780337

Limits

Time · Python: 5000 ms
Time · Go: 3000 ms
Memory: 256 MB
Judging: 6 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Trial division up to the square root will not do: the smallest divisor of 2⁶⁷ − 1 is 193,707,721, and the second largest of 2⁹⁸ + 1 is more than ten billion. What if divisors are tried up to a million and the remainder declared prime?

2Hint 2

The remainder after trial division up to a million can be composite: 2⁶⁷ − 1 is a product of two primes greater than a million. Two things are needed: checking quickly whether the remainder is prime, and splitting it quickly if not. The time of the rho algorithm depends on the smallest prime divisor, not on the size of the number.

3The idea

The standard combination: trial division by a few small primes, the Miller–Rabin test for each piece and Pollard’s rho algorithm for each composite piece. A piece on which rho gave a divisor d is replaced by two, d and m/d, and they are processed the same way until only primes remain. The numbers here go up to 2¹⁰⁰, so Go will need math/big; in Python ordinary integers are enough.

4Walkthrough

Go through the queries and build n = 2^k ± 1. Divide by primes up to 71: this removes the most frequent factors and all even cases. Put the remainder on a stack. Take out a piece m: if the Miller–Rabin test says “prime”, it is a factor of the answer. Otherwise run rho in Brent’s variant with the mapping x ↦ x² + c: the tortoise waits at powers of two, the differences are multiplied modulo m in batches of 128, and the gcd is taken once per batch. If the gcd turned out equal to m, change c. The divisor found and the quotient go back onto the stack.

The hardest rows of the table are those where the second largest prime factor is large: for 2⁹⁸ − 1 it is 4,363,953,127,297, about 4·10¹². Rho spends about √p on it, a few million steps in the worst case and usually fewer in practice; trial division would need two trillion divisions.

It can also be sped up algebraically: if a divides k, then 2^a − 1 divides 2^k − 1, and 2^2k − 1 = (2^k − 1)(2^k + 1). The compilers of the tables did this, but within these limits rho copes without it.

4+Solution

5Complexity

For each number, a few Miller–Rabin rounds per piece and O(√p) rho steps per split, where p is the smallest prime divisor of the piece being split. The worst piece in the table up to a hundred is about 4·10¹², that is, about two million steps; the whole table fits in tenths of a second.

6Common mistakes

The remainder after trial division is not necessarily prime. 2⁶⁷ − 1 is not divisible by any number below 193,707,721. Trial division up to a million will pass it off as prime.
Printing gcd = m. Sometimes rho finds a cycle modulo all divisors at once, and the gcd equals the number itself. This is not a divisor; another c is needed.
Exactly one round of the primality test. The numbers of the table were not chosen by an adversary, but one base is still too few; a few bases cost next to nothing.
Overflow in Go. 2¹⁰⁰ does not fit in uint64.

Algorithms behind it

NUM Algorithm Pollard’s rho algorithm A divisor p of n in ~√p steps: a cycle modulo an unknown p, the tortoise and the hare, the gcd. O(√p) multiplications modulo n 1 problem NUM Algorithm The Miller–Rabin test Primality in k modular exponentiations: base-witnesses catch a composite, and liars make up at most a quarter. O(k log³ n) 2 problems