🚀 go-pugleaf

In article <226XVB4w164w@k5qwb.lonestar.org> lrk@k5qwb.lonestar.org (Mr.  
Lyn R. Kennedy) writes:
> Also, for ANY value of n ( =p*q), there are at least nine values of m 
> (the message) that will encrypt as m. I.e. E(m) = m and D(m) = m. Three 
> of these are trivial, m=0, 1, and n-1. The other six allow factoring n. 
> For some values of e, there are more cases but I'm not sure how easy it 

E(m) = m for as many as k messages where
   k = [1+gcd(e-1,p-1)]*[1+gcd(e-1,q-1)].

The smallest value k=[1+2]*[1+2]=9 as pointed out. This is because
   gcd(e-1,p-1) >= 2 
since p and e are odd numbers; p is prime, and gcd(e,(p-1)(q-1))=1 and
thus e is odd.

Thus, you want gcd(e-1,p-1) and gcd(e-1,q-1) as small as possible.

Ref: Blakley & Borosh. Comp. & Math. with App. 5:169-178, 1979.