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）算法

回答

相关问题