Как компьютеры могут вычислять экспоненциальную математику без ошибок переполнения?

Изучая некоторые методы шифрования / дешифрования RSA, я нашел эту статью: Пример алгоритма RSA

Требуется это для расшифровки этого сообщения

Общий результат для 64-битной / 32-битной машины настолько велик, что я не верю, что она может хранить такое большое значение в одном регистре. Как компьютер делает это без переполнения?

Этот вопрос был Супер Вопросом Пользователя Недели .
Прочитайте запись в блоге для получения более подробной информации или внесите свой вклад в блог самостоятельно

Поскольку операция целочисленного модуля является кольцевым гомоморфизмом ( Википедия ) из ℤ -> ℤ / nℤ,

(X * Y) mod N = (X mod N) * (Y mod N) mod N

Вы можете убедиться в этом сами с помощью небольшой алгебры. (Обратите внимание, что финал modсправа появляется из-за определения умножения в модульном кольце.)

Компьютеры используют этот трюк для вычисления экспонент в модульных кольцах без необходимости вычисления большого количества цифр.

               / 1 I = 0,
               |
(X ^ I) mod N = <(X * (X ^ (I-1) mod N)) mod NI нечетно,
               |
               \ (X ^ (I / 2) mod N) ^ 2 mod NI даже & I / = 0.

В алгоритмической форме

-- compute X^I mod N
function expmod(X, I, N)
    if I is zero
        return 1
    elif I is odd
        return (expmod(X, I-1, N) * X) mod N
    else
        Y <- expmod(X, I/2, N)
        return (Y*Y) mod N
    end if
end function

Вы можете использовать это для вычисления (855^2753) mod 3233только с 16-битными регистрами, если хотите.

Однако значения X и N в RSA намного больше, слишком велики, чтобы поместиться в регистр. Модуль обычно имеет длину 1024-4096 бит! Таким образом, вы можете заставить компьютер выполнять умножение «длинным» способом, так же, как мы умножаем вручную. Только вместо цифр 0-9 компьютер будет использовать «слова» 0-2 ¹⁶ -1 или что-то в этом роде. (Использование только 16 бит означает, что мы можем умножить два 16-битных числа и получить полный 32-битный результат, не прибегая к языку ассемблера. На языке ассемблера обычно очень легко получить полный 64-битный результат, или для 64-битного компьютера , полный 128-битный результат.)

-- Multiply two bigints by each other
function mul(uint16 X[N], uint16 Y[N]):
    Z <- new array uint16[N*2]
    for I in 1..N
        -- C is the "carry"
        C <- 0
        -- Add Y[1..N] * X[I] to Z
        for J in 1..N
            T <- X[I] * Y[J] + C + Z[I + J - 1]
            Z[I + J - 1] <- T & 0xffff
            C <- T >> 16
        end
        -- Keep adding the "carry"
        for J in (I+N)..(N*2)
            T <- C + Z[J]
            Z[J] <- T & 0xffff
            C <- T >> 16
        end
    end
    return Z
end
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have

Это умножит X на Y на количество времени, примерно равное количеству слов в X, умноженному на количество слов в Y. Это называется O (N ² ) время. Если вы посмотрите на алгоритм выше и выделите его отдельно, то это то же самое «длинное умножение», которому они учат в школе. У вас нет запомненных временных таблиц до 10 цифр, но вы все равно можете умножить 1 926 348 x 8 192 004, если сядете и решите это.

Длинное умножение:

    1,234
  x 5,678
---------
    9,872
   86,38
  740,4
6,170
---------
7,006,652

На самом деле есть несколько более быстрых алгоритмов умножения ( Википедия ), таких как быстрый метод Фурье Штрассена, и некоторые более простые методы, которые делают дополнительное сложение и вычитание, но меньше умножения, и, следовательно, в итоге быстрее в целом. Числовые библиотеки, такие как GMP, способны выбирать разные алгоритмы в зависимости от того, насколько большие числа: преобразование Фурье является самым быстрым для самых больших чисел, меньшие числа используют более простые алгоритмы.

Ответ прост: они не могут, не самостоятельно. Действительно, если вы берете понятие x-битной машины, то существует ограниченное число чисел, которые могут быть представлены ограниченным числом битов, точно так же, как существует ограниченное число чисел, которые могут быть представлены 2 цифрами в десятичная система.

Тем не менее, компьютерное представление очень больших чисел является крупным компонентом области криптографии. Существует много способов представления очень больших чисел в компьютере, каждый из которых отличается от следующего.

Каждый из этих методов имеет свои преимущества и недостатки, и хотя я не могу / не могу перечислить здесь все методы, я представлю очень простой.

Предположим, что целое число может содержать только значения от 0 до 99. Как можно представить число 100? Поначалу это может показаться невозможным, но это потому, что мы рассматриваем только одну переменную. Если бы я имел целое число , называемое unitsи один называется hundreds, я мог бы легко представить 100: hundreds = 1; units = 0;. Я мог бы легко представить большее число, как 9223: hundreds = 92; units = 23.

Хотя это простой метод, можно утверждать, что он очень неэффективен. Как и большинство алгоритмов, которые раздвигают границы возможностей компьютера, это, как правило, перетягивание каната между властью (представляют большие числа) и эффективностью (быстрый поиск / хранение). Как я уже говорил ранее, существует много способов представления больших чисел в компьютерах; Просто найдите метод и экспериментируйте с ним!

Я надеюсь, что это ответило на ваш вопрос!

Дальнейшее чтение:Эта статья и эта могут пригодиться для получения дополнительной информации.

Способ, которым это может быть сделано (есть намного более быстрые способы, включающие повторное возведение в квадрат и т.п.), является умножением, и после каждого умножения берут модуль. Пока квадрат модуля меньше 2 ^ 32 (или 2 ^ 64), переполнение никогда не произойдет.

Точно так же, как вы можете.

Я собираюсь догадаться, что вы не знаете, что такое 342 * 189. Но вы знаете следующие факты:

9 * 2 = 18
9 * 4 = 36
9 * 3 = 27
8 * 2 = 16
8 * 4 = 32
8 * 3 = 24
1 * 2 = 2
1 * 4 = 4
1 * 3 = 3

18 + 360 + 2700 + 160 + 3200 + 24000 + 200 + 4000 + 30000 = 64638

Зная эти простые факты и изучив технику манипулирования ими, вы можете делать арифметику, которую иначе не могли бы сделать.

Точно так же компьютер, который не может обрабатывать более 64 бит математики за раз, может легко разбить большие задачи на более мелкие части, выполнить эти меньшие части и соединить их вместе, чтобы сформировать ответ на более крупные, ранее неопровержимая проблема.

Что касается сложения и вычитания, многие процессоры имеют «бит переноса», который устанавливается, если арифметическая операция была переполнена. Таким образом, если результат потребует 8 байтов для хранения, а процессор 32-битный (что эквивалентно 4 8-битным байтам), он может выполнить две операции сложения, сначала над «младшим словом», а затем над «старшим словом» с битом для переноски, обеспечивающим перелив. Сначала необходимо очистить бит переноса. Это одна из причин, по которой старшие процессоры повышают производительность, потому что это не нужно делать так сильно.

Конечно, это из моего ограниченного опыта ассемблера с 8-битными процессорами. Я не знаю, как бит переноса работает с современными процессорами с умножением и делением команд. Процессоры не-Intel RISC также могут вести себя по-разному.

Я не очень разбираюсь в математике с плавающей запятой, но в основном байты представляют фиксированное количество мест, но не конкретные места. Вот почему это называется «плавающей» точкой. Так, например, число 34459234 будет занимать примерно то же пространство памяти, что и 3.4459234, или 3.4459234E + 20 (это 3.4459234 x 10 ^ 20).