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

Published on 12 May 2024 09:40 PM
#Clojure

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

Source code in the clojure programming language

(ns example
  (:gen-class))

(defn prime? [n]
  " Prime number test (using Java) "
  (.isProbablePrime (biginteger n) 16))

(defn carmichael [p1]
  " Triplets of Carmichael primes, with first element prime p1 "
  (if (prime? p1)
    (into [] (for [h3 (range 2 p1)
          :let [g (+ h3 p1)]
          d (range 1 g)
          :when (and (= (mod (* g (dec p1)) d) 0)
                     (= (mod (- (* p1 p1)) h3) (mod d h3)))
          :let [p2 (inc (quot (* (dec p1) g) d))]
          :when (prime? p2)
          :let [p3 (inc (quot (* p1 p2) h3))]
          :when (prime? p3)
          :when (= (mod (* p2 p3) (dec p1)) 1)]
         [p1 p2 p3]))))

; Generate Result
(def numbers (mapcat carmichael (range 2 62)))
(println (count numbers) "Carmichael numbers found:")
(doseq [t numbers]
  (println (format "%5d x %5d x %5d = %10d" (first t) (second t) (last t) (apply * t))))

You may also check:How to resolve the algorithm Calculating the value of e step by step in the ZX Spectrum Basic programming language
You may also check:How to resolve the algorithm Arithmetic/Integer step by step in the Scheme programming language
You may also check:How to resolve the algorithm Averages/Pythagorean means step by step in the Modula-2 programming language
You may also check:How to resolve the algorithm Josephus problem step by step in the Batch File programming language
You may also check:How to resolve the algorithm Determine if a string is collapsible step by step in the APL programming language