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

Question

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

您可以为您的函数添加更多选项:allow k作为输入，x , y等等。无论如何，然后运行 ​​testing(20) .