Function ProvablePrime

src/cryptlib/nbtheory.cpp:380–420

}

Integer ProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
{
    const unsigned smallPrimeBound = 29, c_opt=10;
    Integer p;

    BuildPrimeTable();
    if (bits < smallPrimeBound)
    {
        do
            p.Randomize(rng, Integer::Power2(bits-1), Integer::Power2(bits)-1, Integer::ODD);
        while (TrialDivision(p, 1 << ((bits+1)/2)));
    }
    else
    {
        const unsigned margin = bits > 50 ? 20 : (bits-10)/2;
        double relativeSize;
        do
            relativeSize = pow(2.0, double(rng.GetLong())/0xffffffff - 1);
        while (bits * relativeSize >= bits - margin);

        Integer a,b;
        Integer q = ProvablePrime(rng, unsigned(bits*relativeSize));
        Integer I = Integer::Power2(bits-2)/q;
        Integer I2 = I << 1;
        unsigned int trialDivisorBound = (unsigned int)STDMIN((unsigned long)primeTable[primeTableSize-1], (unsigned long)bits*bits/c_opt);
        bool success = false;
        do
        {
            p.Randomize(rng, I, I2, Integer::ANY);
            p *= q; p <<= 1; ++p;
            if (!TrialDivision(p, trialDivisorBound))
            {
                a.Randomize(rng, 2, p-1, Integer::ANY);
                b = a_exp_b_mod_c(a, (p-1)/q, p);
                success = (GCD(b-1, p) == 1) && (a_exp_b_mod_c(b, q, p) == 1);
            }
        }
        while (!success);
    }
    return p;
}

Integer CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
{