Generating 2 random prime number in C#

The problem in your code is that you call 'CheckIfPrime passing it a 'BigInteger, but its parameter is: 'int.

There's also a problem in that the Math library 'Sqrt Function will not accept Type 'BigInteger. You can work around that with this:

<br />
BigInteger sqrt = Math.Exp(BigInteger.Log(bigIntValue) / 2); 

// see: [^].

Think about the range of values you want the randomly selected primes within; your use of 'BigInteger implies ... well ... very large. As you know, determining the "primality" of very large numbers can take massive amounts of computation power.

There are publicly available lists of primes, including very large primes; could you implement your solution using a list from which you randomly select ? There's a list of 5000 very large primes here (minimum 1000 digits each): [^].

Re the issue of getting two random values "simultaneously:" if you have multi-cores to work with, consider using parallel programming in .NET: [^].

This uses 'System.Security.Cryptography the RNGCrytoServiceProvider facility to get random big integers with a certain number of bits:

// note this code is from a a static Class named 'Methods in a NameSpace named 'PrimeUtilties

private static RNGCryptoServiceProvider rngProvider = new RNGCryptoServiceProvider();
private static Random random = new Random(DateTime.Now.Millisecond);
private static byte[] someBytes;

public static BigInteger GetRandomBigInteger(int nBits, bool onlyPositive = true)
{
    someBytes = new byte[nBits/8];
    rngProvider.GetBytes(someBytes);
    
    BigInteger bg = new BigInteger(someBytes);
    if (onlyPositive && bg.Sign == -1) bg = bg * -1;
    
    return bg;
}

You can use a Tuple to return two values from a Method:

public static Tuple<BigInteger, BigInteger> GetTwoRandomBigInts(int nbitsOf1 = 128, int nbitsOf2 = 128, bool onlyPositive = true)
{
    return Tuple.Create(GetRandomBigInteger(nbitsOf1, onlyPositive), GetRandomBigInteger(nbitsOf2, onlyPositive));
}

// get a Tuple with two (non-negative) BigInts
// var TwoBigOnesWith = PrimeUtilities.Methods.GetTwoRandomBigInts(512, 256, onlyPositive: true);

But, normally I wouldn't bother writing a hard-coded method like that; I'd write a more general one that took a 'param array, or passed in some structure that I'd parse to generate whatever bunch, or, bunch-of-bunches, of BigIntegers I wanted to create.

Your code have numerous problems.
One of them is efficiency, here is your code and 2 trivial changes:

public bool CheckIfPrime(int n) //to check if the random number generated is prime
{
    var isPrime = true;
    var sqrt = Math.Sqrt(n);
    for (var i = 2; i <= sqrt; i++)
        if ((n % i) == 0) isPrime = false;
    return isPrime;
}

for n=400 the code checks 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

public bool CheckIfPrime(int n) //to check if the random number generated is prime
{
    var isPrime = true;
    var sqrt = Math.Sqrt(n);
    if ((n % 2) == 0) isPrime = false;
    for (var i = 3; i <= sqrt; i+= 2)
        if ((n % i) == 0) isPrime = false;
    return isPrime;
}

for n=400 the code checks 2, 3, 5, 7, 9, 11, 13, 15, 17, 19

public bool CheckIfPrime(int n) //to check if the random number generated is prime
{
    var sqrt = Math.Sqrt(n);
    if ((n % 2) == 0) return false;
    for (var i = 3; i <= sqrt; i+= 2)
        if ((n % i) == 0) return false;
    return true;
}

and here the code stops as soon as it knows n is not a prime.

As already spotted, int n parameter of the function is wrong since you want to check a BigInteger.

So I've tried this code, and it works okay to me.

Random rand = new Random();
            BigInteger p = BigInteger.genPseudoPrime(128, 10, rand);
            txtP.Text = p.ToString();

            Random rand2 = new Random();
            BigInteger q = BigInteger.genPseudoPrime(128, 10, rand2);
            do
            {
                q = BigInteger.genPseudoPrime(128, 10, rand2);
            }
            while (p == q);
            txtQ.Text = q.ToString();

using the DLL from Client/Server Encryption plus extras[^]

All the other codes are also okay, but for my case I'm using this code, so here it is, to share to anyone who is looking at the same problem. Thank you all so much for your kindness!

OK, Just throwing this out there...

EASY PRIME GENERATION IN C#.NET

I think this approach will be far more useful to most readers than some of the suggestions above. Forgive me, but after reading this thread I figured that this little trick is sorely missing from the discussion. I don't normally post here.

Before we begin, this method does have limitations... it cannot make really small primes. It can, however make huge primes, even over 16,000 bits without any fuss.

Personally I think not being able to make tiny primes is a limitation most of us can probably live with, yes? If you DO need tiny primes, then the table or random methods above are manageable... and you can use both techniques if you need all sizes ...

- a table or a random search for primes less than 384 bits, and;
- this code for primes between 284 bits and 16,384 bits.

I think you'll agree that it's a really simple and safe method. Let's get stuck in :

First,

using system.security.cryptography

As a quick test, you could create an instance of the RSACryptoServiceProvider class... as this exposes the range of primes that are valid when creating an RSA key. Like this...

using (RSACryptoServiceProvider myRsa = new RSACryptoServiceProvider)
{
    // Now look at the following properties of myRsa...
    int min = myRSA.LegalKeySizes.MinSize;  // Usually 16,384
    int max = myRSA.LegalKeySizes.MaxSize;  // Usually    384
    int step = myRSA.LegalKeySizes.StepSize; //             8

    // Use the values above to decide on a valid keysize for the
    // prime you want to generate!  As you can see, you have a
    // LOT of options.  The size is in bits, which is why we
    // see a 'StepSize' of 8
}

These numbers are not likely to change, so feel free to ignore the above - I include it only to show the primes you can produce. Once you have identified a size (between min and max, with a step size of 8) ... you can ask c# to create a key of that specific size!

Delete the above code, and let's start generating primes...


Use DotNets RSA implementation to generate a large prime

Let's begin with a nice small 1024 bit prime number...

// Create a temporary RSA key (we don't need the key, just it's prime)
using (RSACryptoServiceProvider myRsa = new RSACryptoServiceProvider(1024))
{
    // Boom, prime generated!  Yes, that simple... let's dig it out.

    // First, output the private certificate as an XML string
    // The parameter 'true' tells c# to include the private key
    // otherwise we only get the public part.
    String xml = myRsa.ToXmlString(true);

    // Now, you're interested in the subkeys P and Q in that XML
    // so, parse the XML using a reader or some string operations.

    // It is in Base64, so if you need it as a byte array you'll also
    // have to decode it from Base64 to a byte array.  But, that is
    // up to you, and depends what format you want the prime in.
}

Yep... just 2 lines of code! To convert it to a BigInt is about 5 lines of code. Feel free to donate beer.

Here is the format of the xml, all values are Base64 encoded ...

<RSAKeyValue>
    <Modulus> ... </Modulus>
    <Exponent> ... </Exponent>
    <P> Your prime 'P' of the required size </P>
    <Q> another useful prime 'Q', close in size to 'P' </Q>
    <DP> ... </DP>
    <DQ> ... </DQ>
    <InverseQ> ... </InverseQ>
    <D> ... </D>
</RSAKeyValue>

Now, I have deliberately avoided showing how to parse the Base64 as only you know where you want to store this number. But, there are plenty of snippets here on CodeProject which show how to parse XML (or, alternatively, split up strings) and decode Base64 into binary bytes. It's not a big deal.

One warning though... if you are going to put it into a container that is unsigned, you need to follow the rules - as the representation you get from the Base64 will be UNsigned but MIGHT have the most significant bit set.

So, if you want to put it into a System.Numerics.BigInteger ... remember that you should make the byte array one byte larger than the number requires. This is because the byte array needs to have an added zero to ensure that BigInteger doesn't consider it to be negative.


And, that's that : )

Now you know how to generate large primes between 48 bytes (384 bits) and 2048 bytes (16,384 bits) without messing around with guessing games or using large tables of primes... and all in just a few lines of code.

And, all we had to do was abuse the RSACryptoServiceProvider class into doing our bidding ; )

Hope that helps someone.


EDIT: Answer extended - Quick & dirty example of parsing into a BigInteger

using system.security.cryptography;
using system.numerics;

using (RSACryptoServiceProvider myRsa = new RSACryptoServiceProvider(1024))
{
    byte[] sbin; // The raw byte array (looks signed)
    byte[] ubin; // The cooked byte array

    // Export RSA certificate to an XML string
    String xml = myRsa.ToXmlString(true);

    // Locate <P> in the Base64 certificate (quick and dirty code)
    int s = xml.IndexOf("<P>")+3;
    int l = xml.IndexOf("<",s)-s;
    // Convert P from Base64 to a raw byte array
    sbin = Convert.FromBase64String(xml.Substring(s, l));
    // Postfix a null byte to keep BigInteger happy
    ubin = new byte[sbin.Length + 1]; ubin[sbin.Length] = 0;
    Buffer.BlockCopy(sbin, 0, ubin, 0, sbin.Length);
    // Convert the bytes into positive BigNumber
    BigInteger bigprime = new BigInteger(ubin);

    // Write it to the console
    Console.WriteLine(bigprime);
}