To find a prime number larger than a given starting number, the program simply considers increasingly large numbers until it finds one that is probably prime. The following FindNextPrime method does just that:  

// Find a prime at least as large a startNumber and with at least the 
// given probability of being prime.
// Return the number, probability, and number of tests performed.
public static BigInteger FindNextPrime(this BigInteger startNumber

,
    double desiredProb, out double primeProb, out int numTests)
{
    // Make sure the start number is odd.
    if ((startNumber != 2) && (startNumber % 2 == 0)) startNumber++;

    // Calculate the number of tests we need to run to achieve the 
    // desired probability.
    numTests = (int)Math.Log(1.0 / (1.0 - desiredProb), 2) + 1;

    // Test values until we find a prime.
    for (BigInteger p = startNumber; ; p += 2)
    {
        primeProb = p.ProbabilityIsPrime(numTests);
        if (primeProb > 0.1) return p;
    }
}

The method first ensures that the number is either 2 or odd. If the number is 2, then it is prime. If the number is even and not 2, the code makes the number odd because no even numbers other than 2 are prime.

Next, the code calculates the number of tests that it must make to ensure the desired probability. The code then enters a loop that begins at startNumber and considers increasingly large numbers. It calls ProbabilityIsPrime for each number and returns that number if it is probably prime.

The FindPrimes example solution shows that the next prime larger than 1 trillion is 1,000,000,000,039. Download the example solution to see additional details.