在函数和 shell 中对相同的方程式得到不同的结果

Question

我已经使用 Sage 为对数实现了 Pollard 的 Rho，如下程序存储在 pollardrho.py。

def pollardrho(g, h, G):
    k, m = 1, 0
    t = g**k * h**m
    i, j = 1, 0
    r = g**i * h**j

    def step(t, k, m):
        if lift(t) % 3 == 0:
            return (t * g, k+1, m)
        if lift(t) % 3 == 1:
            return (t * h, k, m+1)
        if lift(t) % 3 == 2:
            return (t ** 2, 2*k, 2*m)

    while True:
        t, k, m = step(t, k, m)
        r, i, j = step(*step(r, i, j))
        if t == r:
            print("Found a cycle")
            print("g^%s h^%s == g^%s h^%s" % (k, m, i, j))
            print("g^(%s - %s) == h^(%s - %s)" % (i, k, m, j))
            l = g.multiplicative_order()
            print("(%s - %s) / (%s - %s) %% %s" % (i, k, m, j, l))
            return (i - k) / (m - j) % l  # this is where everything goes wrong.

运行这与 G = GF(1013), g = G(3), h = G(245) 给出以下输出：

sage: pollardrho(g, h, G)
Found a cycle
g^262 h^14 == g^16870 h^1006
g^(16870 - 262) == h^(14 - 1006)
(16870 - 262) / (14 - 1006) % 1012
995

但是：

sage: (16870 - 262) / (14 - 1006) % 1012
375

请注意，这是一个完全不同的结果！

如果我检查 i, j, k, m 的类型，它们都是 int...

类型

Answer 1

事实证明，在 sage shell 中键入一个整数与在使用 Sage 库的 python 程序中执行相同的结果不同：

sage: type(1234)
<type 'sage.rings.integer.Integer'>

这与我在自己的程序中得到的 <type 'int'> 不同！

使用 k, m = Integer(1), Integer(0) 解决了我的问题，现在我得到了正确的离散日志。

Answer 2

为了详细说明 Thom 的回答，在 .py 文件中，您不能使用 Sage 所做的各种准备工作 - 特别是，ints 是 ints。从文件中的 sage.rings.integer.Integer（或 sage.all）导入可以工作，或者（我推荐这样做）只使文件扩展名 .sage 而不是 .py 是最简单的，并且最不可能运行进入其他细微差别。

在函数和 shell 中对相同的方程式得到不同的结果

Getting different results for the same equation in a function and the shell

ipython

sage

modular-arithmetic