How does a 32-bit operating system perform the 2^56 modulo 7?

Question

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?

Barron

Analogy: We can only count up to 10 with our fingers (or 1023, if you use them correctly (and then only 256, if you want to use them comfortably)) but when using the same fingers to hold a pen and a sheet of paper we can handle numbers way larger than that. Substitute fingers for register and pen and sheet of paper by programming language and/or library. – Cenacle

I think it's possible with my fingers :) But how exactly? And i think the right answer it's modular exponentiation – Barron

Law of Modulus: (A+B) mod C == ((A mod C) + (B mod C)) mod C Actually, from that, you can derive everything else. – Forebrain

Thank you. I find this also: Montgomery reduction. In fact exists a lot of algorithm for do a modulo with big numbers! :) en.wikipedia.org/wiki/Montgomery_reduction – Barron

@regexp: When you say 2^56/7 do you mean "two raised to 56th power, divided by 7", or "two raised to 56th power, modulo 7"? You may want to check up on the notational convention if you want to work further in this field. – Trochlear

@ polygenelubricants: sorry, it's my mistake. i mean "two raised to 56th power, modulo 7". I will change the title – Barron

Strictly speaking, a 32-bit system should be able to handle numbers as large as 256^2147483648 ((2^8)^(2^31)), so I don't see the problem with 2^56. That's, of course, using arbitrary precision arithmetic aka "bignums". – Political

Answer 1

On arbitrary-precision arithmetic

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).

See also

• Wikipediia/Arbitrary-precision arithmetic
• GNU MP BigNum library

---

On mathematics on the ring of integers

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 = 2⁵⁶ (mod 7), you do NOT have to first compute and store 2⁵⁶. If you have y = 2⁵⁵ (mod 7) -- a number between 0..6 -- you can find x = y * 2 (mod 7).

But how do you find y = 2⁵⁵ (mod 7)? Well, one naive way is to apply the process linearly and first try to find z = 2⁵⁴ (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 2⁸, you can square it to immmediately get 2¹⁶. You can then square that to immediately get 2³².

---

Summary

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.

Trochlear

Ok, and how it's work when it's more then 64 bit? For example 2^256/4 – Barron

@regexp: read the Wikipedia page about arbitrary-precision arithmetics. Abstract out the mathematics from the implementation. I think you're confusing the two for some reason. First you have to accept that 32-bit OSes can compute 2^100 if need be. Once you accept this abstraction, you can then concentrate on the mathematical/algorithmic aspects with regards to cryptography application. – Trochlear

@regexp: 2^256 mod 4 is 0. I can do that without even calculating anything. Again, distinguish the math from the 32-bit/64-bit issue. They're not directly related. – Trochlear

Fantastic answer. Thank you for taking the time to be so informative :) – Godson

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

You'll note that we never dealt with any large numbers (indeed the largest was 56).

Furthermore:

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

And thus also 2**896 %7 = 4, etc (since 896 = 4 * 224, where 224 = 4 * 56).

Hyaloid

Answer 3

Modular exponentiation algorithms are used for this kind of operation. This Wikipedia article tells how it is done: http://en.wikipedia.org/wiki/Modular_exponentiation

Psychomancy

Thank you, i think it's what i mean! – Barron

Answer 4

Generally, if you know your numbers are going to get very big, you'll use a library like GMP (Gnu Multi-Precision) to handle the math. It does what you'd do on paper if you had 2^32 fingers on you hands.

Forebrain

You don't need anything more than 16-bit arithmetic to compute 2^56 mod 7. See @polygenelubricant's answer. – Premeditation

Answer 5

Which system? Which architecture?

Generally speaking on a 32-bit architecture, you are getting overflow results. Some languages have built-in, arbitrarily big, numeral types which can handle these calculations. Examples of this are BigDecimal in Java, and the built-in long ints in Python.

Ayakoayala

I mean 32 bits system. I suppose it's can store and operate only with number 2^32 or not? – Barron

32-bit systems typically can store and operate with 32-bit numbers for one operation. If you want to manipulate larger numbers, you simply do it in several operations (see other answers for references). – Spoken

But division it's a one operation? Or the system always try do this in several times? – Barron

Answer 6

One uses that (a * b) mod c = ((a mod c) * (b mod c)) mod c. That means that you can basically do

1. start with x=1
2. Do x = (x*2)%7 56 times

Exercise

You don't want to do this with crypto, though, where in a^b (mod m) each number is thousands of bits long ;-) – Cenacle

@Joey: One definitely uses that identity, though one also uses a^(b+c) = (a^b)*(a^c) and a^(b*c)=(a^b)^c. – Pitiless

Answer 7

I think your terminology is a bit confused.

A 32 bit operating system or 32-bit architecture is one in which machine addresses are limited to 32 bits. It is not at all unusual for a 32 bit architecture to have arithmetic instructions that operate on 64 bit integers and / or 64 bit floating point numbers.

So, it is quite likely that a machine with a 32 bit architecture (and running a 32 bit operating system) would use 64 bit arithmetic and store the result in memory as a 64 bit long or long long using 2 consecutive 32 bit words.

Grani

Answer 8

too add to other answers which do a good explanation of a 32 int and modular multiplicative inverse and what not

I'll explain what a the 32 bit CPU is

32 bit CPUs as most people know them as, is related to the Address bus size this is that the amount of addresses available so for example on a x86 (your common desktop CPU [AMD, Intel]) processor this allows 2^32 bytes of address space or 4GB this is usually split between the the addressable hardware and the RAM, so the reason for actually implementing a 64 bit Processor was because we were coming closer too the 4GB of RAM limit

as a side note this has previously happened when CPU's were 16bit

Cerography