Help on Constructing a Carmichael number from an algorithm

Question

A quick definition of a Carmicheal number:

A composite integer $n$ such that all integers $a$ relatively prime to $n$, it is true that $a^{n-1}$ $=$ $1$ $\pmod n$ (Composite numbers satisfying Fermat's Little Theorem whenever $\gcd(a, n$) $=$ $1$))

I am trying to construct a Carmichael number from scratch using algorithm C from here on page 825. Reference:

(Copied directly)

Algorithm C C1 [Start]. Choose an appropriate product of prime powers $\Lambda \leftarrow q_1^{h1} q_2^{h2} ...q_r^{hr}$ (with $q_1 = 2$ and $hj > 0$ for all $j$).

C2 [Combine qj ]. Build all p(α1, α2,...,αr) $\leftarrow 2^{α1} q_2^α2 q_r^{αr} +1$ with $1 ≤ α1 ≤ h1$ and $0 ≤ αj ≤ hj$ for $j > 1$.

C3 [Collect admissible factors]. Put all p(α1, α2,...,αr), if they are prime and different from every qj , j = 2, 3,...,r, into the set S. If Λ + 1 ∈ S, set S←S $\backslash$ {Λ+1}. [In this case, every Carmichael number with λ(N)=Λ found by the algorithm can be multiplied by Λ+1 to give another Carmichael number, see property (b).] Build $s ← (Q_p ∈ S_p) \bmod Λ$. If s = 1, set T ← ∅ and continue with C5.

C4 [Find T ]. Find a set T ⊂S with Q p∈T p ≡ s (mod Λ). C5 [Construct Carmichael number]. Now N = Y p∈SrT p is a Carmichael number.

I started with the product: $2^2*3*5*11*17*31*59*61$ $=$ $1251804180$ $=$ $P-1$. Now let $2^2*3*5*11*17*31*59*61+1$ $=$ $1251804181$ $=$ $P$ is a prime. I am confused at step two since the only prime factors in the subset $S$ are $P$ and those dividing $P-1$. Can someone help finish the construction. Thanks in advance.

I am unsure weather $P$ | $N$ where $N$ is our resulting Carmicheal number. I know from reading the .pdf file that when $q$ and $nq+1$ are primes, a Carmicheal number is never divisible by both $q$ and $nq+1$. So if $N$ | $P$ then $N\nmid (2, 3, 5, 11, 17, 31, 59, 61)$.

Despite the post earlier, I chose 6 of 62 of the primes found by Joffan:

$D$ $=$ $4013*158357*241429*310931*347821*624031$ $=$ $290539349$ $\pmod {1251804180}$.

The modulo inverse of $D$ is $895667609$. Therefore finding a number $B$ with the 62 primes factors coprime to $D$ congruent to $895667609$ $\pmod {1251804180}$, $BD$ should result in a Carmichael number. Substantially adding prime factors to these gives me a $1$ in $1.25*10^9$ chance of a Carmichael number occuring.

What about choosing other sets, say $2^5*3*5*7*73*3084468319$ = $756558389284320$ $=$ $Λ$. $13*29*41*43*71*113*337*421$ $=$ $756558389284321$ = $Λ + 1$ is not prime, however it is a Carmichael number. Would that still give me the the additional Carmichael number, $p$($Λ + 1$) for every Carmichael number $p$ I construct with the set $2^5*3*5*7*73*3084468319$ $756558389284320$ $=$ $Λ$?

Answer 1

I started with the product: $2^2*3*5*11*17*31*59*61$ $=$ $1251804180$ $=$ $P-1$.

Woah, where did $P$ spring from? $2^2*3*5*11*17*31*59*61$ $=$ $1251804180$ $= \Lambda$.

Now the candidate prime set is formed by taking every even factor of $\Lambda$ and adding one; if this value is prime, it is added to the candidate prime set.

Now let $2^2*3*5*11*17*31*59*61+1$ $=$ $1251804181$ $=$ $P$ is a prime.

This is not essential to the method. You can ignore $\Lambda+1$ - whether it is prime or not makes no difference to the method or the potential for success in constructing a Carmichael number. If it happens that $\Lambda+1$ is prime, then any Carmichael numbers $c_j$ that you generate have a "free" additional Carmichael number, $(\Lambda+1)c_j$

There are $62$ primes in the candidate set for your starting product:

$$\{ 7,13,23,67,103,311,331,367,373,661,683,709,733,1021,1123,1181,1831,1861,1871,3163,3541,3659,4013,4027,4093,6491,7789,8053,12037,13421,18911,19471,22067,23189,30091,41603,43189,56731,68443,107971,109741,158357,192883,241429,244733,310931,342211,347821,395891,624031,734197,1248061,1928821,2231381,2375341,3536171,3670981,4038079,4104277,6840461,8076157,250360837 \}$$

Answer 2

Rather than addressing your example head-on, I'll illustrate the process with a really simple $\Lambda = 2^2\cdot3\cdot5\cdot7$

Then the even factors of $\Lambda$ are $ \{2,4,6,10,12,14,20,28,30,42,60,70,84,140,210,420\}$; adding one to each gives $ \{3, 5, 7, 11, 13, 15, 21, 29, 31, 43, 61, 71, 85, 141, 211, 421\}$ then weeding out composites and factors of $\Lambda$ gives $ \{11, 13, 29, 31, 43, 61, 71, 211, 421\}$ and finally removing $\Lambda +1 = 421$, which happens to be prime, gives $ S =\{11, 13, 29, 31, 43, 61, 71, 211\}$ . I will explain later in the process why removing $\Lambda +1$ doesn't hurt our chance of finding Carmichael numbers.

Now according the overview, we find $\prod S \bmod \Lambda$, which is $311$. Since this isn't $1$, we can't just multiply all members of $S$ together and declare that we have found a Carmichael number. Note that keeping $421$ in set $S$ would have made no difference to this modular result.

So we need to find a subset of $S$, called $T$, that also has $\prod T \bmod \Lambda = 311$. Then we would know that $\prod (S\backslash T) \bmod \Lambda = 1$ and the elements of $ (S\backslash T)$ mulitplied together will be a Carmichael number.

But for reasonably challenging numbers, we don't want to just go fishing around for a subset $T$ with a matching modulus, which is where the interesting part of the algorithm begins. Instead of trying to match one big number, we'll match a number of smaller numbers - in this case relative to four moduli, the prime (power) components of $\Lambda$ . So now each member of $S$ has a quad of residues associated with it:

$$\begin{array}{r|c} \text{modulus:} & 2^2 & 3 & 5 & 7 \\ \hline 11 & 3 & 2 & 1 & 4 \\ 13 & 1 & 1 & 3 & 6 \\ 29 & 1 & 2 & 4 & 1 \\ 31 & 3 & 1 & 1 & 3 \\ 43 & 3 & 1 & 3 & 1 \\ 61 & 1 & 1 & 1 & 5 \\ 71 & 3 & 2 & 1 & 1 \\ 211 & 3 & 1 & 1 & 1 \\ \hline \prod S & 3 & 2 & 1 & 3 \\ \end{array}$$

And without getting too deep into the process, we can work back across the values to match the $(3,2,1,3)$ of $\prod S$ with a subset. In this case $31$ will match the $7$ modulus, then we can choose from those elements with $p \equiv 1 \bmod 7$ to match the remaining requirements. Setting $T = \{31, 71, 211\}$ gives the required match here and so $11\cdot 13 \cdot 29\cdot 43\cdot 61 =10877581$ is a Carmichael number.

Note that the quad for $\Lambda+1=421$ is $(1,1,1,1)$, so it makes no difference to the process, whether included or excluded - so for the sake of simplicity, it is left to one side while the matching process goes on. Since, in this case, it is prime, we can get a second Carmichael number, $421\cdot 10877581 = 4579461601$ .