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

Published on 12 May 2024 09:40 PM
#D

How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the D 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 D programming language

Source code in the d programming language

enum mod = (in int n, in int m) pure nothrow @nogc=> ((n % m) + m) % m;

bool isPrime(in uint n) pure nothrow @nogc {
  if (n == 2 || n == 3)
    return true;
  else if (n < 2 || n % 2 == 0 || n % 3 == 0)
    return false;
  for (uint div = 5, inc = 2; div ^^ 2 <= n;
     div += inc, inc = 6 - inc)
    if (n % div == 0)
      return false;
  return true;
}

void main() {
  import std.stdio;

  foreach (immutable p; 2 .. 62) {
    if (!p.isPrime) continue;
    foreach (immutable h3; 2 .. p) {
      immutable g = h3 + p;
      foreach (immutable d; 1 .. g) {
        if ((g * (p - 1)) % d != 0 || mod(-p * p, h3) != d % h3)
          continue;
        immutable q = 1 + (p - 1) * g / d;
        if (!q.isPrime) continue;
        immutable r = 1 + (p * q / h3);
        if (!r.isPrime || (q * r) % (p - 1) != 1) continue;
        writeln(p, " x ", q, " x ", r);
      }
    }
  }
}

You may also check:How to resolve the algorithm String length step by step in the Rust programming language
You may also check:How to resolve the algorithm Generic swap step by step in the Julia programming language
You may also check:How to resolve the algorithm Accumulator factory step by step in the Nim programming language
You may also check:How to resolve the algorithm Tokenize a string step by step in the Zsh programming language
You may also check:How to resolve the algorithm Euler's identity step by step in the Mathematica/Wolfram Language programming language