Please add Made-Easy test series in Title.

The Gateway to Computer Science Excellence

+3 votes

Best answer

Given $n$=3599 and $e$=31

$n$ = $p*q$ where $p$ and $q$ are prime numbers

$3599 = 59 * 61$

We have, $ed$=$1mod\phi(n) $

Where , $ \phi(n) $ is Euler's tortient function .

$ \phi(n) =(p-1) * (q-1) $

$ \phi(n) = 58 * 60 = 3480 $

Now 31 * $d$ = $1mod( 3480) $

$3480 * X + 31 * Y = 1$

Step1: Eucledian Algorithm

----------------------------------------------

3480 = 112 * (31) + 8

31 = 3 * (8) + 7

8 = 1 * (7) + 1

Step 2 : Back Substitution

-----------------------------------------

1 = 8 - 1(7)

1 = 8 - 1( 31 - 3(8) )

1 = 4(8) - 1(31)

1 = 4( 3480 - 112(31) ) - 1(31)

1 = 4(3480) - 449(31)

Since 449 is a negative number substract from tortient function

So that $d = 3480 - 449 = 3031 $

$n$ = $p*q$ where $p$ and $q$ are prime numbers

$3599 = 59 * 61$

We have, $ed$=$1mod\phi(n) $

Where , $ \phi(n) $ is Euler's tortient function .

$ \phi(n) =(p-1) * (q-1) $

$ \phi(n) = 58 * 60 = 3480 $

Now 31 * $d$ = $1mod( 3480) $

$3480 * X + 31 * Y = 1$

Step1: Eucledian Algorithm

----------------------------------------------

3480 = 112 * (31) + 8

31 = 3 * (8) + 7

8 = 1 * (7) + 1

Step 2 : Back Substitution

-----------------------------------------

1 = 8 - 1(7)

1 = 8 - 1( 31 - 3(8) )

1 = 4(8) - 1(31)

1 = 4( 3480 - 112(31) ) - 1(31)

1 = 4(3480) - 449(31)

Since 449 is a negative number substract from tortient function

So that $d = 3480 - 449 = 3031 $

+1 vote

n=3599=3600-1 = 60*60 - 1 = 60^2 - 1^2 = (60+1)(60-1) = 61*59 = p*q

p=61

q=59

phi(n) = (p-1)(q-1) = (61-1)(59-1) = 60*58 = 3480

(e*d) % phi(n) = 1

31d % 3480 = 1

Divident = 31d

Quotient = k

Divisor = 3480

Remainder = 1

Divident = remainder + quotient*divisor

=> 31d = 1 + k*3480

=> d=(1+k*3480)/31

k,d are positive integers

By Brute Force, If I apply k=27, then I get (1+27*3480)/31 = (1+93960)/31 = 93961/31 = 3031

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,242 answers

194,294 comments

95,950 users