- [Neuenschwander 04, 2.4]より。
定理(RSA-HC1)の証明のアイデア
- うまく a∈Zq* をつくって、有理数[ax]n/nを十分な精度で求めれば、x がわかる。
- 自明な精度1からはじめて、精度を再帰的に倍加していく。
定理(RSA-HC1)の証明
整数aについて、[a] := a mod n とかく。
アルゴリズムA2: n, e, y(= xe mod n)を入力として、
- u0 = 0, a0 = 1
- t ∈ [1..(l+1)]: (※ l := nのビット長)
- at = 2-1 at-1 mod n
- ut = (1/2)・(ut-1 + A1(n, e, [at-1e y]) (∈ Q)
- ※ ut = (1/2)・(ut-1 + Lsb([at-1 x])
- return x = al+1-1 floor(ul+1 n + 1/2) mod n.
[アルゴリズムA2の解析]:
t ∈ [1..(l+1)]について、
- [at x] = [2-1 at-1 x]
- = (1/2) [at-1 x] (when [at-1 x]: even)
- = (1/2) ([at-1 x] + n) (when [at-1 x]: odd)
- = (1/2) ([at-1 x] + Lsb([at-1 x]) n)
よって、
- | [at x] - ut n | = | (1/2) ([at-1 x] + Lsb([at-1 x]) n) - ut n |
- = (1/2) | [at-1 x] - ut-1 n |.
| [a0 x] - u0 n | = [x] < n に注意して
- | [al+1 x] - ul+1 n | < n / (2l+1) < 1/2
よって、
- [al+1 x] = floor(ul+1 n + 1/2)
ゆえに
- x = al+1-1 floor(ul+1 n + 1/2) mod n.
Q.E.D.
最終更新:2009年09月02日 01:04