CF1091G New Year and the Factorisation Collaboration

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

N/A

N/A

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