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 (s-1)(r-1). 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
Amiram Eldar, Table of n, a(n) for n = 1..8000 (terms 1..2773 from Barry Fagin)
D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn, Giuga's Conjecture on Primality, Amer. Math. Monthly 103, No. 1, 40-50 (1996).
B. S. Fagin, Composite Numbers That Give Valid RSA Key Pairs For Any Coprime p, Information, 9, 216; doi:10.3390/info9090216.
J. M. Grau and Antonio Oller-Marcén, Generalizing Giuga's conjecture, arXiv:1103.3483 [math.NT], 2011.
MATHEMATICA
Reap[For[s = 1, s < 10^5, s++, If[!Divisible[s, 4] && CompositeQ[s], If[ Divisible[2(s-1), CarmichaelLambda[s]], Print[s]; Sow[s]]]]][[2, 1]] (* Jean-Franç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*(s-1) % numbthy.carmichael_lambda(s) == 0):
print("s =", s)
(PARI) isok(s) = s>1 && s%4>0 && !isprime(s) && (2*s-2)%lcm(znstar(s)[2])==0; \\ Jinyuan Wang, Mar 01 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Barry Fagin, Aug 28 2018
STATUS
approved