在 RSA 中，CPU 如何處理這個巨大的模數（8192 位）？
雖然我了解 RSA 算法的工作原理，但我不了解 CPU 在需要使用
mod大量函式時如何執行 $ n $ ， 例如。$ n = 8192 $ 位；
$ c = m^e \mod n $ ;
本質上，我的問題是 CPU 如何處理這個巨大的模數？
它（或者更確切地說，在其上執行的軟體）將使用任意精度（“bignum”）算術。它的工作方式與您（可能）在學校學習紙上算術的方式基本相同。
在學校教給我們人類的算術是以 10 為基礎的算術——也就是說，我們將數字表示為由十個不同數字組成的字元串，從“0”到“9”，其中每個數字單獨代表一個低於 10的不同小數，並且將一個數字放在另一個數字的左側，將其值乘以 10。
假設您在小學時沒有完全睡覺，您可能還記得必須記住一位數的加法和乘法表：1 + 1 = 2、7 + 7 = 14、6 × 4 = 24，等等。這些是基數為 10 算術的基本“原子”操作，一旦你知道如何去做，你就可以將它們結合起來計算更大的數字。
（當然，您不必完全記住基本操作；例如，如果您忘記了 7 × 6 是什麼，但仍然記得 6 × 6 = 36，那麼您可以再數六個數字最終到 42。即使你忘記了 7 + 7 是什麼，你也可以說，指望手指到達 14。事實證明，對於我們人類來說，記住那些基本的個位數運算——即用人類等效的查找表來實現它們——使得算術比每次都從第一原理中計算出來要快得多。對於電腦，權衡可能不同。）
例如，根據您學校的數學教學方式，您可能記得在紙上寫下一個加法問題，如下所示：
Exercise: 12345 + 67890 = ______ <-- carries 12345 <-- first number + 67890 <-- second number ------- <-- result並從右到左逐位計算。在這裡，您將從 5 + 0 = 5 開始（沒有進位）：
0 <-- carries 12345 <-- first number + 67890 <-- second number ------- 5 <-- result然後繼續 4 + 9 = 13（即寫下 3，進位 1）：
10 <-- carries 12345 <-- first number + 67890 <-- second number ------- 35 <-- result然後 1 + 3 + 8 = 4 + 8 = 12（即寫下 2，進位 1），以此類推，一直到：
1110 <-- carries 12345 <-- first number + 67890 <-- second number ------- 80235 <-- result您可能還為其他基本算術運算學習過類似的紙筆算法，例如減法、乘法甚至長除法（也可用於模約簡）。需要認識到的重要一點是，所有這些計算方法都基於操作數字字元串的規則，以及對單個數字的簡單算術運算。只要你能做基本的個位數運算，並且知道將它們組合在一起的算法，你就可以在紙上用你想要（或需要）的數字做算術！
那麼電腦是如何做到的呢？他們當然可以使用與我們完全相同的十進制算術規則，但這將是非常低效的。典型的 CPU 已經具有快速電路，可以將任意兩個 32 位或 64 位（甚至可能更大）的數字與單個機器程式碼指令相加或相乘，因此將 32 位或 64 位算術視為基本建構更有意義堵塞。
因此，bignum 算術的典型電腦實現有效地處理 32 位或 64 位整數的“數字”，並將較大的數字表示為這些較小整數的字元串。所使用的算法與我們用於鉛筆和紙計算的算法非常相似，只是電腦更可能使用以 2 32或 2 64為基數的算法，而不是以 10 為基數。
例如，讓我們計算兩個隨機 128 位數字的總和（為了方便，寫成十六進制）：
Exercise: 3d96d3e9d019665051ecf94e4c0c697b + a80314053a779df7464ea2feebf771be = ______現代 CPU可能能夠直接計算，但我們假設我們只有一個 32 位 CPU 可用。幸運的是，我們可以將數字分解為 32 位塊，並使用我們之前使用的相同加法算法：
<-- carries 3d96d3e9 d0196650 51ecf94e 4c0c697b <-- first number + a8031405 3a779df7 464ea2fe ebf771be <-- second number ------------------------------------- <-- result所以首先，我們需要計算
4c0c697b + ebf771be，我們的 CPU 很容易告訴我們是13803db39（即 32 位結果3803db39，加上進位 1）：1 <-- carries 3d96d3e9 d0196650 51ecf94e 4c0c697b <-- first number + a8031405 3a779df7 464ea2fe ebf771be <-- second number ------------------------------------- 3803db39 <-- result接下來，我們要求我們的 CPU 計算
51ecf94e + 464ea2fe，並由於進位而將結果加一，這會產生983b9c4d（並且下一個位置沒有進位）：0 1 <-- carries 3d96d3e9 d0196650 51ecf94e 4c0c697b <-- first number + a8031405 3a779df7 464ea2fe ebf771be <-- second number ------------------------------------- 983b9c4d 3803db39 <-- result然後我們可以用同樣的方法處理剩下的兩個 32 位加法，得到
d0196650 + 3a779df7 = 10a910447（即0a910447進位 1）和3d96d3e9 + a8031405 + 1 = e599e7ef：0 1 0 1 <-- carries 3d96d3e9 d0196650 51ecf94e 4c0c697b <-- first number + a8031405 3a779df7 464ea2fe ebf771be <-- second number ------------------------------------- e599e7ef 0a910447 983b9c4d 3803db39 <-- result我們得到了我們的結果！
我在這個簡單的例子中使用了加法，但類似的算法可以用於其他算術運算，包括求冪和模約簡（通常將它們組合成一個模冪算法，因為將它們一起做比先做更有效取冪然後減少）。
另請注意，用於加密的算術算法往往有些專業化，因為在加密中，通過確保算法花費相同的時間來執行（並消耗大致相同的功率等），無論添加（或乘以或提高到冪等）的數字是多少。