

A318555


"Strong impostors" not divisible by 4: Those numbers s !== 0 (mod 4) such that lambda(s)  2(s1), where lambda is the Carmichael function (A002322).


1



6, 15, 66, 91, 435, 561, 703, 946, 1105, 1729, 1891, 2465, 2701, 2821, 2926, 3367, 5551, 6601, 8646, 8695, 8911, 10585, 11305, 12403, 13981, 15051, 15841, 16471, 18721, 23001, 26335, 29341, 30889, 38503, 39865, 41041, 46657, 49141, 52633, 53131, 62745, 63973, 68101, 75361, 76627, 76798, 79003, 88561, 88831, 91001
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Strong impostors not == 0 (mod 4) have the property that, even though they are composite, when paired with any odd prime r such that (s,r) = 1, they produce valid RSA key pairs. More specifically, if n=sr, all a in Z_n will be correctly encrypted and decrypted for any (e,d) key pair such that ed == 1 mod (s1)(r1). They include the Carmichael numbers and are squarefree. The set of their odd prime factors is always normal: If p_i and p_j are odd prime factors, no p_i == 1 mod p_j.


LINKS



MATHEMATICA

Reap[For[s = 1, s < 10^5, s++, If[!Divisible[s, 4] && CompositeQ[s], If[ Divisible[2(s1), CarmichaelLambda[s]], Print[s]; Sow[s]]]]][[2, 1]] (* JeanFrançois Alcover, Feb 18 2019 *)


PROG

(Python with numbthy library)
for s in range(min_s, max_s):
if numbthy.is_prime(s):
continue
elif s % 4 == 0:
continue
elif (2*(s1) % numbthy.carmichael_lambda(s) == 0):
print("s =", s)
(PARI) isok(s) = s>1 && s%4>0 && !isprime(s) && (2*s2)%lcm(znstar(s)[2])==0; \\ Jinyuan Wang, Mar 01 2020


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



