In This Earlier Posting, I had written at first some observations about Bluetooth-pairing, but then branched out on the subject, of whether a Diffie-Hellman Key Exchange could be easier to compute, if it was somehow simplified into using a 32-bit modulus. Obviously, my assumption was that a 64-bit by 32-bit divide instruction would be cheap on the CPU, while arbitrary-precision integer operations are relatively expensive, and actually cause some observable lag on CPUs which I’ve used.
And so, because I don’t only want to present theory in a form that some people may not be able to visualize, what I did next was to write a C++ program, that actually only uses C, that assumes the user only has a 32-bit CPU, and yet that performs a 64-bit by 64-bit division.
This has now been tested and verified.
One problem in writing this code is the fact that, depending on whether the divisor, which is formatted as a 64-bit field, contains an actual 64-bit, 32-bit, 24-bit, or 16-bit value, a different procedure needs to be selected, and even this fixed-precision format cannot assume that the bits are always positioned in the correct place.
I invite people to look at this sample-code:
(Update 06/10/2018, 23h30 : )
I needed to correct mistakes which I made in the same piece of code. However, I presently know the code to be correct.
Just to test my premises, I’m going to assume that the following division is to be carried out, erroneously as a simple division, but assuming a word-size of 32 bits:
0x FFFF FFFF FF00 0000 / 0x 0000 0000 8000 0000
What we would find, is that the following value will act as the temporary quotient:
0x FFFF FFFF
But, multiplying that by the divisor and subtracting, would yield a temporary remainder, still greater than the divisor. Thus, my algorithm would next subtract the divisor from that one more time, still yielding too great a remainder, and would also add (1) to the quotient, resulting in an overflow. Thus, the approach is not suited if the quotient is needed, but a derived approach might be suited if only the remainder / modulus is needed. And, the correct answer would be:
Q: 0x 0000 0001 FFFF FFFF R: 0x 0000 0000 7F00 0000