New Year and the Factorisation Collaboration
Contest: Good Bye 2018
Difficulty rating: 3200
Tags: interactive, math, number theory

Integer factorisation is hard. The RSA Factoring Challenge offered $$$$100\,000$$$ for factoring RSA-$$$1024$$$, a $$$1024$$$-bit long product of two prime numbers. To this date, nobody was able to claim the prize. We want you to factorise a $$$1024$$$-bit number.

Since your programming language of choice might not offer facilities for handling large integers, we will provide you with a very simple calculator.

To use this calculator, you can print queries on the standard output and retrieve the results from the standard input. The operations are as follows:

- + x y where $$$x$$$ and $$$y$$$ are integers between $$$0$$$ and $$$n-1$$$. Returns $$$(x+y) \bmod n$$$.
- - x y where $$$x$$$ and $$$y$$$ are integers between $$$0$$$ and $$$n-1$$$. Returns $$$(x-y) \bmod n$$$.
- * x y where $$$x$$$ and $$$y$$$ are integers between $$$0$$$ and $$$n-1$$$. Returns $$$(x \cdot y) \bmod n$$$.
- / x y where $$$x$$$ and $$$y$$$ are integers between $$$0$$$ and $$$n-1$$$ and $$$y$$$ is coprime with $$$n$$$. Returns $$$(x \cdot y^{-1}) \bmod n$$$ where $$$y^{-1}$$$ is multiplicative inverse of $$$y$$$ modulo $$$n$$$. If $$$y$$$ is not coprime with $$$n$$$, then $$$-1$$$ is returned instead.
- sqrt x where $$$x$$$ is integer between $$$0$$$ and $$$n-1$$$ coprime with $$$n$$$. Returns $$$y$$$ such that $$$y^2 \bmod n = x$$$. If there are multiple such integers, only one of them is returned. If there are none, $$$-1$$$ is returned instead.
- ^ x y where $$$x$$$ and $$$y$$$ are integers between $$$0$$$ and $$$n-1$$$. Returns $$${x^y \bmod n}$$$.

Find the factorisation of $$$n$$$ that is a product of between $$$2$$$ and $$$10$$$ distinct prime numbers, all of form $$$4x + 3$$$ for some integer $$$x$$$.

Because of technical issues, we restrict number of requests to $$$100$$$.

Input format:
The only line contains a single integer $$$n$$$ ($$$21 \leq n \leq 2^{1024}$$$). It is guaranteed that $$$n$$$ is a product of between $$$2$$$ and $$$10$$$ distinct prime numbers, all of form $$$4x + 3$$$ for some integer $$$x$$$.

Output format:
You can print as many queries as you wish, adhering to the time limit (see the Interaction section for more details).

When you think you know the answer, output a single line of form ! k p_1 p_2 ... p_k, where $$$k$$$ is the number of prime factors of $$$n$$$, and $$$p_i$$$ are the distinct prime factors. You may print the factors in any order.

Hacks input

For hacks, use the following format:.

The first should contain $$$k$$$ ($$$2 \leq k \leq 10$$$) — the number of prime factors of $$$n$$$.

The second should contain $$$k$$$ space separated integers $$$p_1, p_2, \dots, p_k$$$ ($$$21 \leq n \leq 2^{1024}$$$) — the prime factors of $$$n$$$. All prime factors have to be of form $$$4x + 3$$$ for some integer $$$x$$$. They all have to be distinct.

Interaction format:
After printing a query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

The number of queries is not limited. However, your program must (as always) fit in the time limit. The run time of the interactor is also counted towards the time limit. The maximum runtime of each query is given below.

- + x y — up to $$$1$$$ ms.
- - x y — up to $$$1$$$ ms.
- * x y — up to $$$1$$$ ms.
- / x y — up to $$$350$$$ ms.
- sqrt x — up to $$$80$$$ ms.
- ^ x y — up to $$$350$$$ ms.

Note that the sample input contains extra empty lines so that it easier to read. The real input will not contain any empty lines and you do not need to output extra empty lines.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
We start by reading the first line containing the integer $$$n = 21$$$. Then, we ask for:

1. $$$(12 + 16) \bmod 21 = 28 \bmod 21 = 7$$$.
2. $$$(6 - 10) \bmod 21 = -4 \bmod 21 = 17$$$.
3. $$$(8 \cdot 15) \bmod 21 = 120 \bmod 21 = 15$$$.
4. $$$(5 \cdot 4^{-1}) \bmod 21 = (5 \cdot 16) \bmod 21 = 80 \bmod 21 = 17$$$.
5. Square root of $$$16$$$. The answer is $$$11$$$, as $$$(11 \cdot 11) \bmod 21 = 121 \bmod 21 = 16$$$. Note that the answer may as well be $$$10$$$.
6. Square root of $$$5$$$. There is no $$$x$$$ such that $$$x^2 \bmod 21 = 5$$$, so the output is $$$-1$$$.
7. $$$(6^{12}) \bmod 21 = 2176782336 \bmod 21 = 15$$$.

We conclude that our calculator is working, stop fooling around and realise that $$$21 = 3 \cdot 7$$$.

Example input:
21
7
17
15
17
11
-1
15

Example output:
+ 12 16
- 6 10
* 8 15
/ 5 4
sqrt 16
sqrt 5
^ 6 12
! 2 3 7

Editorial:
Most of the operations we're given are useless, as we can perform them on our own. However, we cannot perform the square root ourselves, so we should be able to use the information given us by the square root oracle to find the factorisation.
First let's solve the task for a product of two primes.
Select $$$x$$$ uniformly at random and assign $$$z = x^2$$$. Let $$$y$$$ be the answer to the query sqrt z. We have $$$$$$x^2 \equiv y^2 \pmod n$$$$$$ $$$$$$(x+y)(x-y) \equiv 0 \pmod n$$$$$$ For a fixed $$$x$$$, thanks to Chinese remainder theorem there are four solutions to this equation for $$$y$$$, two of them being $$$x$$$ and $$$-x$$$. If that is not the case, then as $$$p$$$ and $$$q$$$ are coprime, then $$$p$$$ divides one of the factors while $$$q$$$ divides the other. Hence, one factor can be computed as $$$\text{gcd}(x-y, n)$$$. Since we selected $$$x$$$ at random, the probability that the interactor returns $$$x$$$ or $$$-x$$$ is exactly $$$\frac{1}{2}$$$ and $$$2$$$ queries are needed in expectation.
Let's take a look what happens when there are more than two prime factors. Some of them will be accumulated in $$$x+y$$$, and the others in $$$x-y$$$. Collect all these values (again, after taking gcd of them with $$$n$$$) over multiple queries. We can find the prime factor $$$p_j$$$ if and only if for $$$i \neq j$$$ we have seen a value $$$t$$$ such that $$$\text{gcd}(t, p_i \cdot p_j) = p_j$$$. This is because we can take gcd of exactly all values containing $$$p_i$$$ as a factor and to get $$$p_i$$$.
We do not know which values contain the prime factor before we know the prime factor, but we simply calculate gcd of all subsets of retrieved values. Since gcd is a commutative and associative operation, and all values we get this way must be factors of $$$n$$$, we can perform this step in $$$\mathcal O(f \cdot 4^f)$$$ time, where $$$f$$$ is the number of prime factors of $$$n$$$. We can then a primality checking algorithm to check which of these are primes. Alternatively, we can just greedily pick the smallest of all values (except $$$1$$$) that is coprime to all the values that have been selected so far – this will always be a prime.
It remains to show what is the probability of success. We need each pair of primes to be separated at least once. The probability of that happening in one query is $$$1/2$$$. Over the course of $$$q$$$ queries, we have probability $$$2^{-q}$$$ that we are still unable to separate the two primes. Taking union bound over all prime pairs yields an upper bound on the error probability $$$4 * 10^{-14}$$$.
Implementation note: To find the square root, we use Chinese remainder theorem and find the square roots in the respective finite fields. The primes are of form $$$4x + 3$$$ for a simple reason – we can find the square root of $$$x$$$ modulo $$$p$$$ by simply calculating $$$x^{\frac{p+1}{2}}$$$. For primes of form $$$4x + 1$$$, we need Tonelli-Shanks, which empirically uses about $$$5$$$ modular exponentiations. With the number of queries and prime factors, and the size of the numbers, it was suddenly impossible for the interactor to fit into the time limit.