guess_number3

懒得贴交互的图了

非预期

先说说非预期吧，这个我确实是疏忽了，也导致过的大部分人都是这么做的。
先从费马小定理定理出发:

费马小定理和欧拉定理类似,对于上面式子而言欧拉定理为 $2^{p - 1} = 1 (m o d p)$ ,因为 $p$ 的欧拉函数为 $p - 1$

$2^{p} = 2 (m o d p) 2^{p} = 2 + k * p (1)$

现在将式子变一下看看：

2^{p} = 2 + (- k) * (- p) 2^{p} = 2 - p + (- k + 1) * (- p)

即

2^{p} = 2 - p (m o d - p)

当输入式子为 $- p$ 时，绝对值加 $2$ 就是 $p$ ，即:

∣2 - p ∣ + 2 = p - 2 + 2 = p

对于 $(1)$ 而言有:

2^{p} - 2 = k * p

大家注意一下这个式子，只有在模

k * p

的因数下它才等于2，如果我模的是

p

的倍数，比如说

p^{2}

和

p^{3}

会发生下面这种情况

2^{p} = c_{1} + k_{1} * p^{2} 2^{p} = c_{2} + k_{2} * p^{3}

再给模

p

后

2 = c_{1} (m o d p) 2 = c_{2} (m o d p)

很神奇的事发生了，再对式子变一下形

c_{1} - 2 = k_{3} * p c_{2} - 2 = k_{4} * p

那么p即可得到：

p = g c d (c_{1} - 1, c_{2} - 2)

gcd是求最大公因数的意思，python里也有现成的函数，用不着自己实现,但我还是用的sagemath

输入 $p^{2}$ , $p^{3}$ 得到的 $c_{1}, c_{2}$ 分别减去 $2$ 后求最大公因数。

别的构造方法也是OK的，核心就是求最大公因数

请见guess_number3.5，这个是当时突然想到的，所以在比赛最后一天才出guess_number3.5，想用guess_number3.5看看过了guess_number3的有没有用这种方法。