大数分解的Shor算法-C#

看代码吧，没有太多要说的

using System.Numerics; using System.Security.Cryptography; namespace ShorAlgorithm; class Program { /********************************************************************* * shor.cc -- Use Shor's Algorithm * to factor a large BigInteger * ChangeLog: * 970225 -- Created by Paul Herman <a540pau@pslc.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序列 //r=a^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; } }