位移位得到128位produ

Question

首先，我知道Python不使用位运算符就可以很好地处理这一问题，第三行代码应该说明这一点。我最终尝试用C语言来完成这个任务——在一个不支持uint t的体系结构上实现RSA（因此代码中有p、q和n个变量）；我只不过对Python比较在行，并试图用它来理解。编辑：没有上述支持，存储total0（128位）是它自己的问题，但是这个概念证明应该允许我解决其余的问题。在

我发现this archived magazine正在讨论如何在摩托罗拉68000 CPU上使用64位产品来实现这一点，并尝试用Python实现，但是增加了一倍。我把上面的32位取对了，但是剩下的96位是不正确的（好吧，最后16位也是正确的，但是它们根本没有移位，所以这并不奇怪）。在

为了防止我在计算位时出现数学错误，我尝试了一个暴力for/for/for循环，在范围（0,81）内运行total1/total2/total3。不匹配。在

p = 10259632476918722477
q = 17757547285565901767
n = p*q

big_mask =    0xffffffff
small_mask =      0xffff

p_lo = p & big_mask
p_hi = p >> 32
q_lo = q & big_mask
q_hi = q >> 32

p_lo_q_lo = p_lo * q_lo
p_lo_q_hi = p_lo * q_hi
p_hi_q_lo = p_hi * q_lo
p_hi_q_hi = p_hi * q_hi

p_lo_q_lo_UPPER = p_lo_q_lo >> 16
p_lo_q_lo_LOWER = p_lo_q_lo & small_mask
p_lo_q_hi_UPPER = p_lo_q_hi >> 16
p_lo_q_hi_LOWER = p_lo_q_hi & small_mask
p_hi_q_lo_UPPER = p_hi_q_lo >> 16
p_hi_q_lo_LOWER = p_hi_q_lo & small_mask
p_hi_q_hi_UPPER = p_hi_q_hi >> 16
p_hi_q_hi_LOWER = p_hi_q_hi & small_mask

# Original, incorrect implementation
#total0 = p_hi_q_hi_UPPER
#total1 = (p_lo_q_hi_UPPER + p_hi_q_lo_UPPER + p_hi_q_hi_LOWER)
#total2 = (p_lo_q_lo_UPPER + p_lo_q_hi_LOWER + p_hi_q_lo_LOWER)
#total3 = p_lo_q_lo_LOWER
#total = total0 << 80 | total1 << 33 | total2 << 14 | total3 << 0

# Corrected implementation
total0 = p_hi_q_hi_UPPER << 80
total1 = p_hi_q_hi_LOWER << 64
total2 = (p_lo_q_hi_UPPER + p_hi_q_lo_UPPER) << 48
total3 = (p_lo_q_hi_LOWER + p_hi_q_lo_LOWER) << 32
total4 = p_lo_q_lo_UPPER << 16
total5 = p_lo_q_lo_LOWER

total = total0 + total1 + total2 + total3 + total4 + total5

print("\n")
if (n==total):
  print("Match!")
else:
  print("No match.")
print("\n")
print("Actual:   " + str(n))
print("Computed: " + str(total))

print("\n")
# Strip '0b' off of the binary string so the list groupings display logically
hex_n = hex(n)[2:]
hex_total = hex(total)[2:]
print("Actual:   ", end="")
print("\t" + str([hex_n[i:i+4] for i in range(0, len(hex_n), 4)]))
print("Computed: ", end="")
print("\t" + str([hex_total[i:i+4] for i in range(0, len(hex_total), 4)]))

我的想法是将total0移到80位，这是一个48位的数字，所以它应该有80 0填充到右边。total1是47位，所以左移33位（80-47）。总计2是44位，所以左移14位（47-33）。最后，让total3保持原样，因为它是LSDW。在

Answer 1

我认为在末尾创建total值时，您的移位量是关闭的。以下是各种中间值的移位量：

p_lo         0
p_hi        32
q_lo         0
q_hi        32

p_lo_q_lo    0
p_lo_q_hi   32
p_hi_q_lo   32
p_hi_q_hi   64

p_lo_q_lo_UPPER    16
p_lo_q_lo_LOWER     0
p_lo_q_hi_UPPER    48
p_lo_q_hi_LOWER    32
p_hi_q_lo_UPPER    48
p_hi_q_lo_LOWER    32
p_hi_q_hi_UPPER    80
p_hi_q_hi_LOWER    64

最后一组排序：

^{pr2}$

所以有6种不同的最终移位量，而不是4种。通过在末尾创建6个total变量，并将它们与上面所示的移位量相加，应该很容易修复。在