如何在Sagemath中使用函数mod修复错误？

Question

我决定使用Sagemath，因为我听说它在数论中非常有用。我制作了这个程序（这是我的第一个程序）来分解数字，我不知道为什么它不起作用。我认为它与函数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=0 mod 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)。