|
|
(p-1)(q-1) is euler function value of n. 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 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. 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 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 =) {$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. My program accept all my tests,but I have WA1. Can you give me some tests pls. 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. AC in 0.001sec :-) I used Extended-Eular to count Mult-invers 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? > But I don't have any book on number theory.Could you tell me more about it?Thanks! |
|
|