2^n mod（m）算法

在課堂上，我們給出了2^n mod（m）的算法。2^n mod（m）算法

to find 2^n mod(m){ 
     if n=0 {return 1;} 

     r=2^(n-1)mod(m); 
     if 2r < m {return 2r;} 
     if 2r > =m {return 2r-m;} 
    }

我們被告知運行時是O（n *尺寸（μm）），其中的M尺寸爲以m比特的數量。

我瞭解n部分，但我不能解釋大小（m），除非是因爲涉及到減法。任何人都可以對此有所瞭解嗎？

在此先感謝。

來源

2011-10-12 Chet

*你在做什麼n次？你正在做一個指數，一個模數，一個比較或者一個減法。所以... –

我相信'r = 2 ^（n-1）mod（m）;'是遞歸調用同一個函數 – Slartibartfast

它是O（n）好的。 O（n）== O（n * some_k）。儘管'sizeof（m）'可以適用於任意大小的'm'，只有固定大小的算術硬件。 – ruslik

n部分很明確，因爲您已經瞭解了自己。 size(m)（這是m中的位數，基本上是log(m)）是因爲mod。即使你的CPU在一條指令中爲你做了這個，它需要log(m)（比方說32位）次。如果m非常大，如加密密鑰常見的那樣，這可能變得相當可觀。

爲什麼數字在m？記得除法：

abcdefghijk | xyz 
      |----- 
alm   | nrvd... 
opq 
    stu 
    wabc 
    .......

你做減號的次數最多是被除數中的位數。

來源

2011-10-13 00:43:01 Shahbaz

我相信這是用在密碼學（所謂的不可逆函數）。

如果我們需要遞歸計算(2**n) mod m，這將是最明顯的方法。由於遞歸的深度是n，因此複雜度很明顯。但是，如果我們想要支持任意大小的m（512位密鑰在密碼學中是可能的，並且比任何算術寄存器大得多），我們也應該考慮到（在大多數情況下，我們不需要使用任意的精確算術，所以這個術語通常是1）。

編輯 @Mysticial：該功能不明確地調用硬件mod操作，它是所有移動和減法。移位始終爲O(1)，同時加法/減法爲O(ceil(m/sizeof_ALU_precision))

來源

2011-10-13 00:34:22 ruslik

這裏的問題是，大小爲「m」的算術運算時間不是線性的。對於這些小尺寸，它是'O（m^2）'，對於非常大的'm'大致爲'O（m * log（m））'。 – Mysticial

是的，我們正在討論RSA。我沒有建立聯繫，這就是我們考慮m的原因。我想大小（m）項有一些係數，因爲在記錄O（n * size（m））時不包括比較，減法等。謝謝！ – Chet

我在談論高等數學。對512位整數的算術被認爲是bignum。所以在這個意義上，加/減是'O（m）'而不是'O（1）'，其中'm'是你的密鑰的長度。 – Mysticial

2^n mod（m）算法

回答

相關問題