6
$\begingroup$

Call a prime $p$ devious if $(p-1)/2$ is a Carmichael number. They are called devious since they superficially look like safe primes but are not. In particular, Diffie-Hellman using such a prime could be vulnerable to the Pohlig Hellman algorithm.

Devious primes exist. A small example is $4931$. A more interesting example is

$$1947475860046218323 = 2(973737930023109161) + 1 = 2(220361)(1542521)(2864681) + 1.$$

Surely such primes must appear in the literature, but my search efforts have drawn a blank, possibly because they are called something else (I just coined "devious" for the purpose of this question). Does anyone know of any references for them?

I am interested in generating large examples of such things. The main tool that I know for generating examples of large Carmichael numbers (search for $k$ for which $6k+1, 12k+1, 18k+1$ are all prime then take their product) seems to fail to produce such examples. Devious primes, assuming that large ones exist at all, are doubtless vanishingly rare so simply fishing for them isn't a promising approach. At this stage I am out of ideas.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ The first few ones are 1123, 4931, 303060803, 348705283, 1368212803, 1879894019, 12195557923. That sequence is not currently at OEIS. $\endgroup$ Commented Nov 11, 2021 at 18:32
  • $\begingroup$ @fgrieu Interesting that it isn't in OEIS. There are of course two closely related sequences, that of the primes of this form and that of the Carmichael numbers which give rise to them (pseudo-sophie germains?). $\endgroup$ Commented Nov 12, 2021 at 19:39

1 Answer 1

Reset to default
5
$\begingroup$

The issue with using Chernick's expression $(6k+1)(12k+1)(18k+1)$ and its generalisations is that the number is always congruent to 1 mod 3 so that twice the number plus one is divisible by and hence not prime. All is not lost however and the methods of Loh and Niebur "A new algorithm for constructing large Carmichael numbers" (which inspired the famous Alford, Granville and Pomerance "There are infinitely many Carmichael numbers" result) can be used to produce large Carmichael numbers that are 2 mod 3 and that have many factors (making them suitable for your devious application).

Taking our cue from Loh and Niebur's Algorithm C (p. 285) we add small extra conditions:

  1. Choose a product of prime powers $\Lambda\leftarrow 2^{h_1}q_2^{h_2}\cdots q_r^{h_r}$ where the $h_i$ are all positive and none of the $q_i$ are 3. (The construction works best if the $q_i$ are small primes, so taking $q_2=5$, $q_3=7$ and so on is a good choice).
  2. Test all $p(\alpha_1,\ldots,\alpha_r)\leftarrow 2^{\alpha_1}q_2^{\alpha_2}\cdots q_r^{\alpha_r}+1$ with $0\le \alpha_i\le h_i$ for primality. Collecting successful values into a set $\mathcal S$ (omitting $\Lambda+1$). You may wish to omit the prime 3 in case having a putative prime divisible by 3 is a bit obvious or because it's a likely choice for a base for a Fermat test.
  3. Compute $\prod_{p\in\mathcal S}\pmod\Lambda$ and call this residue $s$.
  4. Test subsets $\mathcal T\subset\mathcal S$ whose cardinality has different parity to $\mathcal S$ until we find a subset such that $\prod_{p\in\mathcal T}p\equiv s\pmod\Lambda$
  5. Set $N=\prod_{p\in\mathcal S\backslash\mathcal T}p$. This will be a Carmichael number, it will have an odd number of prime factors and will be congruent to 2 mod 3.

There should be enough variety in the choices of $\mathcal T$ to get a Carmichael number of an appropriate size. You can then multiply by two and add one. As the resulting number is congruent to $3\pmod\Lambda$, it will not be divisible by any prime dividing $\Lambda$ and has a much better than average chance of being prime (which is nice).

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Thank you for this. My motivation is to have an interesting example for an intro to cryptography class that I am teaching. I mentioned to the class how PGP used (still?) a simple Fermat test to find large primes. I remarked that it was actually reasonable enough for randomly generated numbers but would fail for a number designed to defeat it. I want to show that it could also be problematic for a prime designed to undermine DH. Hopefully this weekend I'll have time to experiment with this. $\endgroup$ Commented Nov 12, 2021 at 19:35
  • $\begingroup$ $p = 19248540273487192628727638093418570989399483505551360003$ is a 56-digit devious prime that I was able generate using your idea. $(p-1)/2$ is a Carmichael number with 19 prime factors. Discrete logs for this $p$ can be recovered in a fraction of a second. Your algorithm seems quite sensitive to the choice of the initial primes and powers. Once they pass a certain threshold I seem unable to find candidate $\mathcal T$. $\endgroup$ Commented Nov 14, 2021 at 17:58
  • $\begingroup$ After letting my (non-optimized) code churn away for about an hour, I found p = 535528299911273231318261682611857786128733492376235786223632658066997780843716220764905747558932241929032637097264301018240352003, which is a 129-digit devious prime for which $(p-1)/2$ is a Carmichael number with 37 prime factors. The Loh-Neibuhr paper contains references to methods for producing large Carmichael numbers with a small number of factors. I might look at those to try to construct large devious primes that could resist casual attempts at factoring $p-1$. $\endgroup$ Commented Nov 16, 2021 at 17:57

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.