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;
}