cp's OEIS Frontend

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

%I A318555 #44 May 11 2024 09:13:23
%S A318555 6,15,66,91,435,561,703,946,1105,1729,1891,2465,2701,2821,2926,3367,
%T A318555 5551,6601,8646,8695,8911,10585,11305,12403,13981,15051,15841,16471,
%U A318555 18721,23001,26335,29341,30889,38503,39865,41041,46657,49141,52633,53131,62745,63973,68101,75361,76627,76798,79003,88561,88831,91001
%N A318555 "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 A318555 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 A318555 Amiram Eldar, <a href="/A318555/b318555.txt">Table of n, a(n) for n = 1..8000</a> (terms 1..2773 from Barry Fagin)
%H A318555 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 A318555 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 A318555 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 A318555 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 A318555 (Python with numbthy library)
%o A318555 for s in range(min_s,max_s):
%o A318555     if numbthy.is_prime(s):
%o A318555         continue
%o A318555     elif s % 4 == 0:
%o A318555         continue
%o A318555     elif (2*(s-1) % numbthy.carmichael_lambda(s) == 0):
%o A318555         print("s =",s)
%o A318555 (PARI) isok(s) = s>1 && s%4>0 && !isprime(s) && (2*s-2)%lcm(znstar(s)[2])==0; \\ _Jinyuan Wang_, Mar 01 2020
%Y A318555 Cf. A002997 (Carmichael numbers), A005117 (squarefree numbers).
%Y A318555 Subsequence of A231569.
%K A318555 nonn
%O A318555 1,1
%A A318555 _Barry Fagin_, Aug 28 2018