Python一个整数分解的代码无法运行

poorich

从github上找的一段用于整数分解的pyhton小程序
https://github.com/delta003/lenstra_algorithm
4年前的代码了，我想可能这是py2的代码，可能是版本的问题，因此一直报错——错误似乎是找不到变量的样子
哎，除了print差个括号外，我根本不了解py2和py3还有什么异同啊...
同时我py3的修为也完全不到家，不知道该怎么整，只能请教论坛的专家了

[Python] 纯文本查看 复制代码

import argparse
from random import randint
from fractions import gcd

# Sieve of Eratosthenes
def primes(n):
    b = [True] * (n + 1)
    ps = []
    for p in xrange(2, n + 1):
        if b[p]:
            ps.append(p)
            for i in xrange(p, n + 1, p):
                b[i] = False
    return ps

# Finds modular inverse
# Returns inverse, unused helper and gcd
def modular_inv(a, b):
    if b == 0:
        return 1, 0, a
    q, r = divmod(a, b)
    x, y, g = modular_inv(b, r)
    return y, x - q * y, g

# Addition in Elliptic curve modulo m space
def elliptic_add(p, q, a, b, m):
    # If one point is infinity, return other one
    if p[2] == 0: return q
    if q[2] == 0: return p
    if p[0] == q[0]:
        if (p[1] + q[1]) % m == 0:
            return 0, 1, 0  # Infinity
        num = (3 * p[0] * p[0] + a) % m
        denom = (2 * p[1]) % m
    else:
        num = (q[1] - p[1]) % m
        denom = (q[0] - p[0]) % m
    inv, _, g = modular_inv(denom, m)
    # Unable to find inverse, arithmetic breaks
    if g > 1:
        return 0, 0, denom  # Failure
    z = (num * inv * num * inv - p[0] - q[0]) % m
    return z, (num * inv * (p[0] - z) - p[1]) % m, 1

# Multiplication (repeated addition and doubling)
def elliptic_mul(k, p, a, b, m):
    r = (0, 1, 0)  # Infinity
    while k > 0:
        # p is failure, return it
        if p[2] > 1:
            return p
        if k % 2 == 1:
            r = elliptic_add(p, r, a, b, m)
        k = k // 2
        p = elliptic_add(p, p, a, b, m)
    return r

# Lenstra's algorithm for factoring
# Limit specifies the amount of work permitted
def lenstra(n, limit):
    g = n
    while g == n:
        # Randomized x and y
        q = randint(0, n - 1), randint(0, n - 1), 1
        # Randomized curve coefficient a, computed b
        a = randint(0, n - 1)
        b = (q[1] * q[1] - q[0] * q[0] * q[0] - a * q[0]) % n
        g = gcd(4 * a * a * a + 27 * b * b, n)  # singularity check
    # If we got lucky, return lucky factor
    if g > 1:
        return g
    # increase k step by step until lcm(1, ..., limit)
    for p in primes(limit):
        pp = p
        while pp < limit:
            q = elliptic_mul(p, q, a, b, n)
            # Elliptic arithmetic breaks
            if q[2] > 1:
                return gcd(q[2], n)
            pp = p * pp
    return False

# Command line tool
def main():
    parser = argparse.ArgumentParser(description = 'Process arguments')
    parser.add_argument('--n', type = int,
                        help = 'number to factor')
    parser.add_argument('--limit', type = int, default = 1000,
                        help = 'work limit (default = 1000)')
    args = parser.parse_args()
    print(lenstra(args.n, args.limit))

if __name__ == '__main__':
    main()

奔跑者_Python

没报错信息怎么看

prty

我想帮你看看 但是眼睛也确实也不是很睁的开  提出问题 基本信息你得进行说明
忙活了我这么久 发现把参数的--n 看成了-n  解决这个问题 发现出现一个更低级的问题 print 和xrange 用到同一脚本 这是干什么。。。

poorich

prty 发表于 2019-9-7 01:23
我想帮你看看 但是眼睛也确实也不是很睁的开  提出问题 基本信息你得进行说明
忙活了我这么久 发现把参数 ...

老哥，真的谢谢你这么晚答疑
我问这问题，是实在没办法了
想分解一些大整数测试一下
网上就找到这个好几年前的代码，我想可能这是py2的代码
我唯一找到的错误就是print没加括号，其他就两眼一抹黑了

我也找到另外一个核心思想一样的代码，
https://github.com/nishanth17/factor
但文件代码多了许多，也是print不加括号，我觉得还是问个短点的代码吧

海是倒过来的天

至少上个报错信息啊。。。

namedlxd

代码能跑, 是你没输入参数吧?

D:\soft\Jetbrains\PycharmProjects\collector>python test.py --n 100
test.py:73: DeprecationWarning: fractions.gcd() is deprecated. Use math.gcd() instead.
  g = gcd(4 * a * a * a + 27 * b * b, n)  # singularity check
4

Roothu

你报错信息呢，总不能等别人跑一遍吧