python - 类型错误 : unsupported operand type(s) for &: 'sage.rings.rational.Rational' and 'int'

Question

因此，在我的密码学类(class)中，我们得到了一项作业，在问题 1 中，我们必须编写 Solovay-Strassen 素数检验函数的其余部分，这是我写的内容:

def SolovayStrassen(n,k):
    for i in [1..k]:
        a = randint(2,n-1) #picks a random number between 2 and n-1
        j = jacobi_symbol(a,n) #computes jacobi function
        p = power_mod(a,(n-1)/2,n) #uses the power mod function 
        #now we test if both are equal to find if both are equal in order to check if the number is "composite" or "probably prime"
        if (j != p):
            return False #"composite"
    return True #"probably prime"

请注意，这是在 sage online 中编译的，但是当我运行代码时，它会弹出此错误消息

Error in lines 2-2
Traceback (most recent call last):
  File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "", line 5, in SolovayStrassen
  File "/ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/arith/misc.py", line 1939, in power_mod
    while n&1 == 0:
TypeError: unsupported operand type(s) for &: 'sage.rings.rational.Rational' and 'int'

看起来它指的是错误似乎发生的这一行

 p = power_mod(a,(n-1)/2,n) #uses the power mod function 

我假设错误可能是它试图根据 power_mod 函数将有理数转换为整数？

Answer 1

您需要使用// 运算符进行整数除法。如果分子不能被分母整除，则 / 运算符将在 Sagemath 中生成有理数。我怀疑你的算法无论如何都不应该在 n 的偶数上尝试，这是这个问题可能表现出来的唯一方式。甚至 n 通常也被视为特例，因为它们的素数很容易确定。