如何找到2乘以10 ^ 9为模的疯狂大数的幂 [英] How to find 2 to the power of an insanely big number modulo 10^9

问题描述

我有一个太大的数字(1500+)，我需要找到2 **该数字以1_000_000_000为模，所以我写了这个python:

I have an excessively big number (1500+) digits and I need to find 2 ** that number modulo 1_000_000_000 so I wrote this python:

n = 1
return_value = 2
while n < To_the_power_of:
    return_value *= 2
    return_value = return_value % 1_000_000_000 
    n += 1

对于较小的值，它返回正确的值，但是对于较大的值，它花费的时间太长.

This returns the correct value for smaller values, but takes too long for bigger values.

如果数字是10模，那么您会得到可以使用的模式.

If the number is modulo 10 then you get this pattern which could be used.

2 ** 1 modulo 10 = 2
2 ** 2 modulo 10 = 4
2 ** 3 modulo 10 = 8
2 ** 4 modulo 10 = 6
2 ** 5 modulo 10 = 2
2 ** 6 modulo 10 = 4 
2 ** 7 modulo 10 = 8 
2 ** 8 modulo 10 = 6 

我希望可以使用类似的模式来回答原始问题.

I'm hoping that a similar pattern could be used to answer the original problem.

推荐答案

您已经知道该序列将重复.您发现mod 10的周期为4；现在，只需找到十亿美元即可:

You already know that the sequence will repeat. You found the cycle of 4 for mod 10; now, just find it for a billion:

mod_billion = set()
pow_2 = 2
billion = 10**9

while pow_2 not in mod_billion:
    mod_billion.add(pow_2)
    pow_2 *= 2
    if pow_2 > billion:
        pow_2 -= billion

print (pow_2, len(mod_billion))

三秒钟后，我们得到:

512 1562508

因此，此序列每1562508个项目重复一次.为了找到给定能力的价值，

Thus, this sequence repeats every 1562508 items. To find your value for your given power:

cycle = 1562508
small_power = big_power % cycle
result = (2 ** small_power) % billion

这篇关于如何找到2乘以10 ^ 9为模的疯狂大数的幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！