Step by Step solution about How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the Kotlin programming language

Extension Function isPrime:

This function extends the Int type by adding a method isPrime that checks if the integer is prime. It uses the following logic:

• If the integer is 2, it's prime.
• If the integer is less than or equal to 1 or divisible by 2, it's not prime.
• Otherwise, it checks if any integers between 3 and the square root of the integer (excluding even numbers) divide the integer evenly. If so, it's not prime. If not, it's prime.

mod Function:

This function calculates the modulo of two integers n and m. It ensures that the result is positive by adding m to the result if it's negative.

main Function:

The main function iterates through integers from 3 to 61 and checks if each is prime. For each prime number p1, it calculates g as h3 + p1, where h3 is an integer between 2 and p1. It then iterates through integers d from 1 to g and checks the following conditions:

• (g * (p1 - 1)) % d == 0: This checks if d is a factor of g * (p1 - 1).
• mod(-p1 * p1, h3) == d % h3: This checks if d is a specific residue when -p1 * p1 is divided by h3.

If these conditions are met, it calculates q as 1 + (p1 - 1) * g / d and checks if it's prime. If so, it calculates r as 1 + (p1 * q / h3) and checks if it's prime. Finally, it checks if (q * r) % (p1 - 1) == 1. If all these conditions are met, it prints the values of p1, q, and r.

fun Int.isPrime(): Boolean {
    return when {
        this == 2 -> true
        this <= 1 || this % 2 == 0 -> false
        else -> {
            val max = Math.sqrt(toDouble()).toInt()
            (3..max step 2)
                .filter { this % it == 0 }
                .forEach { return false }
            true
        }
    }
}

fun mod(n: Int, m: Int) = ((n % m) + m) % m

fun main(args: Array<String>) {
    for (p1 in 3..61) {
        if (p1.isPrime()) {
            for (h3 in 2 until p1) {
                val g = h3 + p1
                for (d in 1 until g) {
                    if ((g * (p1 - 1)) % d == 0 && mod(-p1 * p1, h3) == d % h3) {
                        val q = 1 + (p1 - 1) * g / d
                        if (q.isPrime()) {
                            val r = 1 + (p1 * q / h3)
                            if (r.isPrime() && (q * r) % (p1 - 1) == 1) {
                                println("$p1 x $q x $r")
                            }
                        }
                    }
                }
            }
        }
    }
}