How does the system perform the 2^56 modulo 7, if it's 32 bits operating system in cryptography for example?
And how it stored in memory?
A 32-bit operating system does not limit you from having custom types that exceed that size. Your application can take two 32-bit words and treat it like one 64-bit number. Most programming languages even have a "double-word" integral type to simplify matters.
You can further extend the concept to create an arbitrary precision integral data type that is only bound by the amount of limited memory. Essentially you have an array of words, and you store your N-bit numbers in the bits of the words of this array.
The fact that it's a 32-bit operating system does not by itself limit the numeric computation that you can do. A Java long
, for example, is a 64-bit integral type, regardless of where it's running. For an arbitrary precision, java.math.BigInteger
ups the ante and provides "infinite word size" abstraction. And yes, this "feature" is available even in 32-bit operating systems (because that was never a limiting factor to begin with).
Finding modular multiplicative inverse or modular exponentiation is a common mathematical/algorithmic task in the fields of cryptography.
One identity that you may want to use here is the following:
A * B (mod M) == (A (mod M)) * (B (mod M)) (mod M)
To find x = 256 (mod 7), you do NOT have to first compute and store 256. If you have y = 255 (mod 7) -- a number between 0..6 -- you can find x = y * 2 (mod 7).
But how do you find y = 255 (mod 7)? Well, one naive way is to apply the process linearly and first try to find z = 254 (mod 7) and so on. This is a linear exponentiation, but you can do better by performing e.g. exponentiation by squaring.
That is, if you have say 28, you can square it to immmediately get 216. You can then square that to immediately get 232.
There are many sophisticated mathematical algorithms applicable to cryptography, and whether or not it's implemented in a program running on a 32-bit or a 64-bit operating system is not directly relevant. As long as enough memory is available, the computer is more than capable of performing arbitrary-precision arithmetic.
Precisely because arbitrary-precision arithmetic is a useful abstraction, many high-performance libraries are available, so that you can build your application on top of a pre-existing framework instead of having to build from the ground up.
Some high-level languages even have arbitrary-precision arithmetic built-in. Python, for example, provides arbitrary precision int
and long
at the language level.