Show all threads Hide all threads Show all messages Hide all messages |
Small hint | andreyDagger | 1141. RSA Attack | 17 Nov 2021 13:58 | 1 |
(p-1)(q-1) is euler function value of n. |
This problem involves number theory??? | Miguel Angel | 1141. RSA Attack | 17 Aug 2016 14:40 | 5 |
This problem involves number theory??? > This problem involves number theory??? yes, you can refer to chapter 33 of Introduction to Algorithms, MIT Press, there covers enough knowledge you need to solve the problem. suppose d is multiplicative inverse of e, modulo (p - 1)(q - 1), where p * q = n then the answer should be c^d (mod n) > > This problem involves number theory??? > > yes, you can refer to chapter 33 of Introduction to Algorithms, > MIT Press, there covers enough knowledge you need to solve the > problem. > > suppose d is multiplicative inverse of e, modulo (p - 1)(q - 1), > where p * q = n > > then the answer should be c^d (mod n) Но ведь ответ не всегда верен! Контрпример: e=3 n=15 (p=3,q=5) c=3 GCD(e,(p-1)(q-1))=GCD(3,8)=1 e<(p-1)(q-1) e*d=1 modulo (2*4) => d=3 m=c^d (modulo n)=3^3 mod (15)=(15+12) modulo (15)=12 (modulo 15) != 3 modulo (15)=c modulo (15) Проблема возникает в случае GCD(c,n)>1 (p or q (if pq then c=0 mod (n))). Автор забыл упомянуть, что GCD(c,n)=1 или мне повезло с АС? Edited by author 17.08.2016 14:41 |
Python TL#1 | Semm | 1141. RSA Attack | 3 Aug 2016 16:31 | 2 |
What's wrong with me (or with this test)? Usually test #1 is the example. I don't see where the problem could come form. I know there were other people getting TL, could you tell what's the problem. What's wrong with this problem? I translated my code on C# and it got AC 0.015. |
why WA test#1 | magzhan | 1141. RSA Attack | 25 Oct 2015 14:30 | 4 |
Now TL on test#1, what's wrong, I don't understand everything I also got AC out there. 250 ms. 1300 kb. Here I got TLE. 102 kb. using long long rather than int |
Could anyone sent his program to me? | Tony | 1141. RSA Attack | 30 Nov 2013 18:54 | 4 |
|
strange test #1 | Baurzhan | 1141. RSA Attack | 28 Apr 2011 11:11 | 2 |
I wonder why I'm getting either TL or Crash on the test #1. Complexity of my approach is K*sqrt(N)*log(N) - more than enough! About crash - bounds of my array is ok, I never divide by zero - something else? Very strange. Please,somebody give some tests. Edited by author 28.04.2011 10:32 Edited by author 28.04.2011 10:32 I forgot ifndef ONLINE_JUDGE =) |
Give me some tests!PLZ! I have WA test1!!! | Krukov=>[ProgMyaZzz] | 1141. RSA Attack | 14 Jun 2007 19:01 | 1 |
{$N+,E-} program tmp2; {$APPTYPE CONSOLE} uses SysUtils; var i,k,j,p,q,d:integer; n,e,c:int64; function pow1(a,k:int64):int64; var b:int64; begin b:=1; while k>0 do if k mod 2 = 0 then begin k:=k div 2; a:=a*a; end else begin dec(k); b:=b*a; end; pow1:=b; end; function powmod(a,k,n:int64):int64; var b:int64; begin b:=1; while k>0 do if k mod 2 = 0 then begin k:=k div 2; a:=(a*a) mod n; end else begin dec(k); b:=(b*a) mod n; end; powmod:=b; end; procedure factor(n:integer); var d:integer; begin for d:=2 to trunc(sqrt(n)) do if n mod d =0 then begin p:=d; q:=n div d; exit; end; end; begin { TODO -oUser -cConsole Main : Insert code here } { reset(input,'data.in'); rewrite(output,'data.out');} readln(k); for i:=1 to k do begin readln(e,n,c); factor(n); d:=1; while (1+k*(p-1)*(q-1)) mod e <> 0 do inc(k); d:=(1+k*(p-1)*(q-1)) div e; writeln(powmod(c,d,n)); end; end. |
WA1! | I&K | 1141. RSA Attack | 7 Oct 2006 22:33 | 1 |
WA1! I&K 7 Oct 2006 22:33 My program accept all my tests,but I have WA1. Can you give me some tests pls. |
Am I true? | Trần Quang Chung | 1141. RSA Attack | 17 Jun 2006 14:39 | 2 |
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! I don't think it's fast enough. |
Thanks to CLRS.I got AC in 0.015sec. | Yu YuanMing | 1141. RSA Attack | 15 Apr 2005 21:39 | 2 |
AC in 0.001sec :-) I used Extended-Eular to count Mult-invers |
How to do it fast? | Sbreg | 1141. RSA Attack | 10 Aug 2004 18:21 | 2 |
My programm find secret key d (e*d mod (p-1)*(q-1)=1) and compute c^d mod n (=m) with "russian peasant method". But 0.981 sec is very bad. I have the same algorithm and AC program in 0.421 sec. How did all these people solve the problem better than in 0.1 sec? Maybe some idea of optimization? |
How to solve this problem ? Can anyone give me some hints. | hello | 1141. RSA Attack | 26 May 2004 10:08 | 1 |
|
Do you have any goodidea? | Tony | 1141. RSA Attack | 15 Oct 2002 16:12 | 3 |
But I don't have any book on number theory.Could you tell me more about it?Thanks! |
How to do it?Please help!!! | linchuan | 1141. RSA Attack | 26 May 2002 14:18 | 1 |
|
Thanks for Miguel Angel's help.He is kind hearted. | Nazarov Denis (nsc2001@rambler.ru) | 1141. RSA Attack | 31 Jan 2002 19:47 | 1 |
|