# 永不溢出的计算器

这是一个在 mod n 意义下提供加减乘除和乘方开方运算的计算器。

flag 对应的字符串在 mod n 意义下计算 65537 次方，就是 `e=65537` 的 RSA 加密。

如果我们想解密 flag，需要对 n 进行分解。

我们知道，计算 mod n 的加减乘除和乘方，并不需要知道 n 的分解，知道 n 本身已经足够可以进行这些计算，所以这些计算并不能提供任何额外的信息。唯一可能可以提供额外信息的计算就是开平方的运算。

此时，搜索能力较强的同学可能已经找到了[这篇文章](https://crypto.stackexchange.com/questions/34061/factoring-large-n-given-oracle-to-find-square-roots-modulo-n)。

解法其实很简单。

首先我们通过计算 `0 - 1` 可以得到 n - 1 的值，从而知道 n。

当我们选择一个 0 ~ n 范围内随机的整数 x 后，我们计算 x ^ 2 mod n，然后发给服务器开平方得到 y。

每一个能够在 mod n 意义下开平方（二次剩余）的非零整数都有 4 个平方根，分别是 a、b、n-a、n-b。

如果我们拿到的 y 不巧是 x 或者 n-x 的话（1/2 的概率），我们没有得到任何有用信息，这时我们重试就可以。

如果我们拿到的 y 是另外两个数的话，此时我们有 x^2 = y^2 mod n，也就是 n | x^2 - y^2，也就是 n | (x+y)(x-y)。此时 x+y 和 x-y 都不是 n 的倍数，而 (x+y)(x-y) 却是 n 的倍数，说明 x+y 和 x-y 中分别包含一个 n 的真因数。此时计算 gcd(n, x+y) 即可得到 n 的一个真因数，从而分解 n。

最后，使用标准的 RSA 解密公式就可以解密得到 flag 了。

## 花絮

这道题是根据一道原理相同的 ACM 题改编的
