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

Published on 12 May 2024 09:40 PM
#Wren

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

Source code in the wren programming language

import "./fmt" for Fmt
import "./math" for Int

var mod = Fn.new { |n, m| ((n%m) + m) % m }

var carmichael = Fn.new { |p1|
    for (h3 in 2...p1) {
        for (d in 1...h3 + p1) {
            if ((h3 + p1) * (p1 - 1) % d == 0 && mod.call(-p1 * p1, h3) == d % h3) {
                var p2 = 1 + ((p1 - 1) * (h3 + p1) / d).floor
                if (Int.isPrime(p2)) {
                    var p3 = 1 + (p1 * p2 / h3).floor
                    if (Int.isPrime(p3)) {
                        if (p2 * p3 % (p1 - 1) == 1) {
                            var c = p1 * p2 * p3
                            Fmt.print("$2d   $4d   $5d  $10d", p1, p2, p3, c)
                        }
                    }
                }
            }
        }
    }
}

System.print("The following are Carmichael munbers for p1 <= 61:\n")
System.print("p1     p2      p3     product")
System.print("==     ==      ==     =======")
for (p1 in 2..61) {
    if (Int.isPrime(p1)) carmichael.call(p1)
}

You may also check:How to resolve the algorithm Strip comments from a string step by step in the Factor programming language
You may also check:How to resolve the algorithm Formatted numeric output step by step in the Gambas programming language
You may also check:How to resolve the algorithm Rep-string step by step in the Phix programming language
You may also check:How to resolve the algorithm Check output device is a terminal step by step in the C++ programming language
You may also check:How to resolve the algorithm Monads/Maybe monad step by step in the ATS programming language