Изучая некоторые методы шифрования / дешифрования 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 N I odd,
|
\ (X^(I/2) mod N)^2 mod N I even & 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 16 -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 2) время. Если вы посмотрите на алгоритм выше и выберете его отдельно, это то же самое "длинное умножение", которому они учат в школе. Таблицы времени не запоминаются до 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 .
Хотя это простой метод, можно утверждать, что он очень неэффективен. Как и большинство алгоритмов, которые раздвигают границы возможностей компьютера, это, как правило, перетягивание каната между мощью (представляют большие числа) и эффективностью (быстрый поиск / хранение). Как я уже говорил ранее, существует много способов представления больших чисел в компьютерах; просто найдите метод и экспериментируйте с ним!
Я надеюсь, что это ответило на ваш вопрос!
Дальнейшее чтение: эта и эта статья могут пригодиться для получения дополнительной информации.
Точно так же, как вы можете.
Я догадываюсь, что вы не знаете, что такое 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 бит математики одновременно, может легко разбить большие задачи на более мелкие части, выполнить эти меньшие части и соединить их вместе, чтобы сформировать ответ на более крупные, ранее неопровержимая проблема.
Способ, которым это может быть сделано (есть намного более быстрые способы, включающие повторное возведение в квадрат и т.п.), является умножением, и после каждого умножения берут модуль. Пока квадрат модуля меньше 2 ^ 32 (или 2 ^ 64), переполнение никогда не произойдет.
Что касается сложения и вычитания, многие процессоры имеют "бит переноса", который устанавливается, если арифметическая операция была переполнена. Таким образом, если результат потребует 8 байтов для хранения, а процессор 32-битный (что эквивалентно 4 8-битным байтам), он может выполнить две операции сложения, сначала над "младшим словом", а затем над "старшим словом" с битом переноса, заботящимся о переполнении. Сначала необходимо очистить бит переноса. Это одна из причин, по которой старшие процессоры повышают производительность, потому что это не нужно делать так сильно.
Конечно, это из моего ограниченного опыта ассемблера с 8-битными процессорами. Я не знаю, как бит переноса работает с современными процессорами с инструкциями умножения и деления. Процессоры не-Intel RISC также могут вести себя по-разному.
Я не очень разбираюсь в математике с плавающей точкой, но в основном байты представляют собой фиксированное количество мест, но не конкретные места. Вот почему это называется "плавающей" точкой. Так, например, число 34459234 будет занимать примерно то же пространство памяти, что и 3.4459234, или 3.4459234E+20 (это 3.4459234 x 10 ^ 20).