如何修复Sagemath中mod函数的错误？

Question

我决定用数学，因为我听说它在数论中很有用。我已经做了这个程序（这是我的第一个程序）分解一个数字，我不知道为什么它不工作。我认为这与函数mod的一个特定属性有关，但我不确定。你知道吗

有人知道怎么修吗？ 谢谢。你知道吗

    #Pollard algorithm
k=87757
f(x)=x^2+1
x=1
y=x
iter=20
i=0
while(i<iter):
    i=i+1
    x=mod(f(x),k)
    y=mod(f(f(y)),k)
    g=(x-y).gcd(k)
    if(1<g and g<k):
        print(g)
        print(i)
        break

Answer 1

我相信问题确实出在mod函数的使用上。一旦你做了x = mod(f(x), k)，那么x就生活在Z/kZ环中。这同样适用于g。这个环中的不等式实际上没有意义，特别是，g<k将被转换成g<0。这是因为k=0mod k并且当您执行代数运算、等式检查、不等式检查等时，两边都转换为可用的最佳环。在这个例子中，这个环是Z/kZ。你知道吗

最好一直用整数：

x = f(x).mod(k)
y = f(f(y)).mod(k)

以下是将mod用作函数或方法的区别：

sage: type(5.mod(3))  # method
<type 'sage.rings.integer.Integer'>
sage: type(mod(5, 3)) # function
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>

如果我想将其保存在适合在Sage中使用的Python文件中，我会这样做：

from sage.rings.all import Integer

def f(x):
    # Make sure to return a Sage Integer.
    return Integer(x**2+1)

def testing(iter=20):
    x=1
    y=x
    i=0
    k=87757
    while i<iter:
        i=i+1
        x=f(x).mod(k)
        y=f(f(y)).mod(k)
        g=(x-y).gcd(k)
        # For debugging:
        # print(x, y, g)
        if 1<g and g<k:
            print(g)
            print(i)
            break

您可以为函数添加更多选项：允许k作为输入，x，y，等等。无论如何，运行testing(20)。你知道吗