Modular arithmetic in cryptography?

Question

As part of some lecture notes I'm trying to calculate the following:

x = (1/N) (Mod R)

where N = 1073741827

and R is 4294967296

How do I solve this? The answer is given as 1789569707.
Is this the only answer?

thx

Answer 1

Ian's answer is excellent. Let me show you a shorter way.
It's based on Euclid's extended algorithm
(D.E. Knuth, Art of Computer Programming, vol.2, p.342)
We want to solve Nx = 1(mod R). (*)
If N = 1073741827 and R = 4294967296
we see that R = 2^32 and N is odd, so there is a unique
solution mod R.
Next solving (*) requires that we solve
Nx - Ry = 1.
To solve this by Euclid's extended algorithm,
we write the vectors
1 0 N 0 1 R
and perform Euclid's algorithm on these 2 vectors.
But we can shorten the work further.
If we are solving (*), we aren't interested in the
value of y, so we can suppress the middle column
and write
1 N 0 R
and perform Euclid's algorithm on these 2 vectors instead.
So let's see what happens.
1 1073741827 0 4294967296
Here the quotient is 0, so we swap the 2 vectors:
0 4294967296 1 1073741827
Next, q = [429496726/1073741827] = 3.
So our next 2 vectors are
1 1073741827 -3 1073741815
Here are the remaining steps:
q = 1
-3 1073741815 4 12

q = 89478484
4 12 -357913939 7
q = 1
-357913939 7 357913943 5
q = 1
357913943 5 -715827882 2
q = 2
-715827882 2 1789569707 1
q = 2
1789569707 1 _______ 0
Since the last remainder is 0, we have our
answer at last:
x = 1789569707(mod 2^32).

Answer 2

If x = (1/N) (mod R)
then
x*N = 1 (mod R)
There are several techniques you can use to solve this. I will detail the Euclid algorithm.

First divide 4294967296 by 1073741827 and find the remainder.
4294967296 = 3 * 1073741827 + 1073741815
or rearranging:
1073741815 = 4294967296 - 3 * 1073741827 ... (1)

Next repeat with this with 1073741827 and 1073741815.
1073741827 = 1 * 1073741815 + 12
or rearranging:
12 = 1073741827 - 1 * 1073741815 ... (2)

Then repeat with 1073741815 and 12.
1073741815 = 89478484 * 12 + 7
or rearranging:
7 = 1073741815 - 89478484 * 12 ... (3)

Then repeat with 12 and 7.
12 = 7 * 1 + 5
or rearrnaging:
5 = 12 - 7 * 1 ... (4)

Then repate with 7 and 5.
7 = 5 * 1 + 2
or rearranging:
2 = 7 - 5 * 1 ... (5)

Then repeat with 5 and 2.
5 = 2 * 2 + 1
or rearranging:
1 = 5 - 2 * 2 ... (6)

Now that you have gotten down to a remainder of 1 we can build it back up.
So rewriting the last line gives:
1 = 5 - 2 * 2
Then subbing in (5) the second last line gives:
1 = 5 - 2 * (7 - 5 * 1)
1 = 5 - 2*7 + 2*5
1 = 3*5 - 2*7
Then subbing in (4) gives:
1 = 3*(12 - 7 * 1) - 2*7
1 = 3*12 - 3*7 - 2*7
1 = 3*12 - 5*7
Then subbing in (3) gives:
1 = 3*12 - 5*(1073741815 - 89478484 * 12)
1 = 3*12 - 5*1073741815 + 447392420*12
1 = 447392423*12 - 5*1073741815
The subbing in (2) gives:
1 = 447392423*(1073741827 - 1 * 1073741815) - 5*1073741815
1 = 447392423*1073741827 - 447392423*1073741815 - 5*1073741815
1 = 447392423*1073741827 - 447392428*1073741815
Then subbing in (1) gives:
1 = 447392423*1073741827 - 447392428*(4294967296 - 3 * 1073741827)
1 = 447392423*1073741827 - 447392428*4294967296 + 1342177284*1073741827
1 = 1789569707*1073741827 - 447392428*4294967296
And then if you apply (mod 4294967296) to it you can see that the second part will disappear at it is an integeral multiple of 4294967296.
And hence
1 = 1789569707*1073741827 (mod 4294967296)
And so your answer is 1789569707.
And it is the only answer in modulo 4294967296.