0

我遇到了一个问题：如果对 (p-1)/2 使用经典除法，那么 512 位奇数的代码会非常慢。但是使用楼层划分，它可以立即生效。是浮点数转换引起的吗？

def solovayStrassen(p, iterations):    
    for i in range(iterations):         
        a = random.randint(2, p - 1)         
        if gcd(a, p) > 1:
            return False        
        first = pow(a, int((p - 1) / 2), p)    
        j = (Jacobian(a, p) + p) % p                            
        if first != j: 
            return False 
    return True

完整代码

import random
from math import gcd

#Jacobian symbol
def Jacobian(a, n): 
    if (a == 0): 
        return 0 
    ans = 1 
    if (a < 0):         
        a = -a
        if (n % 4 == 3): 
            ans = -ans 
    if (a == 1): 
        return ans
    while (a): 
        if (a < 0): 
            a = -a
            if (n % 4 == 3):
                ans = -ans 
        while (a % 2 == 0): 
            a = a // 2 
            if (n % 8 == 3 or n % 8 == 5): 
                ans = -ans  
        a, n = n, a
        if (a % 4 == 3 and n % 4 == 3): 
            ans = -ans
        a = a % n
        if (a > n // 2): 
            a = a - n 
    if (n == 1): 
        return ans
    return 0 

def solovayStrassen(p, iterations):    
    for i in range(iterations):         
        a = random.randint(2, p - 1)         
        if gcd(a, p) > 1:
            return False        
        first = pow(a, int((p - 1) / 2), p)    
        j = (Jacobian(a, p) + p) % p                            
        if first != j: 
            return False 
    return True

def findFirstPrime(n, k): 
    while True:              
        if solovayStrassen(n,k):            
            return n
        n+=2    

a = random.getrandbits(512)
if a%2==0:
    a+=1    
print(findFirstPrime(a,100))
4

1 回答 1

3

如注释中所述，如果是超过 53 位的整数，int((p - 1) / 2)则会产生垃圾。转换为浮点数进行除法时p，仅保留 的前 53 位。p-1

>>> p = 123456789123456789123456789
>>> (p-1) // 2
61728394561728394561728394
>>> hex(_)
'0x330f7ef971d8cfbe022f8a'
>>> int((p-1) / 2)
61728394561728395668881408
>>> hex(_) # lots of trailing zeroes
'0x330f7ef971d8d000000000'

当然，素性检验的理论依赖于精确地使用的无限精确值(p-1)/2，而不是仅对前 53 个最高有效位或多或少好的近似值。

正如评论中所指出的，使用垃圾可能会使这部分更早返回，而不是更晚：

        if first != j: 
            return False

那么为什么它总体上要慢得多呢？因为必须多次findFirstPrime()调用solovayStrassen()才能找到完全靠运气的垃圾。

要查看这一点，请更改代码以显示循环尝试的频率：

def findFirstPrime(n, k):
    count = 0
    while True:
        count += 1
        if count % 1000 == 0:
            print(f"at count {count:,}")
        if solovayStrassen(n,k):            
            return n, count
        n+=2

然后添加，例如，

random.seed(12)

在主程序开始时，您可以获得可重复的结果。

使用 floor ( //) 除法，它运行得相当快，显示

(6170518232878265099306454685234429219657996228748920426206889067017854517343512513954857500421232718472897893847571955479036221948870073830638539006377457, 906)

所以它在第 906 次尝试中找到了一个可能的素数。

但是使用 float ( /) 除法，我从来没有看到它靠运气成功：

at count 1,000
at count 2,000
at count 3,000
...
at count 1,000,000

然后放弃-“垃圾进，垃圾出”。

顺便说一句，要注意的另一件事是：+ p在：

        j = (Jacobian(a, p) + p) % p

对 的值没有影响j。正确的？p % p为 0。

于 2021-02-19T05:00:07.843 回答