Click here to Skip to main content
15,892,072 members
Please Sign up or sign in to vote.
5.00/5 (1 vote)
See more:
C#
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;
        }

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!
Posted
Updated 26-Feb-13 1:38am
v2
Comments
boogac 26-Feb-13 9:05am    
150 digits and int length ??

I am not sure, it can be a memory problem..After seen your post,I m curious about Big O notation of this algorithm..if its something like n2 or worse it can cause trouble with big numbers naturally
Member 9552449 26-Feb-13 9:20am    
how do you think I can fix that?
do you know a better version of this algorithm?

1 solution

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
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS


CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900