かわぐちさんの素因数発見アルゴリズムを用いない、初歩的なRSA暗号の解き方

かわぐちさんの素因数発見アルゴリズムを用いない、初歩的なRSA暗号の解き方

求める数$:=p$
商$:=d$
割る数$:=n$
余り$:=c$
適当に求める数$:=p_2$
適当な商$:=d_2$
前提として
$p=dn+c\cdots (a)$
今適当に$d_2$を決めて$p_2$を求めると
$p_2=d_{2}n+c\cdots (b)$
差を取って

$p_2-p=n(d_2-d)$

$p=p_2-d_{2}n+dn\cdots (c)$

$(b)$より
$c=p_2-d_{2}n$
変形して
$n=(p_2-c)/d_2\cdots (d)$
$(d)$を$(a)$に代入して
$p=d(p_2-c)/d_2+c$

$d/d_2=D$とおくと
$p=(p_2-c)D+c$

$0<D<1$かつ、$D(p_2-c)\in \mathbb{N}$
なので、総当りで求められる。