连分数因子分解法——C语言实现

2024-09-07 08:04

本文主要是介绍连分数因子分解法——C语言实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考网址:连分数分解法寻找整数的因子(Python)-CSDN博客

大数运算:C语言实现 大数运算 加减乘除模运算 超详细_64编程 加减乘除取模 复杂运算-CSDN博客

连分数因子分解法‌是一种用于大整数因子分解的算法,它是计算数论中的一个重要方法。连分数因子分解法通过寻找x2≡y2 (mod p)x2≡y2 (mod p)的形式来分解N。具体来说,这种方法涉及到计算N的简单连分数展开,并通过组合得到的同余式来寻找或组合得到因子。

连分数因子分解法的步骤大致如下:

  1. 计算NN的简单连分数展开‌,同时计算PkPk​和QkQk​序列,其中P0=a0,P1=a0a1+1,Pk=akPk−1+Pk−2P0​=a0​,P1​=a0​a1​+1,Pk​=ak​Pk−1​+Pk−2​,Q0=1,Q1=a1,Qk=akQk−1Q0​=1,Q1​=a1​,Qk​=ak​Qk−1​。
  2. 通过连分数展开寻找或组合得到同余式‌:x2≡y2 (mod p)x2≡y2 (mod p),其中pp是素数,xx和yy是整数。
  3. 利用找到的同余式‌,通过计算和组合这些同余式,可以进一步分解给定的整数NN。

这种方法在处理大整数时特别有用,因为它提供了一种有效的手段来分解那些无法通过简单试除法直接分解的大数。连分数因子分解法与二次筛法、数域筛法等方法一起,构成了处理大数因子分解的一系列工具‌1。

此外,连分数因子分解法在实际应用中也有其局限性,尤其是在处理非常大的数时,其计算复杂度和所需资源可能会成为限制因素。因此,尽管这种方法在理论和实践上都有其价值,但在实际应用中还需要考虑其他更高效的算法或技术的结合使用‌

我使用C语言实现的连分数因子分解法部分代码,由于是测试代码,目前还没有优化,存在一些问题:

/*
-----------------------连分数因子分解法----------------------实现时间:2024年9月5日作者:赵良军
*/
//求完全平方数
int is_square(unsigned char* seq_Q){unsigned char* p = my_sqrt(seq_Q);p = mul(p, p);//printf( "s = %s\n",p );if(maxer( p,seq_Q ) == 0){return 1;	}	  return 0;
}
//求最大公约数
unsigned char* my_gcd(unsigned char* a,unsigned char* b){unsigned char* c = NULL;while (a){   	c = mol(b,a);   b = a;a = c;if( maxer( a, "0" ) == 0 || maxer( c, "0" ) == 0 ){return b;}     	} return NULL;   
}
void cfrac(char* n){unsigned char seq_P[3][BUFLEN] = {{'\0'},{'\0'},{'\0'}};unsigned char seq_Q[3][BUFLEN] = {{'\0'},{'\0'},{'\0'}};unsigned char seq_a[3][BUFLEN] = {{'\0'},{'\0'},{'\0'}};unsigned char seq_p[3][BUFLEN] = {{'\0'},{'\0'},{'\0'}};strncpy(seq_P[0],"0",1);//strncpy(seq_P[1],"0",1);//strncpy(seq_P[2],"0",1);strncpy(seq_Q[0],"1",1);//strncpy(seq_Q[1],"1",1);//strncpy(seq_Q[2],"1",1);unsigned char* p = NULL;unsigned char buf[BUFLEN] = {'\0'};printf("N = %s\n",n);unsigned char* a0 = my_sqrt(n);strcpy(seq_a[0],a0);   strncpy(seq_p[0],"0",1);strcpy(seq_p[1],a0 ); unsigned char i[BUFLEN] = {'\0'};strncpy(i,"1",1);unsigned char t[BUFLEN] = {'\0'};while(1){//P_{k},Q_{k}序列printf("Start------------------------->\n");//P序列的模数p = mul(seq_a[0], seq_Q[0]);strcpy(buf,p);p = sub(buf,seq_P[0]);strcpy( seq_P[0],p );printf("P_M = %s\n",p );p = mul(seq_P[0], seq_P[0]);strcpy(buf,p);//printf("M0 = %s\n",p );p = sub(n,buf);strcpy(buf,p);//printf("M1 = %s\n",p );p = divi( buf,seq_Q[0]);strcpy(seq_Q[0],p);//printf("M2 = %s\n",p );//p = mol(buf,seq_Q[0]);//strcpy(buf,p);//printf("M3 = %s\n",p );p = add(seq_P[0],my_sqrt(n));strcpy(buf,p);//printf("M3 = %s\n",p );p = divi( buf,seq_Q[0]);strcpy(seq_a[0],p);//printf("M4 = %s\n",seq_a[0] );//p_{k}序列if( maxer(i,"1") == 0 ){p = mul(a0, seq_a[0]);strcpy(buf,p);p = add(buf,"1");strcpy(seq_p[2],p);}else{strcpy(seq_p[0],seq_p[1]);strcpy(seq_p[1],seq_p[2]);p = mul(seq_a[0], seq_p[1]);strcpy(buf,p);p = add( buf,seq_p[0] );strcpy(seq_p[2],p);}if( maxer( mol( i, "2" ), "0" ) == 0 && is_square(seq_Q[0]) ){unsigned char* s = my_sqrt(seq_Q[0]);unsigned char* p_p = NULL;printf("S = %s\n",s );p = add(seq_p[1],s);p_p = my_gcd(p,n);     	  printf("P+ = %s\n",p_p);p = sub(seq_p[1],s);p_p = my_gcd(p,n);     	  printf("P- = %s\n",p_p);if(p_p != NULL && maxer( p_p, "1" ) != 0){	      	  	  break;}} if( maxer( mol( i, "1000" ), "0" ) == 0 ){printf("Run to %s\n",i);}p = add(i,"1");strcpy(i,p);}
}int main(){//unsigned char* n = "70191551";//2**67-1unsigned char* n = "147573952589676412927";cfrac(n);}

这篇关于连分数因子分解法——C语言实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1144520

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、