試劃分的時間複雜度
認為 $ n=pq $ ， 在哪裡 $ p,q $ 是素數。
讓 $ p ( \le q) $ 是最小的素數，那麼我們知道 $ p \le \sqrt{n} $ .
在跟踪劃分中，我們檢查 $ n \mod i $ 對於值 $ i $ 從 2 到 $ \sqrt{n} $ , 求值 $ p $ 然後我們計算 $ \dfrac{n}{p} $ 要得到 $ q $ .
一般來說，時間複雜度是（假設求餘數和除法發生在常數時間內） $ \sqrt{n} $ .
如何計算密碼時間複雜度？
認為 $ b $ 是要表示的位數 $ n $ 以二進制格式，那麼我可以直接替換為 $ \sqrt{n} $ ，這樣我就可以得到 $ 2^{\frac{b}{2}} $ .
還是應該計算為 $ (\sqrt{n}-1)* $ 模運算所需的時間 $ + $ 劃分的時間？
如何計算時間複雜度 $ b $ ?
以位為單位計算模數和除法需要多少時間？如果我們替換這些值，最後我們應該得到 $ 2^{\frac{b}{2}} $ ?
您的假設“（假設找到餘數和除法發生在恆定時間內）”在這裡沒有得到滿足。我們正在處理大數，除法複雜度是某個函式 M(b)，其中 M 是乘法算法的複雜度，例如，Schönhage-Strassen 的複雜度為 O(b log b log log b)。教科書分部的順序為 b²。
請注意，出於加密目的，n 確實很大；甚至 n 中的多項式時間算法（b 中的指數）在這裡也不可行。
編輯：關於復雜性計算的說明：只有總和中的前導項是相關的，低階項總是可以忽略不計。當您的複雜性已經是指數級時，您可以忽略多項式因素。因此，只是提到了除法的複雜性，以表明您的假設首先不成立，在論證過程中它可以忽略不計。
注意：這一切都假設經典電腦作為計算模型。使用量子電腦，您可以使用 Shor 算法在多項式時間內分解一個整數。目前發布的量子電腦有 14 個 QBit，可以分解整數 15（十五）。對未發表的量子電腦應用摩爾定律和一些餘地，您就可以估計這種密碼學何時會被破解。