-
题目分类：math
-
题目分值：200
某同学写了一个简单的计算器程序，支持加、减、乘、除、乘方、开方运算。
但是，计算器计算大数的时候会溢出，这位同学不想看到计算器溢出，于是他想了一个绝妙的方法。而更绝妙的是，这里的空间足够写下这个方法：
让计算器的所有计算都是在 mod n 意义下进行
出于某种众所周知的原因，他还用这个计算器算了一下 flag 字符串对应的整数的 65537 次方
公告：“flag 字符串对应的整数”指的是 flag 的 ASCII 编码按大端序转换得到的整数，例如 "abc" 对应 0x616263
这是一个在 mod n 意义下提供加减乘除和乘方开方运算的计算器。
flag 对应的字符串在 mod n 意义下计算 65537 次方，就是 e=65537 的 RSA 加密。
如果我们想解密 flag，需要对 n 进行分解。
我们知道，计算 mod n 的加减乘除和乘方，并不需要知道 n 的分解，知道 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 题改编的