标签：#編碼算法

蒙哥马利算法

在模算數領域，蒙哥馬利模乘()、蒙哥馬利乘算()是一种快速大数（通常是几百個二進位）模乘算法， 由彼得·蒙哥马利在1985年提出。 一般以傳統方式計算模乘 時，是將乘積 除以 並取餘數，然而除法需要相當消耗時間的商數位估算和校正。因此蒙哥馬利模乘引入了一種特殊的數字表達形式「蒙哥馬利型()」。將 與 轉化為蒙哥馬利型後，計算在蒙哥馬利型下的 。令 為一整數常數且與 互質，则记 的蒙哥马利形式为。在計算蒙哥馬利演算法的過程中，唯一必要的除…