RSA 암호화는 다음 절차를 따릅니다:

서로 다른 두 소수 p와 q를 생성합니다.
n=pq과 φ=(p-1)(q-1)를 계산합니다.
gcd(e,φ)=1인 정수 e, 1<e<φ를 고릅니다.

RSA 시스템에서 메시지는 범위 [0,n-1] 안의 수입니다.
암호화할 문서를 어떤 식으로든 (범위 [0,n-1]안의 수인) 메시지들로 변환합니다.
문서의 암호화는, 각각의 평문 메시지 m에 대하여, 암호 메시지 c=m^e mod n를 계산하는 것입니다.

문서의 복호화는 다음과 같습니다: ed=1 mod φ가 되는 d를 찾습니다, 그리고 각각의 암호 메시지 c에 대하여 평문 메시지 m=c^d mod n을 계산합니다.

어떤 e와 m에서는 m^e mod n=m입니다. 즉, 평문과 암호 메시지가 같습니다.
m^e mod n=m인 경우 메시지 m을 드러난 메시지라고 합니다.

e를 고를 때는 드러난 메시지가 너무 많지 않도록 해야합니다.
예를 들어, p=19, q=37이라고 하면,
n=19*37=703이고 φ=18*36=648입니다.
e=181을 고르면, 비록 gcd(181,648)=1이라도 m^e mod n을 계산해보면
모든 m (0≤m≤n-1) 메시지가 드러나 버립니다.
어떤 e를 고르더라도 드러난 메시지는 존재합니다.
드러난 메시지의 수를 최소화하는 것이 중요합니다.

p=1009, q=3643일 때,
드러난 메시지의 수가 최소가 되는 1<e<φ(1009,3643)이고 gcd(e,φ)=1인 모든 e값의 합을 구하세요.