TypeError:用于&：'sage.rings.rational.Rational‘和'int’的不支持的操作数类型

Question

因此，在我的密码学课程中，我们被分配了一项作业，在第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在线中编写的，但是当我运行代码时，它会弹出以下错误消息。

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，也通常被视为特例，因为它们的原始性很容易确定。