Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

Alright Ive been working on this one for a while I found φ(60131) to be 97294

½(60131+60131(5)^.5) = 97294

then I worked through the GCD

GCD(985,97294) = 1
97294 = 985*98+764
985=764*1+221
764 = 221*3+101
221 = 101*2+19
101=19*5+6
19= 6*3+1
6 = 1*6     GCD = 1

Now Im stuck trying to find the inverse of 985 mod φ(60131) this is the work I have

19 – (6*3) = 1 --> 19 – (101 – (19*5))*3 = 1
19*15 - 284 = 1 --> (221 – (101*2))*15 – 284 = 1
-101*30+3031=1 --> -(764-(221*3))*30+3031 = 1
221*90-19889 --> (985 - 764)*90-19889=1
-764*90+68761=1 --> -(97294-(985*98))*90+68761=1
985*8820-8687699=1

I was expecting 8687699 to be divisible by 97294 what went wrong?

share|improve this question
1  
Shouldn't this belong in math.stackexchange, though? I mean, the relation to crypto is hazy at best, this is more of a computation question than anything else. – Thomas Aug 6 '12 at 13:22
1  
@Thomas Since this algorithm is fundamental to the operation of RSA, crypto seems like a reasonable location. I believe it was originally tagged with "homework", so I assume this is some sort of assignment to demonstrate breaking of RSA by factoring the public key. – Iridium Aug 6 '12 at 18:54
Thanks lridium I didnt think much before posting and I didnt even know that there was a crypto stackexchange I was searching for help before posting and saw a similar problem where I originally posted it – Mintybacon Aug 6 '12 at 22:50

migrated from stackoverflow.com Aug 6 '12 at 11:40

1 Answer

up vote 3 down vote accepted

I think you may have calculated φ(60131) incorrectly.

60131 has two prime factors: 157, 383 Therefore: φ(60131) = (157-1) * (383-1) = 59592

GCD(985,59592) = 1
59592 =  60 * 985 + 492
  985 =   2 * 492 + 1
  492 = 492 * 1

So to determine the inverse of 985 mod φ(60131):

1 = 985 - 2 * 492
1 = 985 - 2 * (59592 - 60 * 985)
1 = 985 - 2 * 59592 + 120 * 985
1 = 121 * 985 - 2 * 59592

Therefore 121 is the inverse of 985 mod φ(60131).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.