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

%I #44 May 11 2024 09:13:23

%S 6,15,66,91,435,561,703,946,1105,1729,1891,2465,2701,2821,2926,3367,

%T 5551,6601,8646,8695,8911,10585,11305,12403,13981,15051,15841,16471,

%U 18721,23001,26335,29341,30889,38503,39865,41041,46657,49141,52633,53131,62745,63973,68101,75361,76627,76798,79003,88561,88831,91001

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

%C 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.

%H Amiram Eldar, <a href="/A318555/b318555.txt">Table of n, a(n) for n = 1..8000</a> (terms 1..2773 from Barry Fagin)

%H D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn, <a href="http://www.jstor.org/stable/2975213">Giuga's Conjecture on Primality</a>, Amer. Math. Monthly 103, No. 1, 40-50 (1996).

%H B. S. Fagin, <a href="https://doi.org/10.3390/info9090216">Composite Numbers That Give Valid RSA Key Pairs For Any Coprime p</a>, Information, 9, 216; doi:10.3390/info9090216.

%H J. M. Grau and Antonio Oller-Marcén, <a href="https://arxiv.org/abs/1103.3483">Generalizing Giuga's conjecture</a>, arXiv:1103.3483 [math.NT], 2011.

%t 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 *)

%o (Python with numbthy library)

%o for s in range(min_s,max_s):

%o if numbthy.is_prime(s):

%o continue

%o elif s % 4 == 0:

%o continue

%o elif (2*(s-1) % numbthy.carmichael_lambda(s) == 0):

%o print("s =",s)

%o (PARI) isok(s) = s>1 && s%4>0 && !isprime(s) && (2*s-2)%lcm(znstar(s)[2])==0; \\ _Jinyuan Wang_, Mar 01 2020

%Y Cf. A002997 (Carmichael numbers), A005117 (squarefree numbers).

%Y Subsequence of A231569.

%K nonn

%O 1,1

%A _Barry Fagin_, Aug 28 2018