Как найти 2 в степени безумно большого числа по модулю 10 ^ 9

Question

У меня слишком большое число (1500+) цифр, и мне нужно найти 2 ** это число по модулю 1_000_000_000, поэтому я написал этот питон:

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

Это возвращает правильное значение для меньших значений,но занимает слишком много времени для больших значений.

Если число по модулю 10, вы получаете этот шаблон, который можно использовать.

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 

Я надеюсь, что аналогичный шаблон может быть использованответить на исходную задачу.

Answer 1

Ваш код делает около 10 ** 1500 итераций, что действительно невероятно долго.Полезной общей техникой является возведение в степень путем возведения в квадрат , которое даст вам результат примерно за 4500 итераций.

Если вы хотите следовать по пути ответа @ Prune, вы должны пройти полинии Теоремы Ферма, в частности обобщение Эйлера .phi(1_000_000_000) легко вычислить, потому что 10 ** 9 = (2 ** 9) * (5 ** 9) - произведение двух степеней простых чисел.

Answer 2

Вы уже знаете, что последовательность повторится.Вы нашли цикл 4 для мода 10;теперь просто найдите его на миллиард:

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 пунктов.Чтобы найти свою ценность для данной силы:

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