Как 32-битная операционная система выполняет 2^56 по модулю 7?
Как система выполняет 2^56 по модулю 7, если это 32-битная операционная система в криптографии, например?
И как он хранится в памяти?
7 ответов
Об арифметике произвольной точности
32-битный операционная система не ограничивает вас в использовании настраиваемых типов, превышающих этот размер. Ваше приложение может взять два 32-битных слова и рассматривать их как одно 64-битное число. В большинстве языков программирования для упрощения есть даже целочисленный тип «двойное слово».
Вы можете дополнительно расширить концепцию, чтобы создать интегральный тип данных произвольной точности, который ограничен только объемом ограниченной памяти. По сути, у вас есть массив слов, и вы храните свои N -битные числа в битах слов этого массива.
Тот факт, что это 32-разрядная операционная система, сам по себе не ограничивает числовые вычисления, которые вы можете выполнять. Например, Java long - это 64-битный целочисленный тип, независимо от того, где он запущен. Для произвольной точности java.math.BigInteger увеличивает ставку и обеспечивает абстракцию «бесконечного размера слова».И да, эта «функция» доступна даже в 32-битных операционных системах (потому что это никогда не было ограничивающим фактором).
См. Также
По математике в кольце целых чисел
Нахождение модульного мультипликативного обратного или модульного возведения в степень - это обычная математическая / алгоритмическая задача в области криптографии.
Один идентификатор, который вы можете использовать здесь, следующий:
A * B (mod M) == (A (mod M)) * (B (mod M)) (mod M)
Чтобы найти x = 2 56 (mod 7), вы делаете НЕ необходимо сначала вычислить и сохранить 2 56 . Если у вас есть y = 2 55 (mod 7) - число от 0 до 6 - вы можете найти x = y * 2 (mod 7).
Но как найти y = 2 55 (mod 7)? Что ж, один наивный способ - применить этот процесс линейно и сначала попытаться найти z = 2 54 (mod 7) и так далее. Это линейное возведение в степень, но вы можете добиться большего, выполнив, например, возведение в степень возведением в квадрат .
То есть, если вы скажете 2 8 , вы можете возвести его в квадрат, чтобы сразу получить 2 16 . Затем вы можете возвести это в квадрат, чтобы сразу получить 2 32 .
Заключение
Существует множество сложных математических алгоритмов, применимых к криптографии, и независимо от того, реализован ли он в программе, работающей в 32-битной или 64-битной операционной системе, напрямую не имеет значения.Пока доступно достаточно памяти, компьютер более чем способен выполнять арифметические операции произвольной точности.
Именно потому, что арифметика произвольной точности является полезной абстракцией, доступно множество высокопроизводительных библиотек, так что вы можете построить свое приложение на основе уже существующей инфраструктуры, вместо того, чтобы строить с нуля.
Некоторые языки высокого уровня даже имеют встроенную арифметику произвольной точности. Python, например, обеспечивает произвольную точность int и long на уровне языка.
Думаю, ваша терминология немного запуталась.
32-битная операционная система или 32-битная архитектура - это та, в которой машинные адреса ограничены 32 битами. В 32-битной архитектуре нет ничего необычного в том, что арифметические инструкции работают с 64-битными целыми числами и / или 64-битными числами с плавающей запятой.
Таким образом, весьма вероятно, что машина с 32-битной архитектурой (и работающая под управлением 32-битной операционной системы) будет использовать 64-битную арифметику и сохранять результат в памяти как 64-битный длинный или long long с использованием 2 последовательных 32-битных слов.
Для этого типа операций используются алгоритмы модульного возведения в степень. В этой статье Википедии рассказывается, как это делается: http://en.wikipedia.org/wiki/Modular_exponentiation
Как правило, если вы знаете, что ваши числа станут очень большими, вы будете использовать такую библиотеку, как GMP (Gnu Multi-Precision) для обработки математических расчетов. Он делает то, что вы делали бы на бумаге, если бы у вас на руках было 2 ^ 32 пальца.
Какая система? Какая архитектура?
Вообще говоря, на 32-битной архитектуре вы получаете результаты переполнения. Некоторые языки имеют встроенные числовые типы произвольного размера, которые могут обрабатывать эти вычисления. Примерами этого являются BigDecimal в Java и встроенные long int в Python.
слишком добавить к другим ответам, которые делают хорошее объяснение 32 int и модульной мультипликативной инверсии и что нет
Я объясню, что такое 32-битный процессор
32-битные процессоры, как большинство людей знают их, связаны с размером шины адреса
это количество доступных адресов, например, на процессоре x86 (ваш обычный настольный процессор [AMD, Intel]).
это позволяет 2^32 байт адресного пространства или 4 ГБ это обычно делится между адресуемым оборудованием и оперативной памятью, так что причина для фактической реализации 64-битного процессора была в том, что мы приближались к 4 ГБ предела оперативной памяти
в качестве побочного примечания это ранее происходило, когда процессоры были 16-битными
Используется это (a * b) mod c = ((a mod c) * (b mod c)) mod c. Это означает, что вы можете в основном
- начать с x = 1
- Выполнить x = (x * 2)% 7 56 раз