いや、35=0x23=(00100011)2　だと
乗剰余が7回で少ないでしょ。
いくらフェルマー数だからっつっても
0x10001だと33回乗剰余しなくちゃいけないわけで
署名の検証・暗号化が高速なのは35のほうが高速。

でもいくら高速だっていっても35だと
>LCD（p-1, q-1)と素にならない確率が高いから、
>素数（p, q)を作成するところからやり直す
こういう短所があるから35はお勧めできない。

さらに、M^e(M>1)が法nより小さいと暗号化の意味を成さないから
eとして小さすぎる値はお勧めできない。