Rabin暗号
x q = ( y + B 2 4 ) ( q + 1 ) / 4 − B 2 mod q {\displaystyle x_{q}={\left(y+{\frac {B^{2}}{4}}\right)}^{(q+1)/4}-{\frac {B}{2}}\ {\bmod {\ }}q}
とすると、求める解 x は、(a,b) in { ( x p , x q ) {\displaystyle (x_{p},x_{q})} , ( p − B − x p , x q ) {\displaystyle (p-B-x_{p},x_{q})} , ( x p , q − B − x q ) {\displaystyle (x_{p},q-B-x_{q})} , ( p − B − x p , q − B − x q ) {\displaystyle (p-B-x_{p},q-B-x_{q})} }の4組を中国の剰余定理により、x=a mod p, x=b mod qとして求める。
Rabin暗号の解読問題は、次のように素因数分解問題へ帰着できることが示せる。 ある平文 x1 に対応する暗号文 y1 を与えられたときに、
x 2 + B x − y 1 = 0 ( mod n ) {\displaystyle x^{2}+Bx-y1=0{\pmod {n}}}
を満たす x を求めることができた場合、3/4 の確率で x1 とは異なる値 x2 が得られる。そのとき、無視できない確率で GCD(|x1+x2+B|,n) = p または q となる。