if 13* D = 1 mod 60 then D = 37 how?
Solution 1
i think this is what you are looking for
Verifying the answer is easy, finding it in the first place, a little more work.
Verification:
13 * 37 = 481
481 = 8 * 60 + 1
Hence if you divide 13 * 37 by 60 you have remainder 1.
Alternate answers:
Any integer of the form (37 + 60 k) where k is any integer is also a solution. (97, -23, etc.)
To find the solution you can proceed as follows:
Solve:
13 d = 1 + 60 k
mod 13:
0 = 1 + 8k (mod 13)
8k = -1 (mod 13)
Add 13's until a multiple of 8 is found:
8k = 12 or 25 or 38 or 51 or 64 .... aha a multiple of 8!
k = 64 / 8 = 8
Substitute k = 8 back into 13 d = 1 + 60 k
13 d = 1 + 8 * 60 = 481
481 /13 = 37
and that is the answer.
Solution 2
Use the extended Euclidean algorithm to compute integers x and y such that
13*x+60*y=1
Then x is the answer you're looking for, mod 60.
AmanS
Updated on June 07, 2022Comments
-
AmanS over 1 year
I am solving an example problem, RSA algorithm
I have been given two prime numbers 7 and 11. Let's sayp=7
andq=11
I have to calculate the decryption key,d
, for some encryption key,e
.Firstly I calculated
n=p*q
which implies thatn=77
.Suppose that
e=13
,
to calculated
I used the formulad*e = 1 mod fi
, wherefi=(p-1)(q-1)
, and sofi=60
The final equation becomes
13*d = 1 mod fi
According to some solved example
d
is calculated to be 37, how is this result obtained?Any help would be appreciated.
-
Aki Suihkonen almost 10 yearsen.wikipedia.org/wiki/Linear_congruence_theorem . When the modulus is small (e.g. uint32_t), you can write a program to test each candidate and get the result in no time.
-
Maarten Bodewes almost 10 yearsThis question appears to be off-topic because it is not about programming.
-
-
AmanS almost 10 yearswhat is the simplest method to calculate x because in your equation y is also unknown