>>332>>333 本物です。typoしちゃったんです。 >>331 >e1 ≠ a * e >e2 ≠ x * e >であり、なおかつ、 >e*((a*M1)+(x*M2)) > n >から >(M1*e1)+(M2*e2) > n >が言えると、主張するんだな？ 言えますよ。ビット数で考えてみてください。 e<nでe,nのビット数をNとします。 e1=a*e mod n e2=x*e mod n だから、e1,e2もNビットにできます。 というか、e1,e2がNビットになるようにeを調節する C=e*((a*M1)+(x*M2)) mod nと変形できる =(e mod n)*(((a*M1)+(x*M2)) mod n) ここで、(a*M1)+(x*M2) について考える (a*M1)+(x*M2)<nとなるようにnを選んでいる >>282の1-7行辺りより a,x,M1,M2 とnのビット数の比は約1：2 ∴a,x,M1,M2≒(1/2)Nビット (a*M1)+(x*M2) は約Nビットとなる e<n,(a*M1)+(x*M2)<nだから (e mod n)*(((a*M1)+(x*M2)) mod n) =e*((a*M1)+(x*M2)) eはNビット,(a*M1)+(x*M2)は約(1/2)Nビットだから e*((a*M1)+(x*M2))は約(3/2)Nビットとなる これはnのビット数Nより大きい ∴(M1*e1)+(M2*e2) > n
