当前位置: 首页 > news >正文

Shor`s因子分解法——C语言实现

Shor算法是一种量子算法,用于寻找模数N的周期性(即寻找满足gcd(a^(N/2), N) = 1的最小的正整数a)。它是Peter Shor在1994年提出的一种用于因式分解的方法,该方法基于量子计算。

Shor算法的数学原理:

Shor算法利用了周期性在模数运算中的性质。具体来说,如果a是模N的一个生成元(即a^(N/2) mod N = 1),那么a的所有幂次模N的结果将会形成一个周期,这个周期的长度是N的一个因子。通过在量子计算中利用这种周期性,Shor算法能够高效地找到N的因子。

实现Shor算法的步骤详解:

选择一个合适的生成元a:

首先需要找到一个生成元a,使得gcd(a^(N/2), N) = 1。这通常通过试探法实现,即尝试不同的a值直到找到满足条件的一个。

量子计算:

使用量子门实现QFT,将初始的均匀叠加态转换为相位分布态。

在量子计算机上执行这一转换,并通过测量得到一个可能的因子。

经典后处理:

对量子计算机的测量结果进行经典后处理,例如通过扩展欧几里得算法找到因子的正确形式,并验证其正确性。

/**********************************************************************	shor.cc -- Use Shor's Algorithm *		to factor a large long long int* *	Compile:*	 g++ -s -O4 -o shor shor.c*	Invoke:*	 ./shor NumbertoFactor InitialK* ChangeLog:*  970225 -- Created by Paul Herman <a540pau@pslc.ucla.edu>
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define max(a,b)	(a<b)? b : a
#define mul(x,y,m) ((__int128)(x)*(y)%m)inline long long powm(long long x,long long y,long long mod){long long res=1;while(y){if(y&1){res=mul(res,x,mod);}y>>=1;x=mul(x,x,mod);}return res;
}inline int gcd(int a, int b) {if(b > a) {a ^= b;b ^= a;a ^= b;}while(b > 0) {int r = a % b;a = b;b = r;}return a;
}/********************************************************************
/*  Period:  This computes the size of the group generated by a mod n
/*           i.e. |<a>|
/********************************************************************/
int	Period(long int a, long int n) {int count;count = 1;while (powm(a, count, n) != 1){ count++;printf("%ld\n",count);}return count;
}/*********************
/*  ShorFactor:  Finds a factor of n by looking at the group generated
/*               by <a> mod n.  Let t = |<a>|/2  .  Check to see if
/*               t +/- 1 and n have a common factor.  If not, try another a 
/*********************/long long int ShorFactor(long long int n) {long long int a, t1, t2, f1, f2;int r;//我在这里改为随机化srand(time(NULL));a = rand();for(long int j=2;;j++){f1 = gcd(a, n);if (f1 != 1) return f1;//本质上就是找P序列//r = Period(a, n);//本质上就是找Q序列r = powm(a,j,n);//t1 = powm(a, r, n);t1 = powm(a, (r/2), n);t1 += 1;t2 = t1 - 2;printf("t1 = %ld\n",t1);f1 = gcd(t1, n);if (f1 != 1){printf("f1 = %ld\n",f1);return f1;}f2 = gcd(t2, n);if (f2 != 1){ printf("f2 = %ld\n",f2);return f2;}a += 1;}return (long long int)1;	// No luck at all (This never happens)
}int main() {long int k;k = ShorFactor(70191551);printf("Find q is = %ld\n",k);return 0;
}

http://www.lryc.cn/news/589769.html

相关文章:

  • 实例操作:基于 PipeLine 实现 JAVA项目集成 SonarQube代码检测通知 Jenkins
  • 探索阿里云DMS:解锁高效数据管理新姿势
  • 【NLP舆情分析】基于python微博舆情分析可视化系统(flask+pandas+echarts) 视频教程 - 微博类别信息爬取
  • C#——循环(while循环和do-while循环)
  • Java 大视界 -- 基于 Java 的大数据分布式存储在云计算数据中心数据管理与调度中的应用(348)
  • docker run elasticsearch 报错
  • 征服ZYNQ双核潜能:OCM内存精妙分配与免锁通信实战
  • WPF 加载和显示 GIF 图片的完整指南
  • 【游戏引擎之路】登神长阶(十七):Humanoid动画——长风破浪会有时,直挂云帆济沧海
  • Arduino土壤湿度检测
  • 新手向:自动化图片格式转换工具
  • 【游戏引擎之路】登神长阶(十八):3天制作Galgame引擎《Galplayer》——无敌之道心
  • 玩转Docker | 使用Docker部署bender个人导航页工具
  • my2sql-binlog闪回测试
  • 设计一款用于捕捉动态产品视频的摄像机器人
  • 记录一道sql面试题3
  • EVA series系列(上)
  • 【MySQL基础】MySQL事务详解:原理、特性与实战应用
  • 网络安全(初级)(XSS-labs 1-8)
  • JWT基础详解
  • Linux内核设计与实现 - 第2章 内核开发的准备
  • Python包开发实战:从零构建你的第一个Python包
  • 《透视定轴:CSS 3D魔方中视觉层级的秩序法则》
  • 使用CodeQL挖掘Spring中的大量赋值漏洞
  • PLC-BMS电力载波通信技术深度解析:智能电网与储能系统的融合创新
  • Python 测试全景:单元测试、集成测试与端到端测试实战指南
  • NDVI、噪声和细微差别:使用卫星时间序列进行土地覆盖分类
  • 【源力觉醒 创作者计划】百度携文心 4.5 入局,开源大模型市场再添一员猛将,与 Qwen3 对比如何?
  • 列车调度(vector)
  • Spring Boot 缓存 与 Redis