Finding large devious primes

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).