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

Published on 12 May 2024 09:40 PM
#Arturo

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

Source code in the arturo programming language

printOneLine: function [a,b,c,d]->
    print [
        pad to :string a 3 "x" 
        pad to :string b 5 "x" 
        pad to :string c 5 "=" 
        pad to :string d 10
    ]

2..61 | select => prime?
      | loop 'p ->
            loop 2..p 'h3 [
                g: h3 + p
                loop 1..g 'd ->
                    if and? -> zero? mod g*p-1 d
                            -> zero? mod d+p*p h3 [

                        q: 1 + ((p-1)*g)/d

                        if prime? q [
                            r: 1 + (p * q) / h3

                            if and? [prime? r]
                                    [one? (q*r) % p-1]->
                                printOneLine p q r (p*q*r)
                        ]
                    ]
            ]

You may also check:How to resolve the algorithm Empty string step by step in the Euphoria programming language
You may also check:How to resolve the algorithm 4-rings or 4-squares puzzle step by step in the PL/SQL programming language
You may also check:How to resolve the algorithm Function definition step by step in the Plain English programming language
You may also check:How to resolve the algorithm Return multiple values step by step in the Lasso programming language
You may also check:How to resolve the algorithm Roman numerals/Encode step by step in the Python programming language