2,881 views
2 votes
2 votes
How To Solve..?

17 * d  =  1 mod 3120.

should we need to apply bruteforce?

3 Answers

Best answer
1 votes
1 votes
$3120 \ \text{%} \ 17 = 9$

$3120 \ \text{/} \ 17 = 183$

$17 \ \text{%} \ 9 = 8$

$17 \ \text{/} \ 9 = 1$

$9 \ \text{%} \ 8 = 1  $

$1 = 9 - 8$

$1 = (3120 - 183 \times 17) - 8$

$1 = (3120 - 183 \times 17) - (17 - 9)$

$1 = (3120 - 183 \times 17) - (17 - (3120 - 183 \times 17) )$

$1 = (3120 - 183 \times 17) - 17 + (3120 - 183 \times 17) $

$1 = 2 \times (3120 - 183 \times 17) - 17$

$1 = 2(3120)  - 2(183 \times 17) - 17$

$1 = 2(3120)  - 367 \times 17$

$d = 3120 - 367 = 2753$
selected by
0 votes
0 votes

17d % 3120 = 1

Divident = 17d

Quotient = k

Divisor = 3120

Remainder = 1

Divident = remainder + quotient*divisor

=> 17d = 1 + k*3120

=> d=(1+k*3120)/17

k,d are positive integers

By Brute Force, If I apply k=15, then I get (1+15*3120)/17 = (1+46800)/17 = 46801/17 = 2753

 

In Exam, depending on Time, u can apply either this or Mk Utkarsh's procedure

Related questions

1 votes
1 votes
1 answer
3
Nitesh Methani asked Jan 11, 2017
1,162 views
How to find value of d in RSA algorithm given the values of p , n and e ?Example:p=11q=7hence n =77z = 10 × 6 = 60e =13 (given)Now d should be multiplicative inverse of ...
2 votes
2 votes
2 answers
4
piya asked Jul 23, 2018
11,950 views
In an RSA system, the public key of given user is e = 31 and n = 3599. The private key of user will be ________