开发者社区> jclian91> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

连分数分解法寻找整数的因子(Python)

简介:   首先,先讲个小故事。   1903年10月,科尔(Cole)在纽约参加美国数学(AMS)的一个会议,议程里有他的一篇题目平淡的论文:“关于一个大数的分解”。
+关注继续查看

  首先,先讲个小故事。
  1903年10月,科尔(Cole)在纽约参加美国数学(AMS)的一个会议,议程里有他的一篇题目平淡的论文:“关于一个大数的分解”。大会主席请他宣读论文时,一向寡言的科尔走上黑板,一言不发,拿起粉笔就开始算2的67次方。然后,他小心地减去1.接着,还是不说一个字,他移到黑板的空白处,老老实实地计算

193707721×761838257287193707721×761838257287
两个计算结果一致……美国数学会的听众们破天荒地第一次也是唯一一次为他们听到的报告热烈鼓掌欢呼。科尔还是一言不发,回到自己的位置。也没人向他提任何问题。
  几年过后,1911年,贝尔(E.T.Bell)问科尔用了多长时间来分解M67(Mersenne素数)。科尔回答:“三年里的星期天。”
  在初等数论中,我们可以利用连分数分解法来寻找大整数的因子,具体的算法可以参考《初等数论及其应用 美第五版》。以下我们给出Python代码:

# -*- coding: utf-8 -*-
from math import sqrt,floor,gcd
#判断是否为平方数
def is_square(n):
    t = int(sqrt(n))
    return t*t == n
def main():
    n = 2**67-1 #要分解的数
    print('n=%s'%('2**67-1'))
    seq_P,seq_Q=[0],[1]
    a0 = floor((seq_P[0]+sqrt(n))/seq_Q[0])
    seq_a= [a0]
    seq_p = [0,a0]
    i = 1
    while True:
        #P_{k},Q_{k}序列
        seq_P.append(seq_a[0]*seq_Q[0]-seq_P.pop())
        seq_Q.append(divmod(n-seq_P[0]**2,seq_Q.pop())[0])
        t = (seq_P[0]+sqrt(n))/seq_Q[0]
        seq_a[0] = floor(t)
        #p_{k}序列
        if i == 1:
                seq_p.append(a0*seq_a[0]+1)
        else:
            seq_p[0] = seq_p[1]
            seq_p[1] = seq_p[2]
            seq_p[2] = seq_a[0]*seq_p[1]+seq_p[0]
        #分解因式
        if i%2 == 0 and is_square(seq_Q[0]):
            s = int(sqrt(seq_Q[0]))
            factor = [gcd(seq_p[1]-s,n),gcd(seq_p[1]+s,n)]
            if factor[0] != 1 and factor[1] != 1:
                print('第%d项:%d,%d'%(i,factor[0],factor[1]))
                print('程序运行完毕!')
                break
        if i%1000 == 0:
            print('已运行到第%d项'%i)
        i += 1        
main()

运行结果如下:
M67
因此,M67有因子193707721和761838257287,因此M67不是梅森素数。



  按照这个思路,我们再给出其他几个非梅森素数的MkMk,当然读者也可以自己测试。注意:连分数分解法不一定能找到整数的因子。
  M71
  M79
  M83
  
注意:本人现已开通两个微信公众号: 用Python做数学(微信号为:python_math)以及轻松学会Python爬虫(微信号为:easy_web_scrape), 欢迎大家关注哦~~

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
ZZULIOJ-1022,三整数排序(Python)
ZZULIOJ-1022,三整数排序(Python)
43 0
ZZULIOJ-1020,两整数排序(Python)
ZZULIOJ-1020,两整数排序(Python)
36 0
Python编程:python-attrs模块的简单使用
Python编程:python-attrs模块的简单使用
58 0
Python编程:使用sqlalchemy对数据库进行增删改查
Python编程:使用sqlalchemy对数据库进行增删改查
53 0
Python编程:列表、集合、字典推导式的示例
Python编程:列表、集合、字典推导式的示例
20 0
Python编程:asyncio协程编程
Python编程:asyncio协程编程
22 0
Python编程:pillow对图像的简单处理
Python编程:pillow对图像的简单处理
10 0
Python编程:将markdown格式转换为rst格式
Python编程:将markdown格式转换为rst格式
30 0
Python编程:from __future__ import print_function
Python编程:from __future__ import print_function
17 0
Python编程专属技巧2
Python编程专属技巧2
40 0
+关注
jclian91
热爱算法,热爱技术,热爱生活,期待更好的自己与明天~
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Python第五讲——关于爬虫如何做js逆向的思路
立即下载
Python系列直播第一讲——Python中的一切皆对象
立即下载
Python 系列直播——深入Python与日志服务,玩转大规模数据分析处理实战第二讲
立即下载