TypeError: unsupported operand type(s) for &: 'sage.rings.rational.Rational' and 'int'

TypeError: unsupported operand type(s) for &: 'sage.rings.rational.Rational' and 'int'

因此,在我的密码学课程中,我们得到了一项作业,在问题 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 函数将有理数转换为整数?

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