How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the C++ programming language
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:
-
The
mod
function calculates the modulo ofn
with respect tod
, ensuring the result is always positive. -
The
is_prime
function checks if a given numbern
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 ofn
. -
The
print_carmichael_numbers
function takes a prime numberprime1
as input and prints Carmichael numbers based on it. It iterates through possible values ofh3
andd
using nested loops and calculates potential prime numbersprime2
andprime3
. If these calculated numbers satisfy certain conditions and are prime, the code prints the Carmichael number formula and its value. -
In the
main
function, the code iterates through prime numbers from 2 to 61 and callsprint_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