static bool safe_prime_check()

in src/cg21/cg21_utilities.c [204:244]

• 29 lines of code
• 4 McCabe index (conditional complexity)

static bool safe_prime_check(BIG_1024_58 *p, BIG_1024_58 *P, csprng *RNG, int n)
{
#ifndef C99
    BIG_1024_58 Pm1[FFLEN_2048];
    BIG_1024_58 f[FFLEN_2048];
#else
    BIG_1024_58 Pm1[n];
    BIG_1024_58 f[n];
#endif

    // Sieve small primes from P, p is already checked in Miller-Rabin
    sign32 sf=4849845;/* 3*5*.. *19 */

    if(FF_2048_cfactor(P, sf, n))
    {
        return false;
    }

    // Check primality of p
    if (FF_2048_prime(p, RNG, n) == 0)
    {
        return false;
    }

    // Simplified primality check for safe primes using
    // Pocklington's criterion
    //
    // If p is prime, P = 2p+1, 2^(P-1) = 1 mod P, then P is prime
    FF_2048_init(f, 2, n);
    FF_2048_copy(Pm1, P, n);
    FF_2048_dec(Pm1, 1, n);

    FF_2048_nt_pow(f, f, Pm1, P, n, n);
    FF_2048_dec(f, 1, n);
    if (FF_2048_iszilch(f, n))
    {
        return true;
    }

    return false;
}