Python一个整数分解的代码无法运行
本帖最后由 poorich 于 2019-9-7 02:25 编辑从github上找的一段用于整数分解的pyhton小程序
https://github.com/delta003/lenstra_algorithm
4年前的代码了，我想可能这是py2的代码，可能是版本的问题，因此一直报错——错误似乎是找不到变量的样子
哎，除了print差个括号外，我根本不了解py2和py3还有什么异同啊...
同时我py3的修为也完全不到家，不知道该怎么整，只能请教论坛的专家了import argparse
from random import randint
from fractions import gcd
# Sieve of Eratosthenes
def primes(n):
b = * (n + 1)
ps = []
for p in xrange(2, n + 1):
if b:
ps.append(p)
for i in xrange(p, n + 1, p):
b = 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 == 0: return q
if q == 0: return p
if p == q:
if (p + q) % m == 0:
return 0, 1, 0# Infinity
num = (3 * p * p + a) % m
denom = (2 * p) % m
else:
num = (q - p) % m
denom = (q - p) % 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 - q) % m
return z, (num * inv * (p - z) - p) % 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 > 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 * q - q * q * q - a * q) % 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 > 1:
return gcd(q, 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()
没报错信息怎么看 我想帮你看看 但是眼睛也确实也不是很睁的开提出问题 基本信息你得进行说明
忙活了我这么久 发现把参数的--n 看成了-n解决这个问题 发现出现一个更低级的问题 print 和xrange 用到同一脚本 这是干什么。。。 本帖最后由 poorich 于 2019-9-7 02:29 编辑
prty 发表于 2019-9-7 01:23
我想帮你看看 但是眼睛也确实也不是很睁的开提出问题 基本信息你得进行说明
忙活了我这么久 发现把参数 ...
老哥，真的谢谢你这么晚答疑
我问这问题，是实在没办法了
想分解一些大整数测试一下
网上就找到这个好几年前的代码，我想可能这是py2的代码
我唯一找到的错误就是print没加括号，其他就两眼一抹黑了
我也找到另外一个核心思想一样的代码，
https://github.com/nishanth17/factor
但文件代码多了许多，也是print不加括号，我觉得还是问个短点的代码吧 至少上个报错信息啊。。。 代码能跑, 是你没输入参数吧?
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
你报错信息呢，总不能等别人跑一遍吧
页:
[1]