Solovay-Strassen素性测试函数报错：Rational与int不支持&操作

错误根源分析 #

你遇到的TypeError: unsupported operand type(s) for &: 'sage.rings.rational.Rational' and 'int'错误，主要来自两个核心问题：

• 除法操作导致的类型不匹配
  在SageMath中，用/做除法会返回有理数类型（Rational）——哪怕计算结果是整数。比如当n是奇数时，(n-1)/2的数值是整数，但它的类型是Rational。后续如果用这个类型的变量和整数进行位运算（比如&），就会触发类型不兼容的错误。

• 错误使用位运算&做验证
  Solovay-Strassen的核心验证逻辑是：雅可比符号j需要满足 j ≡ a^((n-1)/2) mod n，正确的比较方式是模运算而非位运算。如果你错误地用&来对比j和p，再加上之前的类型问题，就会直接抛出这个报错。

修正后的完整代码 #

下面是补全并修复后的Solovay-Strassen函数：

def SolovayStrassen(n, k):
    # 先处理特殊情况：小于2的数、偶数、2本身
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for _ in range(k):
        a = randint(2, n-1)
        j = jacobi_symbol(a, n)
        # 用整数除法//代替/，确保指数是整数类型
        p = power_mod(a, (n-1)//2, n)
        
        # 核心验证逻辑：把j转成模n的正整数后和p比较
        if j % n != p:
            return False
    # 经过k轮测试，判定为大概率素数
    return True

关键修正说明 #

1. 用**整数除法//**替代/，确保(n-1)//2返回整数类型，彻底避免Rational带来的类型问题。
2. 实现正确的验证逻辑：由于雅可比符号j的取值是-1、0、1，先对j取模n转成正整数，再和p对比，符合素性测试的数学规则。
3. 增加了特殊值的提前处理，覆盖了所有非素数的边界情况，让函数逻辑更严谨。

内容的提问来源于stack exchange，提问作者AceNinja1101