Как WolframAlpha может быстро выражать цифры?

Мне было интересно, как алгоритм RSA имеет дело с такими большими числами и попробовал один пример в WolframAlpha. Как они могут справиться с такими безумными цифрами?

EDIT: просто чтобы сделать его более причудливым, еще один пример

Ответ 1

Существует простой алгоритм под названием возведения в степень возведения в квадрат, который может быть использован для вычисления a ^b mod c очень эффективно. Это основано на наблюдении, что

a ^2k mod c = (a ^k) ² mod c

a ^{2k + 1} mod c = a & middot; (a ^k) ² mod c

Учитывая это, вы можете вычислить mod c ^b с этим рекурсивным подходом:

function raiseModPower(a, b, c):
    if b == 0 return 1
    let d = raiseModPower(a, floor(b/2), c)
    if b mod 2 = 1:
        return d * d * a mod c
    else
        return d * d mod c

Это делает только O (log b) умножения, каждый из которых не может иметь больше цифр в них, чем O (log c), поэтому он очень быстро. Это то, как реализации RSA также подпитывают силы. Вы можете переписать это, чтобы быть итеративным, если хотите, хотя я считаю, что рекурсивное представление действительно чистое.

Как только у вас есть этот алгоритм, вы можете использовать стандартные методы для умножения чисел произвольной точности для выполнения вычислений. Так как требуется только O (log b) итераций умножения (в отличие, например, от итераций), это безумно быстро. Вы никогда не заканчиваете вычисление ^b а затем модифицировали его на c, что также уменьшает количество разрядов и делает его еще быстрее.

Надеюсь, это поможет!