Discussion @ 1141. RSA Attack @ Timus Online Judge

Online Judge	Problems	Authors	Online contests
About Online Judge Frequently asked questions Site news Webboard Links	Problem set Submit solution Judge status Guide	Register Update your info Authors ranklist	Current contest Scheduled contests Past contests Rules

back to board

Discussion of Problem 1141. RSA Attack

Am I true?

Posted by Trần Quang Chung 16 Jun 2006 08:55

We can assume m=k*n+x. So
              m^e mod n = c
          <->(k*n+x)^e mod n = c
          <-> x^e mod n = c
=> We can find m in [1, n] : m^e mod n = c
=> My algorithm run in O(nlogn). Is it fast enough? (because it TLE on test#1)
Explain me!

Re: Am I true?

Posted by N.M.Hieu ( DHSP ) 17 Jun 2006 14:39

I don't think it's fast enough.