米勒拉宾算法 - 计算机失败 [英] Miller Rabin algorithm - computer fail

问题描述

public BigInteger GenerateNumber(int length)
        {
            RNGCryptoServiceProvider createNum = new RNGCryptoServiceProvider();
            byte[] number = new byte[length];
            createNum.GetBytes(number);
            BigInteger numToRet = new BigInteger(number);
            return numToRet;
        }

        public bool isPrime(BigInteger N, int iterations)
        {
            BigInteger r = new BigInteger((N - 1).ToByteArray());
            BigInteger a;
            BigInteger y;
            byte[] number = N.ToByteArray();

            if (N == 2 || N == 3)
                return true;
            if (N % 2 == 0)
                return false;

            while (r % 2 == 0)
            {
                r = r / 2;                
            }

            for (int i = 0; i < iterations; i++)
            {
                do
                {
                    a = GenerateNumber(number.Length);
                
                } while (a < 2 || a > N - 2);
                
                y = BigInteger.ModPow(a, r, N);
                BigInteger temp = r;
                
                while (temp != N - 1 && y != 1 && y != N - 1)
                {
                    y = BigInteger.ModPow(y, 2, N);
                    temp = BigInteger.Multiply(temp,2);
                }
                
                if (y != N - 1 && BigInteger.ModPow(temp,1,2) == 0)
                    return false;
                
            }

            return true;
        }

当我用小数字运行这个程序时它运行得很好，当我尝试使用150位数字（对于RSA加密）运行它时，使用GenerateNumber（int length）方法，程序失败并且不能继续运行。

你知道一种使它工作的方法吗？

非常感谢！

when I run this program with small numbers it works great, when I try to run it with numbers like 150 digits long (for RSA encryption), using the GenerateNumber(int length) method, the program fails and does not continue to operate.
do you know about a way to make it work ?
thanks a lot!

推荐答案

根据Codeplex，BigInteger应该处理大量的数字，但是默认设置为uint32。处理大数字你必须调整他们的代码。请参阅此处的说明

http://biginteger.codeplex.com/ [ ^ ]





问候

Jegan

Hi,
According to Codeplex the BigInteger should handle large number, but by default it is set uint32. to handle large numbers you have to tweak their code. See instruction here
http://biginteger.codeplex.com/[^]


Regards
Jegan

这篇关于米勒拉宾算法 - 计算机失败的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！