如果 $N$ 可以分解成 $p,q,r\cdots$ 可以透過歐拉函式輕易找出 $\phi(N)$

$$\phi(N) = N\times \frac{(p-1)}{p}\times\frac{(q-1)}{q}\times\frac{(r-1)}{r}\times\frac{(s-1)}{s}\cdots$$

如果 e 和 $\phi(N)$ 互質：

• 直接反函數 invmod( $e$, $\phi(N)$ ) 求 $d$

• $d \equiv e^{-1} \ mod \ \phi(N)$

• 那麼 ${m}^{ed} \equiv c^d \ \equiv m \ \ mod\ p$ ，就可以解出 m

( 如果不互質 [ ex : phi 為 e 的倍數 ]，模反函數將不存在，$k*e \not\equiv 1\ mod\ N$ )

如果 e 和 $\phi(N)$ 非互質：分成質數 p,q,r,s …

• ${m}^e \equiv c_1 \ mod\ p$
• ${m}^e \equiv c_2 \ mod\ q$
• ${m}^e \equiv c_3 \ mod\ r$
• ${m}^e \equiv c_4 \ mod\ s$
  $\ \ \ \ \ \ \ \ \ \ \vdots$
• ${m}^e \equiv c_n \ mod\ n$

1. 如果 e 和 $\phi(p)$ 互質：如上，直接反函數求 $d_p$ ：

   • ${m_1}^e \equiv c \ mod\ p$

   • ${m_1}^{e\times d_p} \equiv c^{\ d_p} \ \equiv m_1 \ mod\ p$

2. 如果 e 和 $\phi(p)$ 不互質，必須先解出他的根：

   • ${m_1}^e \equiv c \ mod\ p$

   • ${m_1} \equiv \sqrt[e] c \ mod\ p$

   • 最後找出 $m_1 = [r_1,r_2,r_3,r_4,……,r_n]$

開根號的方法，可以參考 cube_root.sage, rth_root.sage

最後再用中國餘數定理，合成出原本的 m