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

Published on 12 May 2024 09:40 PM
#Nim

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

Source code in the nim programming language

import strformat

func isPrime(n: int64): bool =
  if n == 2 or n == 3:
    return true
  elif n < 2 or n mod 2 == 0 or n mod 3 == 0:
    return false
  var `div` = 5i64
  var `inc` = 2i64
  while `div` * `div` <= n:
    if n mod `div` == 0:
      return false
    `div` += `inc`
    `inc` = 6 - `inc`
  return true

for p in 2i64 .. 61:
  if not isPrime(p):
    continue
  for h3 in 2i64 ..< p:
    var g = h3 + p
    for d in 1 ..< g:
      if g * (p - 1) mod d != 0 or (d + p * p) mod h3 != 0:
        continue
      var q = 1 + (p - 1) * g div d
      if not isPrime(q):
        continue
      var r = 1 + (p * q div h3)
      if not isPrime(r) or (q * r) mod (p - 1) != 1:
        continue
      echo &"{p:5} × {q:5} × {r:5} = {p * q * r:10}"

You may also check:How to resolve the algorithm SHA-1 step by step in the Java programming language
You may also check:How to resolve the algorithm Run-length encoding step by step in the Oforth programming language
You may also check:How to resolve the algorithm Bitwise IO step by step in the Phix programming language
You may also check:How to resolve the algorithm Entropy/Narcissist step by step in the Julia programming language
You may also check:How to resolve the algorithm Knapsack problem/Unbounded step by step in the Wren programming language