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

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

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

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

$p=p_2-d_2n+dn\cdots(c)$

$(b)$より
$c=p_2-d_2n$
変形して
$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)∈\mathbb{N}$
なので、総当りで求められる。