大数分解的Shor算法-C#

看代码吧没有太多要说的using System.Numerics; using System.Security.Cryptography; namespace ShorAlgorithm; class Program { /********************************************************************* * shor.cc -- Use Shors Algorithm * to factor a large BigInteger * ChangeLog: * 970225 -- Created by Paul Herman a540paupslc.ucla.edu **********************************************************************/ static BigInteger GenerateRandomBigInteger() { // 创建一个RandomNumberGenerator实例 using var rng RandomNumberGenerator.Create(); // 生成一个足够长的字节数组例如16字节128位 var randomBytes new byte[8]; // 可以根据需要增加字节数以生成更大的数 rng.GetBytes(randomBytes); // 将字节数组转换为BigInteger // 注意这里使用了BigEndianBitConverter因为BigInteger期望高位在前大端格式 return new BigInteger(randomBytes); } /******************************************************************** /* Period: This computes the size of the group generated by a mod n /* i.e. |a| /********************************************************************/ static int Period(BigInteger a, BigInteger n) { int count; count 1; while (BigInteger.ModPow(a, count, n) ! 1) { count; //Console.WriteLine(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 /*********************/ static BigInteger ShorFactor(BigInteger n) { BigInteger a, t1, t2, f1, f2; int r; //我在这里改为随机化 a GenerateRandomBigInteger(); for (BigInteger j 2; ; j) { //随机数a是n的因子 f1 BigInteger.GreatestCommonDivisor(a, n); if (f1 ! BigInteger.One) { Console.WriteLine($First Found f1 {f1}); return f1; } //本质上就是找P序列 //r Period(a, n); //本质上就是找Q序列 //ra^j mod n r (int)BigInteger.ModPow(a, j, n); //如果r为负数说明a^j mod n的结果是负数这不应该发生因为模运算的结果应该在0到n-1之间 if (r 0) { Console.WriteLine(Bad r); return BigInteger.One; } //t1和t2分别是a^((a^j mod n)/2) mod n的1和-1 t1 BigInteger.ModPow(a, (r 1), n); t1 1; t2 t1 - 2; //t1(a^(r/2) mod n) 1 //t2(a^(r/2) mod n) - 1 Console.WriteLine($At t1 {t1}); //测试t1 f1 BigInteger.GreatestCommonDivisor(t1, n); if (f1 ! BigInteger.One) { Console.WriteLine($Found f1 {f1}); return f1; } //测试t2 f2 BigInteger.GreatestCommonDivisor(t2, n); if (f2 ! BigInteger.One) { Console.WriteLine($Found f2 {f2}); return f2; } //如果t1和t2都没有找到因子那么就换一个a继续试s a 1; } return BigInteger.One; // No luck at all (This never happens) } static int Main() { BigInteger k ShorFactor(70191551); Console.WriteLine($Found q is {k}); return 0; } }