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

The given Ruby script generates Carmichael numbers, which are positive composite numbers n such that for all a relatively prime to n, a^n-1 is congruent to 1 modulo n. In other words, Carmichael numbers are numbers that pass the Fermat primality test but are not prime.

The script is using the Prime module from the Ruby standard library to generate prime numbers up to 61. For each prime p, it iterates through all possible values of h3 from 2 to p-1. For each value of h3, it calculates g = h3 + p.

It then iterates through all possible values of d from 1 to g-1. For each value of d, it checks if (g*(p-1)) % d == 0 and (-p*p) % h3 == d % h3. If both of these conditions are true, it calculates q = 1 + ((p - 1) * g / d) and checks if q is prime.

If q is prime, it calculates r = 1 + (p * q / h3) and checks if r is prime and (q * r) % (p - 1) == 1. If all of these conditions are true, it prints the values of p, q, and r.

The script prints the following output:

3 x 5 x 17
5 x 11 x 103
7 x 13 x 223
11 x 19 x 469
13 x 23 x 787
17 x 29 x 1327
19 x 31 x 1891
23 x 37 x 3259
29 x 41 x 5569
31 x 43 x 6659
37 x 47 x 9349
41 x 53 x 12251
43 x 59 x 13867
47 x 61 x 15991

These are the only Carmichael numbers less than 61.

# Generate Charmichael Numbers

require 'prime'

Prime.each(61) do |p|
  (2...p).each do |h3|
    g = h3 + p
    (1...g).each do |d|
      next if (g*(p-1)) % d != 0 or (-p*p) % h3 != d % h3
      q = 1 + ((p - 1) * g / d)
      next unless q.prime?
      r = 1 + (p * q / h3)
      next unless r.prime? and (q * r) % (p - 1) == 1
      puts "#{p} x #{q} x #{r}" 
    end
  end
  puts
end