在不知道其中一个因数的情况下求乘积的位数

Question

假设我有一些超过 1000 位的奇数 N，我想将它乘以某个数字 H，以便它们的乘积得到一个所有位都为 1 的数字。例如：

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

考虑到这个条件，在不知道H的情况下如何求NH的长度？

Answer 1

首先，假设我们有某种快速分解算法。 最快的整数分解算法是什么？讨论了一些。

在Python中，我们可以从primefac得到一个不错的实现。

接下来。正如您所指出的，我们正在寻找第一个

k

，使得

2**k

是

1 mod N

。欧拉定理表明，这将是Euler 的 totient 函数 的除数。因此，让我们首先能够以完全因式分解的形式计算 totient 函数。

from primefac import primefac

def factored_totient (n):
    answer = []
    last_p = 0
    for p in primefac(n):
        if p == last_p:
            answer.append(p)
        else:
            last_p = p
            for q in primefac(p-1):
                answer.append(q)
    return sorted(answer)

接下来，这是一个辅助函数，我将用它来计算

2^k mod n

，然后计算算法。

def n_pow_m_mod_k (n, m, k):
    answer = 1
    cur_pow = n
    while 0 < m:
        if 1 == m % 2:
            answer = (answer * cur_pow) % k
        cur_pow = (cur_pow * cur_pow) % k
        m = m // 2
    return answer

def bits_puzzle (n):
    if 0 == n % 2:
        return None
    ft = factored_totient(n)
    answer = 1
    for p in ft:
        answer *= p
    last_failed_p = 0
    for p in ft:
        if p != last_failed_p:
            factor = answer // p
            if 1 == n_pow_m_mod_k(2, factor, n):
                answer = factor
            else:
                last_failed_p = p
    return answer

你可以用一些小值来测试它。

for n in (0b10101, 0b10, 0b1101):
    print((n, bin(n), bits_puzzle(n)))

我还尝试在您想要的尺寸的数字上进行测试。不幸的是，对随机 1000 位数字进行因式分解非常困难。在一分钟左右的典型运行中，它有一堆因子加起来大约为 100 位，现在却被困在试图对一个 900 位数字进行因式分解，其中因子不小。正如“整数分解”所指出的，这属于密码学中可用的分解问题范围。假设最后一个数字是半素数，则使用专门的分布式算法可能需要数万到数十万年的计算时间。

Answer 2

n*h

这太少了，所以这不是一个好方法。这是我的 C++ 实现：

int compute0(uint<_max_words> &n)   // naive bruteforce division
    {
    int nh_bits;
    uint<_max_words> h,nh;
    for (nh_bits=1,nh=1;nh<n;nh<<=1,nh|=1,nh_bits++);
    for (;;nh<<=1,nh|=1,nh_bits++)
        {
        h=nh%n;
        if (!h){ h=nh/n; break; }
        if (nh.a[0]==0xFFFFFFFF){ h=0; nh=0; break; }
        }
    return nh_bits;
    }

其中 

uint<_max_words>

是我的大无符号 int 类（您可以使用任何 BigInt 库）...

经过一番思考，我想到要做一个“二进制长除法”

nh/n

，其中对于非零余数，我们只需向

nh

添加一位，然后继续重复使用已计算的值进行除法，直到出现零余数...这让事情变得简单

很多

，但代价是我们不再知道h（好吧，它也可以以相对较小的成本计算），但这没关系，因为我们无论如何都不想要它......

这里是简单的 C++ 实现：

int compute1(uint<_max_words> &n) // continuous binary long division
    {
    int nh_bits;
    uint<_max_words> nh;
    for (nh_bits=1,nh=1;nh<n;nh<<=1,nh|=1,nh_bits++);
    for (;;nh<<=1,nh|=1,nh_bits++)
        {
        if (nh>=n) nh-=n;
        if (nh.iszero()) break;
        }
    return nh_bits;
    }

速度差异为：

n="13453h"
bitwidth used for computation: 1700

[2061.415 ms] n: 17 , nh: 1688 // brute force
[   2.067 ms] n: 17 , nh: 1688 // binary long division

这是另一个结果（只是二进制长除法，因此位宽较小）：

bitwidth used for computation: 64

n="12345654321h";   
[1327.825 ms] n: 41 , nh: 8947848
        

因此，如果 

nh

结果足够小，那么这种方法很快，但是如果不是或没有解决方案，那么这些东西就会挂起......除非添加检测或最大限制。请注意，该算法只需要使用可以容纳

n

的算术，这使得速度更快......