Step by Step solution about How to resolve the algorithm Chernick's Carmichael numbers step by step in the C programming language

This C program is designed to find the values of m that satisfy the Chernick conditions for a given value of n. Chernick's conditions are a set of divisibility and primality tests used to determine the existence of certain types of prime numbers.

Here's a detailed breakdown of the code:

• Header Files:

  • The program includes the necessary header files:
    • <stdio.h>: For input and output functions.
    • <stdlib.h>: For the exit function.
    • <gmp.h>: For the GMP (GNU Multiple Precision) library, which provides functions for handling large integer arithmetic.

• Type Definitions:

  • typedef unsigned long long int u64;: Defines a new data type alias u64 for representing unsigned 64-bit integers.

• Constants:

  • TRUE and FALSE are defined as 1 and 0, respectively, for logical comparisons.

• Functions:

  • primality_pretest: Performs a quick primality test on a given integer k. It checks divisibility by small primes (3, 5, 7, 11, 13, 17, 19, and 23) and returns TRUE if k is not divisible by any of them. Otherwise, it returns FALSE.
  • probprime: Uses the mpz_probab_prime_p function from the GMP library to perform a probabilistic primality test on k. It sets n to the value of k using mpz_set_ui and then invokes the probabilistic primality test. The function returns TRUE if k is probably prime and FALSE otherwise.
  • is_chernick: Checks if a given m satisfies the Chernick conditions for a given n. It performs the following steps:
    1. Calculates t = 9*m and performs the primality pretest on 6*m+1 and 12*m+1. If either of these is not a prime, it returns FALSE.
    2. Iterates over values of i from 1 to n-2 and performs primality pretests on (t << i) + 1. If any of these is not a prime, it returns FALSE.
    3. Uses mpz_probab_prime_p to perform probabilistic primality tests on 6*m+1, 12*m+1, and (t << i) + 1 for i from 1 to n-2. If any of these is not a probable prime, it returns FALSE.
    4. If all the primality tests pass, it returns TRUE.
  • main:
    1. Initializes an MPZ (multiple precision integer) variable z using mpz_inits.
    2. Iterates over values of n from 3 to 10.
    3. Calculates the multiplier value based on n.
    4. Iterates over values of k until it finds an m that satisfies the Chernick conditions for the given n.
    5. Once m is found, it prints the result as a(n) has m = <value of m>.
    6. Finally, it returns 0 to indicate successful program termination.

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

typedef unsigned long long int u64;

#define TRUE 1
#define FALSE 0

int primality_pretest(u64 k) {
    if (!(k %  3) || !(k %  5) || !(k %  7) || !(k % 11) || !(k % 13) || !(k % 17) || !(k % 19) || !(k % 23)) return (k <= 23);
    return TRUE;
}

int probprime(u64 k, mpz_t n) {
    mpz_set_ui(n, k);
    return mpz_probab_prime_p(n, 0);
}

int is_chernick(int n, u64 m, mpz_t z) {
    u64 t = 9 * m;
    if (primality_pretest(6 * m + 1) == FALSE) return FALSE;
    if (primality_pretest(12 * m + 1) == FALSE) return FALSE;
    for (int i = 1; i <= n - 2; i++) if (primality_pretest((t << i) + 1) == FALSE) return FALSE;
    if (probprime(6 * m + 1, z) == FALSE) return FALSE;
    if (probprime(12 * m + 1, z) == FALSE) return FALSE;
    for (int i = 1; i <= n - 2; i++) if (probprime((t << i) + 1, z) == FALSE) return FALSE;
    return TRUE;
}

int main(int argc, char const *argv[]) {
    mpz_t z;
    mpz_inits(z, NULL);

    for (int n = 3; n <= 10; n ++) {
        u64 multiplier = (n > 4) ? (1 << (n - 4)) : 1;

        if (n > 5) multiplier *= 5;

        for (u64 k = 1; ; k++) {
            u64 m = k * multiplier;

            if (is_chernick(n, m, z) == TRUE) {
                printf("a(%d) has m = %llu\n", n, m);
                break;
            }
        }
    }

    return 0;
}