未知乘数H时，如何求奇数N与H的全1比特乘积的比特长度？

我有一个超过1000比特的奇数N，想要找到某个数H，使得N与H的乘积是一个所有比特均为1的二进制数。例如：

N = 0b1101
  H = 0b100111011
N*H = 0b111111111111

请问，在不知道H的情况下，如何求出N*H的比特长度？

首先，所有比特全为1的二进制数可以表示为 ( R_k = 2^k - 1 )，其中k就是该数的比特长度（比如12个1的数对应 ( 2^{12} - 1 )）。你的问题等价于找到最小的正整数k，使得 ( 2^k \equiv 1 \pmod{N} )——因为 ( N \times H = 2^k - 1 ) 意味着 ( 2^k - 1 ) 能被N整除，也就是 ( 2^k \equiv 1 \pmod{N} )。

这个k叫做2模N的乘法阶，计算它的具体步骤如下：

• 由于N是奇数，2和N互质，根据欧拉定理，k一定是欧拉函数φ(N)的约数。
• 第一步：对N进行质因数分解，得到 ( N = p_1^{e_1} p_2^{e_2} ... p_m^{e_m} )，然后计算欧拉函数 ( φ(N) = N \times \prod_{i=1}^m (1 - \frac{1}{p_i}) )。
• 第二步：找出φ(N)的所有正约数，并按从小到大的顺序排列。
• 第三步：对每个约数d，用快速幂算法高效计算 ( 2^d \mod N )，第一个满足结果等于1的d就是我们要找的k，也就是N*H的比特长度。

举个例子验证：你给出的N=0b1101（十进制13），φ(13)=12，它的正约数有1、2、3、4、6、12。依次验证：

• ( 2^1 \mod 13 = 2 ≠ 1 )
• ( 2^2 \mod 13 = 4 ≠ 1 )
• ( 2^3 \mod 13 = 8 ≠ 1 )
• ( 2^4 \mod 13 = 16 ≡ 3 ≠ 1 )
• ( 2^6 \mod 13 = 64 ≡ 12 ≠ 1 )
• ( 2^{12} \mod 13 = 1 )，所以k=12，对应N*H是12个1的二进制数，和例子完全匹配。

内容的提问来源于stack exchange，提问作者user1240174