Как 32-разрядная операционная система выполняет 2 ^ 56 по модулю 7?

Question

Как система выполняет 2 ^ 56 по модулю 7, если это, например, 32-битная операционная система в криптографии?

А как он хранится в памяти?

Answer 1

По арифметике произвольной точности

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

Вы можете дополнительно расширить концепцию для создания интегрального типа данных произвольной точности, который ограничен только объемом ограниченной памяти. По сути, у вас есть массив слов, и вы храните свои N -битные числа в битах слов этого массива.

Тот факт, что это 32-разрядная операционная система, сама по себе не ограничивает числовые вычисления, которые вы можете выполнять. Например, Java long является 64-битным целочисленным типом, независимо от того, где он работает. Для произвольной точности java.math.BigInteger повышает анте и обеспечивает абстракцию «бесконечного размера слова». И да, эта «функция» доступна даже в 32-битных операционных системах (потому что это никогда не было ограничивающим фактором с самого начала).

Смотри также

• Википедия / Произвольно-точная арифметика
• Библиотека GNU MP BigNum

---

По математике на кольце целых чисел

Нахождение модульного мультипликативного обратного или модульного возведения в степень является распространенной математической / алгоритмической задачей в области криптографии.

Здесь вы можете использовать одну личность:

A * B (mod M) == (A (mod M)) * (B (mod M)) (mod M)

Чтобы найти x = 2 ⁵⁶ (мод 7), вы НЕ должны сначала вычислить и сохранить 2 ⁵⁶ . Если у вас y = 2 ⁵⁵ (мод 7) - число от 0,6 - вы можете найти x = y * 2 (мод 7).

Но как вы находите у = 2 ⁵⁵ (мод 7)? Ну, один наивный способ - применить процесс линейно и сначала попытаться найти z = 2 ⁵⁴ (мод 7) и так далее. Это линейное возведение в степень, но вы можете добиться большего успеха, выполнив, например, возведение в степень в квадрате .

То есть, если вы скажете 2 ⁸ , вы можете поставить его в квадрат, чтобы сразу получить 2 ¹⁶ . Вы можете затем возвести это в квадрат, чтобы сразу получить 2 ³² .

---

Резюме

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

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

Некоторые языки высокого уровня даже имеют встроенную арифметику произвольной точности. Например, Python обеспечивает произвольную точность int и long на уровне языка.

Answer 2

2**56 == 2**(28+28) == 2**28 * 2**28 == (2**28)**2
2**28 == 2**(14+14) == 2**14 * 2**14 == (2**14)**2
2**14 == 2**(7+7) == 2**7 * 2**7 == (2**7)**2
2**7 == 2**(3+3 +1) == 2**3 * 2**3 * 2 == (2**3)**2 * 2
2**3 == 2**(1+1 +1) == 2**1 * 2**1 * 2 == (2**1)**2 * 2

2**56 == (2**28)**2 == ((2**14)**2)**2 == (((2**7)**2)**2)**2
== (((2*(2**3)**2)**2)**2)**2 == (((2*(2*(2**1)**2)**2)**2)**2)**2

2**56 %7
== (((2*(2*(2**1)**2)**2)**2)**2)**2 %7
== (((2*(2*(2**1 %7)**2 %7)**2 %7)**2 %7)**2 %7)**2 %7
== (((2*(2*(2)**2 %7)**2 %7)**2 %7)**2 %7)**2 %7
== (((2*(2*4 %7)**2 %7)**2 %7)**2 %7)**2 %7
== (((2*(1)**2 %7)**2 %7)**2 %7)**2 %7
== (((2 %7)**2 %7)**2 %7)**2 %7
== ((2**2 %7)**2 %7)**2 %7
== ((4)**2 %7)**2 %7
== (16 %7)**2 %7
== (2)**2 %7
== 4 %7
== 4

so (2**56) % 7 == 4

Вы заметите, что мы никогда не имели дело с какими-либо большими числами (на самом деле наибольшее число было 56).

Кроме того:

2**224 %7 == (2**56)**4 %7 == (4*4*4*4) %7 ==
((16%7) * (16%7)) %7 == (2*2) %7 == 4 %7 == 4

И, таким образом, также 2**896 %7 = 4 и т. Д. (Начиная с 896 = 4 * 224, где 224 = 4 * 56).

Answer 3

Как правило, если вы знаете, что ваши цифры станут очень большими, вы будете использовать библиотеку, такую ​​как GMP (Gnu Multi-Precision), для обработки математики.Он делает то, что делал бы на бумаге, если бы у тебя на руках было 2 ^ 32 пальца.

Answer 4

Модульные алгоритмы возведения в степень используются для этого вида операции. Эта статья в Википедии рассказывает, как это делается: http://en.wikipedia.org/wiki/Modular_exponentiation

Answer 5

также добавьте к другим ответам, которые дают хорошее объяснение 32 int и модульного мультипликативного обратного, а что нет

Я объясню, что такое 32-битный процессор

32 bit Процессоры, как их знает большинство людей, связаны с размером шины адреса. это количество адресов, доступных, например, на процессоре x86 (ваш обычный настольный процессор [AMD, Intel]) это позволяет 2^32 байтов адресного пространства или 4GB, как правило, разделяется между адресуемым оборудованием и ОЗУ, поэтому причина для фактической реализации процессора 64 bit была в том, что мы приблизились к 4GB ОЗУ предел

Как примечание стороны, это ранее случалось, когда процессоры были 16 бит

Answer 6

Я думаю, что ваша терминология немного запутана.

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

Таким образом, вполне вероятно, что машина с 32-разрядной архитектурой(и работает с 32-битной операционной системой) будет использовать 64-битную арифметику и сохранять результат в памяти как 64-битный long или long long, используя 2 последовательных 32-битных слова.

Answer 7

Используется, что (a * b) mod c = ((a mod c) * (b mod c)) mod c.Это означает, что вы можете

1. начать с x = 1
2. Do x = (x * 2)% 7 56 раз

Answer 8

Какая система? Какая архитектура?

Вообще говоря, в 32-битной архитектуре вы получаете результаты переполнения. Некоторые языки имеют встроенные произвольно большие числовые типы, которые могут обрабатывать эти вычисления. Примерами этого являются BigDecimal в Java и встроенные long int s в Python.