擅长:python、mysql、java
<p>下面是用python实现的两阶段版本。</p>
<pre><code>from math import gcd, log
def pminus1(n, B1, B2):
log_B1 = log(B1)
M = 1
primes = prime_sieve()
for p in primes:
if p > B1:
break
M *= p**int(log_B1/log(p))
M = pow(2, M, n)
g = gcd(M-1, n)
if 1 < g < n:
return True
if g == n:
return False
# Start part 2.
cache = {0:M}
S = (M*M) % n
for d in range(2, int(log(B2)**2), 2):
cache[d] = cache[d-2] * S) % n
HQ = M
for k, q in enumerate(primes):
if q > B2:
break
d = q - p
HQ = (HQ * cache[d]) % n
M = (M * (HQ-1)) % n
p = q
if k % 200 == 0:
if 1 < gcd(M, n) < n:
return True
return 1 < gcd(M, n) < n
</code></pre>