Click here to Skip to main content
15,885,309 members

Miller Rabin algorithm - computer fail

Member 9552449 asked:

Open original thread
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!
Tags: C#

Plain Text
ASM
ASP
ASP.NET
BASIC
BAT
C#
C++
COBOL
CoffeeScript
CSS
Dart
dbase
F#
FORTRAN
HTML
Java
Javascript
Kotlin
Lua
MIDL
MSIL
ObjectiveC
Pascal
PERL
PHP
PowerShell
Python
Razor
Ruby
Scala
Shell
SLN
SQL
Swift
T4
Terminal
TypeScript
VB
VBScript
XML
YAML

Preview



When answering a question please:
  1. Read the question carefully.
  2. Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
  3. If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
  4. Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.
Let's work to help developers, not make them feel stupid.
Please note that all posts will be submitted under the http://www.codeproject.com/info/cpol10.aspx.



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