How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the C++ programming language

Published on 7 June 2024 03:52 AM

How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the C++ programming language

Table of Contents

Problem Statement

A lot of composite numbers can be separated from primes by Fermat's Little Theorem, but there are some that completely confound it. The   Miller Rabin Test   uses a combination of Fermat's Little Theorem and Chinese Division Theorem to overcome this. The purpose of this task is to investigate such numbers using a method based on   Carmichael numbers,   as suggested in   Notes by G.J.O Jameson March 2010.

Find Carmichael numbers of the form: where   (Prime1 < Prime2 < Prime3)   for all   Prime1   up to   61. (See page 7 of   Notes by G.J.O Jameson March 2010   for solutions.)

For a given

P r i m

e

1

{\displaystyle Prime_{1}}

Chernick's Carmichael numbers

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the C++ programming language

This C++ code finds and prints Carmichael numbers. Carmichael numbers are composite numbers n such that for every integer a relatively prime to n, a^n - 1 is divisible by n.

Here's a brief explanation of the code:

  1. The mod function calculates the modulo of n with respect to d, ensuring the result is always positive.

  2. The is_prime function checks if a given number n is prime. It follows some basic primality checks and then uses a loop to check for divisibility by prime numbers up to the square root of n.

  3. The print_carmichael_numbers function takes a prime number prime1 as input and prints Carmichael numbers based on it. It iterates through possible values of h3 and d using nested loops and calculates potential prime numbers prime2 and prime3. If these calculated numbers satisfy certain conditions and are prime, the code prints the Carmichael number formula and its value.

  4. In the main function, the code iterates through prime numbers from 2 to 61 and calls print_carmichael_numbers for each prime number, which prints Carmichael numbers based on that prime.

Source code in the cpp programming language

#include <iomanip>
#include <iostream>

int mod(int n, int d) {
    return (d + n % d) % d;
}

bool is_prime(int n) {
    if (n < 2)
        return false;
    if (n % 2 == 0)
        return n == 2;
    if (n % 3 == 0)
        return n == 3;
    for (int p = 5; p * p <= n; p += 4) {
        if (n % p == 0)
            return false;
        p += 2;
        if (n % p == 0)
            return false;
    }
    return true;
}

void print_carmichael_numbers(int prime1) {
    for (int h3 = 1; h3 < prime1; ++h3) {
        for (int d = 1; d < h3 + prime1; ++d) {
            if (mod((h3 + prime1) * (prime1 - 1), d) != 0
                || mod(-prime1 * prime1, h3) != mod(d, h3))
                continue;
            int prime2 = 1 + (prime1 - 1) * (h3 + prime1)/d;
            if (!is_prime(prime2))
                continue;
            int prime3 = 1 + prime1 * prime2/h3;
            if (!is_prime(prime3))
                continue;
            if (mod(prime2 * prime3, prime1 - 1) != 1)
                continue;
            unsigned int c = prime1 * prime2 * prime3;
            std::cout << std::setw(2) << prime1 << " x "
                << std::setw(4) << prime2 << " x "
                << std::setw(5) << prime3 << " = "
                << std::setw(10) << c << '\n';
        }
    }
}

int main() {
    for (int p = 2; p <= 61; ++p) {
        if (is_prime(p))
            print_carmichael_numbers(p);
    }
    return 0;
}


  

You may also check:How to resolve the algorithm MAC vendor lookup step by step in the Go programming language
You may also check:How to resolve the algorithm Evolutionary algorithm step by step in the V (Vlang) programming language
You may also check:How to resolve the algorithm Balanced brackets step by step in the C programming language
You may also check:How to resolve the algorithm Rot-13 step by step in the Uxntal programming language
You may also check:How to resolve the algorithm Sort stability step by step in the Phix programming language