测试一下
\[(A−1)!≡ −1 mod A \]其中A为素数
1. 从代码中可以知道：
p=(B1!)%A1p=(B1!)%A1
q=(B2!)%A2q=(B2!)%A2
2. 又由[威尔逊定理]
(A−1)!≡ −1 mod
3. 而B=A-random.randint(1e3,1e5)，所以在B的前面补上
(A−1)(A−2)(A−3)...(B+1)
就有
(A−1)(A−2)(A−3)...(B+1)∗(B!)%A=−1
于是再整理一下又有
(A−2)(A−3)...(B+1)∗(B!)%A=1
这就意味这可由(A−2)(A−3)...(B+1)模A的逆元求得(B!)%A的值。
再取nextprime(sympy.ntheory.generate模块里的nextprime不是nextPrime)
即可得到p或q的值。
def get_p_q(A,B):
tmp = 1 # calculate remain value (mod A) of (A−1)(A−2)(A−3)...(B+1)
for i in range(B+1,A-1):
tmp *= i
tmp %= A
tmp_inv = invert(tmp,A)
result = nextprime(tmp_inv)
return result