1
$\begingroup$

Is there an efficient method to construct random Carmichael-numbers with $50-100$ prime factors ?

The method with vectors $p_1,...,p_k$ , where $\frac{1}{p_1}+...\frac{1}{p_k}=1$ which gives a formula like $(6n+1)(12n+1)(18n+1)$ , which is a Carmichael number, if all the factors are prime, is useless because it is too difficult to find a number $n$, such that so many factors are simultanoeusly prime.

Erdoes method produces Carmichael numbers with not too many factors relatively easy, but it would take rather long to find a subset of $50-100$ primes with $\prod_{j=1}^k p_j\equiv 1\ (\ mod \ L)$

Do the quadratic residues help ? Which method is best to construct my own Carmichael-"monster-numbers" ?

$\endgroup$
  • $\begingroup$ For other folks landing here, this answer gives references for construction of Carmichael numbers with 1m+ and 10m+ factors. $\endgroup$ – Armadillo Jim Jan 27 '17 at 21:43
1
$\begingroup$

If you want to Construct a Carmichael number with many factors, follow this procedure:

I. First pick a "highly composite number $n$" (A number with many divisors)

II. Find all divisors of $n$ are $d_k$.

III. Construct a subset $S$ of primes $p_k$ that are relatively prime to $n$ and are of the form $d_k+1$ $=$ $p_k$, (Again, $d_k$ must divide $n$) $S$ $=$ {$p, p_2, p_3,...p_k$}

Now choose one of the following procedures based on how large your subset $S$ is:

IV. If the subset of primes $p_k$ in $S$ is small (no more than $12$ primes) you can find the product of all your primes in your subset: $p*p_2*p_3*p_4...*p_{12}$ $=$ $x$. Now find all divisors $v_k$ of $x$ and compute all $v_k$ $\pmod n$. If the result is $1$ $\pmod n$ for any $v_k$, then $v_k$ is a Carmichael number. Otherwise it is not.

V. If the subset $S$ is larger (say more than $12$ primes), multiply all the primes in your subset $S$ (as in option $4$), $p*p_2*p_3*p_4...*p_k$ $=$ $x$. Compute $x$ $\pmod n$. If the result is $1$ $\pmod n$, we have a Carmichael Number $x$ with $k$ distinct factors. If it is not $1$ $\pmod n$, then suppose that $x$ $=$ $y$ $\pmod n$. Now find a divisor of $x$ $=$ $v_k$ such that $v_k$ $=$ $y$ $\pmod n$. Then $(x/v_k)$ is a Carmichael number. If we are searching for a $v_k$ $|$ $x$ with at least $3$ distinct prime factors, then you can search for $v_k$ $|$ $x$ such that $v_k$ $=$ $1$ or $y$ $\pmod n$. If $v_k$ is $1$ $\pmod n$, (and at least $3$ distinct prime factors) we have a Carmichael number $v_k$ instead. In fact, this leads to the last (least efficient) procedure.

VI. Construct a divisor $v_k$ (must have $3$ prime factors at least) such that $v_k$ $=$ $1$ $\pmod n$. You can start multiplying primes $p_k$ from subset $S$ (only once however) until your result $\pmod n$ is $1$. The product of those primes will be a Carmichael Number.

Important: I left this out on the procedure, sorry I should have added it in earlier: If $n+1$ is prime, then do NOT include it in your subset of primes $S$ which are $p_k$. Every Carmichael number $x$ that you do construct that is not a multiple of $n+1$, $x(n+1)$ will be a Carmichael number.

Here is an example using the second of all three methods:

$2^6*3^2*5*7$ $=$ $20160$. The divisors of $20160$ are:

$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 28, 30, 32, 35, 36, 40, 42, 45, 48, 56, 60, 63, 64, 70, 72, 80, 84, 90, 96, 105, 112, 120, 126, 140, 144, 160, 168, 180, 192, 210, 224, 240, 252, 280, 288, 315, 320, 336, 360, 420, 448, 480, 504, 560, 576, 630, 672, 720, 840, 960, 1008, 1120, 1260, 1344, 1440, 1680, 2016, 2240, 2520, 2880, 3360, 4032, 5040, 6720, 10080, 20160$ (84 divisors)

The primes $p_k$ which are one more than a divisor $d_k$ of $20160$ and relatively prime to $20160$ are:

$11, 13, 17, 19, 29, 31, 37, 41, 43, 61, 71, 73, 97, 113, 127, 181, 193, 211, 241, 281, 337, 421, 449, 577, 631, 673, 1009, 2017, 2521, 3361, 20161$ (31 primes)

Remember when constructing the subset to leave out $n+1$ $=$ $20161$.

$S$ $=$ {$11, 13, 17, 19, 29, 31, 37, 41, 43, 61, 71, 73, 96, 113, 127, 181, 193, 211, 241, 281, 337, 421, 449, 577, 631, 673, 1009, 2017, 2521, 3361$}

Using method $IV$:

The product is $x$ of all the primes in subset $S$ is $17377$ $\pmod {20160}$. Now the problem is finding a $v_n$ $|$ $x$ such that $v_n$ $=$ $17377$ $\pmod {20160}$.

I started by taking the $\gcd$ of numbers of the form $17377+20160*a$, $x$. If the $\gcd(17377+20160*a, x)$ was not $1$, I divided ($x$/$\gcd(17377+20160*a, x)$ $=$ $x_2$ I repeated the process using ($x_k$/$\gcd(17377+20160*a, x)$ $=$ $x_{k+1}$ until all factors are used up in subset $S$ or we end up with a product of factors that is congruent to $1$ or $y$ $\pmod {20160}$. (But be careful not to use the same factor you removed, otherwise $x$ will not be square free).

$17377+20160*3$ $=$ $13*53*113$, (since $13$, $113$ are factors of $x$, but $53$ is not, I continue below.)

$53+20160*1$ $=$ $17*29*41$ ($17$, $29$, and $41$ are all factors of $x$ which are not $13$ or $113$.) This process is complete.

$13*17*29*41*113$ $=$ $17377$ $\pmod {20160}$

Now $(x/(13*17*29*41*113)$ $=$ $11*19*31*37*43*61*71*73*97*127*181*193*211*241*281*337*421*449*577*631*673*1009*2017*2521*3361$ $=$ $5394154199929997636795937494499572299377721256273675947201$ is a Carmichael number with $24$ prime factors.

The other methods I will not do and I suppose you could use the subset I used in this example, (eg. you could make it bigger by increasing the number of divisors, although you will have a tougher time with it, try $2^8*3^4*5^3*7^2*11*13*17*19*23*29$ $=$ $3912870465504000$ for instance or maybe $n!$ for larger numbers.

Hope this helps.

FYI the quadratic residues I find are not important for constructing larger Carmichael Numbers with many factors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.