FIBO1(n)\nif n=0 then return 0;\nif n=1 then return 1;\nreturn FIBO1(n-1)+FIBO1(n-2);<\/code><\/pre>\n\n\n\n\u6307\u6570\u7ea7(exponential to n)<\/p>\n\n\n\n
algo2:<\/strong><\/p>\n\n\n\nFIBO2(n)\nif n=0 then return 0;\ncreate an array f[0...n];\nf[0]=0;f[1]=1;\nfor i=2 to n do\n| f[i]=f[i-1]+f[i-2];\nend\nreturn f[n];\n<\/code><\/pre>\n\n\n\n\u591a\u9879\u5f0f\u65f6\u95f4(polynomial), n2<\/sup><\/p>\n\n\n\nalgo3:<\/strong><\/p>\n\n\n\n\u6590\u6ce2\u90a3\u5951\u6570\u5217\u6709\u901a\u9879\u516c\u5f0f<\/p>\n\n\n\n
\u5927O\u8868\u793a\u6cd5 Big-O Notation<\/h3>\n\n\n\n
\u4e0a\u754c: f(n) is O(g(n)) (or f(n)=O(g(n)) ), \u5f53\u4e14\u4ec5\u5f53 \u5b58\u5728\u5e38\u6570c>0, \u5e38\u6570n0<\/sub>\u22650; \u4f7f\u5f97\u5bf9\u4e8e\u6240\u6709n\u2265n0<\/sub>, 0\u2264f(n)\u2264c\u00b7g(n).<\/p>\n\n\n\n\u4e0b\u754c: f(n) is \u03a9(g(n)) (or f(n)=\u03a9(g(n)) ), \u5f53\u4e14\u4ec5\u5f53 \u5b58\u5728\u5e38\u6570c>0, \u5e38\u6570n0<\/sub>\u22650; \u4f7f\u5f97\u5bf9\u4e8e\u6240\u6709n\u2265n0<\/sub>, 0\u2264c\u00b7g(n)\u2264f(n).<\/p>\n\n\n\n f(n) is \u0398(g(n)) (or f(n)=\u0398(g(n)) ), \u5f53\u4e14\u4ec5\u5f53 \u5b58\u5728\u5e38\u6570c1<\/sub>>0, c2<\/sub>>0, \u5e38\u6570n0<\/sub>\u22650; \u4f7f\u5f97\u5bf9\u4e8e\u6240\u6709n\u2265n0<\/sub>, 0\u2264c1<\/sub>\u00b7g(n)\u2264f(n)\u2264c2<\/sub>\u00b7g(n).<\/p>\n\n\n\nn! is 2\u0398(n log n)<\/sup><\/p>\n\n\n\n\u65af\u7279\u6797\u516c\u5f0f:
![\" $n! \sim \sqrt{2\pi n}(\frac{n}{e})^{n}$ \"](\"data:image\/svg+xml;base64,PCEtLUFyZ29uTG9hZGluZy0tPgo8c3ZnIHdpZHRoPSIxIiBoZWlnaHQ9IjEiIHhtbG5zPSJodHRwOi8vd3d3LnczLm9yZy8yMDAwL3N2ZyIgc3Ryb2tlPSIjZmZmZmZmMDAiPjxnPjwvZz4KPC9zdmc+\" "\\"Rendered")
<\/div><\/p>\n\n\n\n\u6570\u5b57\u7684\u7b97\u6cd5<\/h2>\n\n\n\n\u57fa\u672c\u7b97\u6570<\/h3>\n\n\n\n
\u9664\u975e\u4f7f\u75281\u8fdb\u5236\uff0c\u5426\u5219\u8ba1\u7b97\u673a\u8fdb\u5236\u4e0d\u5f71\u54cd\u590d\u6742\u5ea6<\/p>\n\n\n\n
\u52a0\u6cd5\u590d\u6742\u5ea6\u662fO(n)\uff0c\u56e0\u4e3a\u8bfb\u53d6\u81f3\u5c11\u662fO(n)\uff0c\u65e0\u6cd5\u4f18\u5316<\/p>\n\n\n\n
\u4e58\u6cd5\u7b97\u6cd5<\/h4>\n\n\n\n
\u6309\u7ad6\u5f0f\u8ba1\u7b97\u7684\u65b9\u6cd5\uff1a\u590d\u6742\u5ea6\u662fO(n2<\/sup>)\uff0c\u4f46*2\u64cd\u4f5c\u662fO(1)\uff0c\u6240\u4ee5\u53ef\u4ee5\u4f18\u5316<\/p>\n\n\n\nAl Khwarizmi<\/strong><\/p>\n\n\n\n\n\n\n- \u4e24\u4e2a\u4e58\u6570\u5206\u5f00\u5199<\/li>\n\n\n\n
- \u5de6\u8fb9\/2\uff0c\u53f3\u8fb9*2<\/li>\n\n\n\n
- \u76f4\u5230\u5de6\u8fb9\u53d8\u4e3a1<\/li>\n\n\n\n
- \u53bb\u6389\u5de6\u8fb9\u4e3a\u5076\u6570\u7684\u884c<\/li>\n\n\n\n
- \u5c06\u53f3\u8fb9\u7684\u6570\u76f8\u52a0<\/li>\n<\/ul>\n<\/div>\n\n\n\n\n<\/div><\/p>\n<\/div>\n<\/div>\n\n\n\n
\u516c\u5f0f\uff1a
<\/div><\/p>\n\n\n\nalgo:<\/strong><\/p>\n\n\n\nMULTIPLY(x,y)\nif y=0 then return 0;\nz=MULTIPLY(x,[y\/2]);\nif y%2=0 then\n| return 2z;\n| else return x+2z;\nend<\/code><\/pre>\n\n\n\n\u590d\u6742\u5ea6\u5206\u6790\uff1a\u9012\u5f52n\u6b21\uff0c\u6bcf\u6b21\u90fd\u53ef\u80fd\u6709\u52a0\u6cd5\uff0c\u52a0\u6cd5\u662fO(n)\uff0c\u6240\u4ee5\u8fd8\u662fO(n2<\/sup>)\uff0c\u8fd8\u6709\u4f18\u5316\u7a7a\u95f4<\/p>\n\n\n\n\u9664\u6cd5\u7b97\u6cd5<\/h4>\n\n\n\nDIVIDE(x,y)\nif x=0 then return (0,0);\n(q,r)=DIVIDE([x\/2],y);\nq=2\u00b7q, r=2\u00b7r;\nif x is odd then r=r+1;\nif r\u2265y then r=r-y;q=q+1;\nreturn (q,r)<\/code><\/pre>\n\n\n\n\u590d\u6742\u5ea6\u5206\u6790\uff1a\u9012\u5f52n\u6b21\uff0c\u6bcf\u6b21\u90fd\u53ef\u80fd\u6709\u52a0\u6cd5\uff0c\u52a0\u6cd5\u662fO(n)\uff0c\u6240\u4ee5\u662fO(n2<\/sup>)<\/p>\n\n\n\n\u6a21\u8fd0\u7b97<\/h3>\n\n\n\n
x\u2261y mod N \u21d4 N divides (x-y)\uff08N\u88ab(x-y)\u6574\u9664\uff09<\/p>\n\n\n\n
\u2261\uff1a\u8bed\u6cd5\/\u8bed\u4e49\u4e0a\u7b49\u4e8e<\/p>\n\n\n\n
\u8fd0\u7b97\u6cd5\u5219\uff1a<\/p>\n\n\n\n
\n- \u66ff\u6362\uff1ax\u2261x’ mod N and y\u2261y’ mod N, \u21d2 x+y\u2261x’+y’ mod N and xy\u2261x’y’ mod N<\/li>\n\n\n\n
- \u6ee1\u8db3\u52a0\u6cd5\/\u4e58\u6cd5 \u4ea4\u6362\/\u7ed3\u5408\u5f8b\u3001\u4e58\u6cd5\u5206\u914d\u5f8b\uff1b<\/li>\n\n\n\n
- \u6a21\u8fd0\u7b97\u53ef\u4ee5\u968f\u65f6\u5e94\u7528\u5728\u4efb\u4f55\u9636\u6bb5\uff1a2345<\/sup>\u2261(25<\/sup>)69<\/sup>\u22613269<\/sup>\u2261169<\/sup>\u22611 mod 31<\/li>\n<\/ul>\n\n\n\n
\u6a21\u52a0\u3001\u6a21\u4e58\u3001\u6a21\u6307\u6570<\/strong><\/h4>\n\n\n\n\u6a21\u52a0\uff1ainput (x,y) output (x+y) mod N\uff0c\u65f6\u95f4\u590d\u6742\u5ea6O(n)\uff08\u52a0\u6cd5\uff0b\u51cf\u6cd5\uff09\uff0cn\u4e3a\u957f\u5ea6<\/p>\n\n\n\n
\u6a21\u4e58\uff1ainput (x,y) output (xy) mod N\uff0c\u65f6\u95f4\u590d\u6742\u5ea6O(n2<\/sup>)\uff08\u4e58\u6cd5\uff0b\u9664\u6cd5\uff09\uff0cn\u4e3a\u957f\u5ea6<\/p>\n\n\n\n\u6a21\u6307\u6570\uff1ainput (x,y) output (xy<\/sup>) mod N\uff0c\u6a21\u6307\u6570\u8fc7\u4e8e\u5927\uff0c\u5982\u4f55\u8ba1\u7b97\uff1a<\/p>\n\n\n\nfirst idea\uff1ax mod N->x2<\/sup> mod N->x3<\/sup> mod N->…->xy<\/sup> mod N\uff0c\u4ecd\u7136\u5f88\u5927<\/p>\n\n\n\nsecond idea\uff1ax mod N->x2<\/sup> mod N->x4<\/sup> mod N->…->x2^[log y]<\/sup> mod N\uff0c\u5bf9\u4e8e\u4e00\u822c\u7684y\uff0c\u5ffd\u7565y\u4e8c\u8fdb\u5236\u8868\u793a\u4e3a0\u7684\u4f4d\uff0c\u4f8b\uff1a<\/p>\n\n\n\nx25<\/sup> mod N=(x16<\/sup> mod N)(x8<\/sup> mod N)(x1<\/sup> mod N)<\/p>\n\n\n\nalgo\uff1a<\/strong><\/p>\n\n\n\nMODEXP(x,y,N)\nif y=0 then return 1;\nz=MODEXP(x,[y\/2],N);\nif y%2=0 then\n| return z2<\/sup> mod N;\n| else return x\u00b7z2<\/sup> mod N;\nend<\/code><\/pre>\n\n\n\n\u590d\u6742\u5ea6\u5206\u6790\uff1a\u9012\u5f52n\u6b21\uff0c\u6bcf\u6b21\u90fd\u505an\u4f4d\u6570\u7684\u4e58\u6cd5\uff0cO(n3<\/sup>)<\/p>\n\n\n\n\u6b27\u51e0\u91cc\u5f97\u7684\u6700\u5927\u516c\u56e0\u6570(gcd)\u7b97\u6cd5<\/h4>\n\n\n\n
algo:<\/strong><\/p>\n\n\n\ngcd(x,y)\nTwo integers with x\u2265y<\/em>\nif y=0 then return x;\nreturn gcd(y,x mod y);<\/code><\/pre>\n\n\n\n\nLemma: If a\u2265b\u22650, then a mod b < a\/2\uff1b<\/p>\n\n\n\n
Proof: \u6309b\u5173\u4e8ea\/2\u7684\u5927\u5c0f\u5173\u7cfb\u5206\u7c7b\u8ba8\u8bba\u5373\u53ef<\/p>\n<\/blockquote>\n\n\n\n
\u590d\u6742\u5ea6\u5206\u6790\uff1a\u6700\u591a\u5faa\u73afn\u8f6e\uff0c\u6bcf\u6b21\u505a\u9664\u6cd5\uff0cO(n3<\/sup>)<\/p>\n\n\n\n\nLemma: if d\u6574\u9664x\u548cy, and \u5b58\u5728\u6574\u6570<\/strong>a,b\u4f7f\u5f97d=ax+by, then d=gcd(x,y)<\/p>\n\n\n\n\u4f8b\uff1a10\uff0c15\u6700\u5927\u516c\u56e0\u6570\u4e3a5\uff0ca,b\u53d6\u503c-1,1<\/p>\n\n\n\n
Proof: <\/p>\n\n\n\n
\n- \u663e\u7136d\u2264gcd(x,y);<\/li>\n\n\n\n
- gcd(x,y)\u88abx\u3001y\u6574\u9664\uff0c\u4e5f\u88abd=ax+by\u6574\u9664\uff0c\u6240\u4ee5d\u2265gcd(x,y);<\/li>\n\n\n\n
- \u6240\u4ee5d=gcd(x,y)<\/li>\n<\/ul>\n<\/blockquote>\n\n\n\n
\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff1a\u7528\u4e8e\u6c42\u51fad\u7684\u540c\u65f6\u5f97\u51fa\u6574\u6570a\u3001b<\/p>\n\n\n\n
algo\uff1a<\/strong><\/p>\n\n\n\nextended-euclid(a,b)\nTwo integers with a\u2265b<\/em>\nif b=0 then return (1,0,a);\n(x',y',d)=extended-euclid(b,a mod b);\nreturn (y',x'-[a\/b]y',d);\/\/\u6bcf\u6b21\u8fdb\u884ca mod b\u5b9e\u9645\u51cf\u5c11\u4e86[a\/b]\u4e2ay\nend<\/code><\/pre>\n\n\n\n\u4e58\u6cd5\u9006\u5143\u548c\u6a21\u9664<\/h4>\n\n\n\n
\u4e58\u6cd5\u9006\u5143\uff1a<\/strong>x\u662fa mod N\u7684\u4e58\u6cd5\u9006\u5143\uff0cif ax\u22611 mod N<\/p>\n\n\n\n\u4e58\u6cd5\u9006\u5143\u81f3\u591a\u6709\u4e00\u4e2a\uff0c\u53ef\u4ee5\u5199\u4f5ca-1<\/sup>\uff0c\u4e58\u6cd5\u9006\u5143\u53ef\u80fd\u4e0d\u5b58\u5728<\/p>\n\n\n\n\nLemma: \u4e0d\u5b58\u5728\u4e58\u6cd5\u9006\u5143\u5f53\u4e14\u4ec5\u5f53gcd(a,N)>1(or a\u4e0eN\u4e0d\u4e92\u8d28)<\/p>\n\n\n\n
Proof: <\/p>\n\n\n\n
\n- gcd(a,N)>1\u21d2\u4e0d\u5b58\u5728\u4e58\u6cd5\u9006\u5143
- gcd(a,N)\u6574\u9664ax+kN\uff0cax+kN\u2261ax mod N \u21d2 ax mod N>=gcd(a,N)>1<\/li><\/ul><\/li>\n\n\n\n
- gcd(a,N)=1\u21d2\u5b58\u5728\u4e58\u6cd5\u9006\u5143
- ax mod N = ax+kN, then gcd(a,N)\u6574\u9664ax+kN=ax mod N<\/li>
- gcd(a,N)=1, \u5e94\u7528\u62d3\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff0c\u7ed9\u51fax,y\u4f7f\u5f97ax+Ny=1\uff0cthen ax\u22611 mod N\uff0cx\u662fa\u7684\u9006\u5143<\/li><\/ul><\/li>\n<\/ul>\n<\/blockquote>\n\n\n\n
\u6a21\u9664<\/strong>\uff08\u6ce8\u610f\u4e0d\u662f\u53d6\u4f59\u6570\uff0c\u4e5f\u4e0d\u662f(a\/b) mod N\uff09input(a,b) output c that (b*c) mod N=a mod N<\/p>\n\n\n\n\u5728\u6a21\u9664\u4e2d\uff0c\u88aba\u9664\u76f8\u5f53\u4e8e\u4e58a\u7684\u4e58\u6cd5\u9006\u5143\uff0c\u6240\u4ee5\u5982\u679c\u4e58\u6cd5\u9006\u5143\u5b58\u5728\uff0c\u53ef\u4ee5\u7528\u62d3\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u5728O(n3<\/sup>)\u65f6\u95f4\u5185\u6c42\u5f97\u3002<\/p>\n\n\n\n\u4f8b\uff1a<\/p>\n\n\n\n
\n- \u6c42(11\/4) mod 5\uff0c4\u7684\u4e58\u6cd5\u9006\u5143\u662f4\uff0c\u6240\u4ee5\u5373\u6c42(11*4) mod 5=4<\/li>\n\n\n\n
- \u6c42(45\/7)mod 10\uff0c7\u7684\u4e58\u6cd5\u9006\u5143\u662f3\uff0c\u6240\u4ee5\u5373\u6c42(45*3) mod10=5<\/li>\n<\/ul>\n\n\n\n
\u7d20\u6570<\/h3>\n\n\n\n\u7d20\u6570\u6d4b\u8bd5<\/h4>\n\n\n\n\n\u8d39\u9a6c\u5c0f\u5b9a\u7406\uff1ap\u4e3a\u8d28\u6570\uff0c\u5219\u4efb\u610f1\u2264a<p\uff0cap-1<\/sup>\u22611 mod p<\/p>\n\n\n\nProof: <\/p>\n\n\n\n
\n- \u53d6\u96c6\u5408S={1,2,3,…,P-1}={a mod p, 2a mod p, 3a mod p, …, (p-1)a mod p}\uff08\u6ce8\u610f\u4e24\u4e2a\u96c6\u5408\u6570\u503c\u4e00\u4e00\u5bf9\u5e94\u4f46\u662f\u987a\u5e8f\u4e0d\u5bf9\u5e94\uff09
- \u8bc1\u660e\u4e24\u4e2a\u96c6\u5408\u4e00\u4e00\u5bf9\u5e94\uff1a\u82e5\u4e0d\u4e00\u4e00\u5bf9\u5e94\uff0c\u5219\u5fc5\u6709ai<\/sub>\u2261aj<\/sub>(mod p)\uff0c\u5bfc\u81f4\u4e86i\u2261j(mod p)\u21d2i=j\u77db\u76fe<\/li><\/ul><\/li>\n\n\n\n
- \u5c06\u5bf9\u5e94\u4f4d\u7f6e\u7684\u5143\u7d20\u76f8\u4e58\uff0c(p-1)! \u2261 ap-1<\/sup>\u00b7(p-1)! (mod p)<\/li>\n\n\n\n
- \u4e24\u8fb9\u540c\u9664(p-1)!\uff08\u4e0ep\u4e92\u7d20\u6240\u4ee5\u53ef\u4ee5\u9664\uff09<\/li>\n\n\n\n
- \u6240\u4ee5ap-1<\/sup>\u22611 mod p<\/li>\n<\/ul>\n<\/blockquote>\n\n\n\n
\u5bf9\u5e94\u7684\u7d20\u6570\u7b97\u6cd5\uff1a<\/strong><\/p>\n\n\n\nprimary(N)\npick a < N at random<\/strong>;\nif aN-1<\/sup>\u22611(mod N)then\n| return yes;\n| else return no;\nend<\/code><\/pre>\n\n\n\n\u4f46\u662f\uff0c\u5408\u6570\u53ef\u80fd\u901a\u8fc7\u8d39\u9a6c\u6d4b\u8bd5\u3002Carmichael\u6570\u5982561=3\u00b711\u00b717\uff0c\u5bf9\u4e8e\u4efb\u610fa<561\uff0c\u6709a560<\/sup>\u22611\uff1b<\/p>\n\n\n\n\n\u9664\u4e86Carmichael\u6570\u5916\uff0c\u6211\u4eec\u6709 \u5bf9\u4e8e\u4efb\u610f\u5408\u6570\uff0c\u5982\u679c\u5b58\u5728\u4e00\u4e2aa\u4e0d\u6ee1\u8db3aN-1<\/sup>\u22611 mod N\uff0c\u90a3\u4e48a<N\u81f3\u5c11\u6709\u4e00\u534a\u4e0d\u6ee1\u8db3aN-1<\/sup>\u22611 mod N\u3002<\/p>\n\n\n\nProof: <\/p>\n\n\n\n
\n- \u5b58\u57281\u4e2aaN-1<\/sup>!\u22611 mod N<\/li>\n\n\n\n
- \u5047\u8bbe1\u4e2abN-1<\/sup>\u22611 mod N<\/li>\n\n\n\n
- \u90a3\u4e48(a\u00b7b)N-1<\/sup>\u2261aN-1<\/sup>\u00b7bN-1<\/sup>\u2261aN-1<\/sup>!\u22611(mod N)<\/li>\n\n\n\n
- \u90a3\u4e48\u53ea\u8981\u6709\u4e00\u4e2ab\u6ee1\u8db3\uff0c\u5fc5\u7136\u5bfc\u81f4\u4e00\u4e2aa\u00b7b\u4e0d\u6ee1\u8db3\uff0c\u518d\u52a0\u4e0a\u4e00\u4e2aa\uff0c\u4f7f\u5f97\u81f3\u5c11\u6709\u4e00\u534a\u4e0d\u6ee1\u8db3<\/li>\n<\/ul>\n<\/blockquote>\n\n\n\n
\u53ef\u4ee5\u901a\u8fc7\u591a\u6d4b\u8bd5\u51e0\u4e2aa<N\uff0c\u6765\u964d\u4f4e\u51fa\u9519\u7387<\/p>\n\n\n\n
Largrange\u7d20\u6570\u5b9a\u7406\uff1a\u4ee4\u03c0(x)\u4e3a\u2264x\u7684\u7d20\u6570\u7684\u4e2a\u6570\uff0c\u5219\u6709\u03c0(x)\u2248x\/(ln x)\uff0c\u6216\u8005\u8bf4
<\/div><\/p>\n\n\n\n\u6240\u4ee5\u968f\u673a\u9009\u5b9a\u4e00\u4e2aN\uff0cN\u662f\u7d20\u6570\u7684\u6982\u7387\u81f3\u5c11\u67091\/n<\/p>\n\n\n\n
\u4e24\u7c7b\u968f\u673a\u7b97\u6cd5<\/h4>\n\n\n\n
\u8499\u7279\u5361\u6d1b\u7b97\u6cd5\uff1a<\/p>\n\n\n\n
\n- \u8fd0\u884c\u65f6\u95f4\u6709\u754c<\/li>\n\n\n\n
- \u6b63\u786e\u6027\u968f\u673a<\/li>\n\n\n\n
- \u4f8b\u5b50\uff1a\u7d20\u6570\u6d4b\u8bd5<\/li>\n<\/ul>\n\n\n\n
\u62c9\u65af\u7ef4\u52a0\u65af\u7b97\u6cd5\uff1a<\/p>\n\n\n\n
\n- \u4e00\u76f4\u6b63\u786e<\/li>\n\n\n\n
- \u8fd0\u884c\u65f6\u95f4\u968f\u673a<\/li>\n\n\n\n
- \u4f8b\u5b50\uff1a\u5feb\u6392\u3001\u54c8\u5e0c<\/li>\n<\/ul>\n\n\n\n
\u5bc6\u7801\u5b66<\/h3>\n\n\n\n
RSA\u673a\u5236\uff1a<\/p>\n\n\n\n
\u6027\u8d28\uff1a\u968f\u673a\u9009\u53d6\u4e24\u4e2a\u7d20\u6570p\u3001q\uff0c\u5e76\u4ee4N=pq\uff0c\u5bf9\u4e8e\u4efb\u610f\u4e0e(p-1)(q-1)\u4e92\u7d20\u7684\u6574\u6570e\uff0c\u6709\u4ee5\u4e0b\u6027\u8d28\u6210\u7acb\uff1a<\/p>\n\n\n\n
\n- \u6620\u5c04x\u2192xe<\/sup> mod N\u662f\u5b9a\u4e49\u5728\u96c6\u5408{0,1,…,N-1}\u4e0a\u7684\u53cc\u5411\u6620\u5c04<\/li>\n\n\n\n
- \u53e6\u5916\uff0c\u5bb9\u6613\u5f97\u5230\u8be5\u6620\u5c04\u7684\u9006\u6620\u5c04\uff1a\u4ee4d\u4e3ae mod (p-1)(q-1)\u7684\u4e58\u6cd5\u9006\u5143\uff0c\u5219\u5bf9\u4e8e\u6240\u6709{0,1,…,N-1},<\/li>\n\n\n\n
- \u6709(xe<\/sup>)d<\/sup>\u2261x mod N<\/li>\n<\/ul>\n\n\n\n
\u53d1\u5e03\u8005\u5c06(N,e)\u4f5c\u4e3a\u516c\u94a5\uff0cd\u4f5c\u4e3a\u79c1\u94a5<\/p>\n\n\n\n
Proof (xe<\/sup>)d<\/sup>\u2261x mod N: <\/p>\n\n\n\n\n- ed\u22611 mod (p-1)(q-1) \u21d2 ed= 1+ k(p-1)(q-1)<\/li>\n\n\n\n
- \u5219\u6709(xe<\/sup>)d<\/sup>-x=x1+k(p-1)(q-1)<\/sup>-x\uff0c\u53ef\u4ee5\u88abp\u6574\u9664\uff0c\u56e0\u4e3axp-1<\/sup>\u22611 mod p\uff0cq\u540c\u6837\uff0c\u5219\u5fc5\u5b9a\u88abN=pq\u6574\u9664<\/li>\n<\/ul>\n\n\n\n
\u5206\u6cbb\u7b97\u6cd5<\/h2>\n\n\n\n\u4e58\u6cd5<\/h3>\n\n\n\n
\u542f\u53d1\uff1a<\/p>\n\n\n\n
\u590d\u6570\u4e58\u6cd5\u4e2d(a+bi)(c+di)=ac-bd+(bc+ad)i\u5305\u542b\u56db\u6b21\u4e58\u6cd5\uff0c\u4f46\u5b9e\u9645\u53ef\u4ee5\u901a\u8fc7\u8ba1\u7b97ac\u3001bd\u3001(a+b)(c+d)\uff0c\u56e0\u4e3abc+ad=(a+b)(c+d)-ac-bd\uff0c\u75314\u6b21\u51cf\u52303\u6b21\uff0c\u7531\u6b64\u53ef\u4ee5\u5e94\u7528\u5230\u5e38\u89c4\u4e58\u6cd5\u3002<\/p>\n\n\n\n
x=2n\/2<\/sup>xL<\/sub>+xR<\/sub>\uff1by=2n\/2<\/sup>yL<\/sub>+yR<\/sub>\uff1b<\/p>\n\n\n\nxy=2n<\/sup>xL<\/sub>yL<\/sub>+2n\/2<\/sup>(xL<\/sub>yR<\/sub>+xR<\/sub>yL<\/sub>)+xR<\/sub>yR<\/sub><\/p>\n\n\n\n\u590d\u6742\u5ea6\u5206\u6790\uff1aT(n)=4T(n\/2)+O(n)\uff0c4\u6b21n\/2\u4f4d\u4e58\u6cd5\uff0b3\u6b21n\u4f4d\u52a0\u6cd5\u3002O(n2<\/sup>)<\/p>\n\n\n\n\u7ee7\u7eed\u5316\u7b80\uff0c\u53ea\u9700\u8ba1\u7b97xL<\/sub>yL<\/sub>\u3001xR<\/sub>yR<\/sub>\u3001(xL<\/sub>+xR<\/sub>)(yL<\/sub>+yR<\/sub>)\uff0c<\/p>\n\n\n\n\u4fee\u6539\u540e\u7684\u590d\u6742\u5ea6\u4e3aT(n)=3T(n\/2)+O(n)\uff0c3\u6b21n\/2\u4f4d\u4e58\u6cd5\uff0b3\u6b21n\u4f4d\u52a0\u6cd5\u3002O(n1.59<\/sup>)<\/p>\n\n\n\nalgo:<\/strong><\/p>\n\n\n\nmultiply(x,y)\nif n=1 return xy;\nxL<\/sub>,xR<\/sub>=leftmost[n\/2],rightmost[n\/2] bits of x\nyL<\/sub>,yR<\/sub>=leftmost[n\/2],rightmost[n\/2] bits of y\n\nP1=multiply(xL<\/sub>,yL<\/sub>)\nP2=multiply(xR<\/sub>,yR<\/sub>)\nP3=multiply(xL<\/sub>+xR<\/sub>,yL<\/sub>+yR<\/sub>)\nreturn P1\u00d72n<\/sup>+(P3-P1-P2)\u00d72n\/2<\/sup>+P2<\/code><\/pre>\n\n\n\n\u590d\u6742\u5ea6\u8ba1\u7b97\uff1a<\/p>\n\n\n\n
\u9012\u5f52\u5c42\u6570\u4e3alog n\uff0c\u5728\u7b2ck\u5c42\u82b1\u8d39\u7684\u603b\u65f6\u95f4\u4e3a
<\/div><\/p>\n\n\n\n\n- k=0\u65f6\uff0c\u65f6\u95f4\u4e3aO(n)<\/li>\n\n\n\n
- k=log2<\/sub> n\u65f6\uff0c\u65f6\u95f4\u4e3a<\/div><\/li>\n\n\n\n
- \u5728\u9876\u5c42\u548c\u6700\u5e95\u5c42\u4e4b\u95f4\uff0c\u5de5\u4f5c\u8017\u65f6\u5448\u7b49\u6bd4\u6570\u5217\uff08\u51e0\u4f55\u7ea7\u6570\uff09\u589e\u957f\uff0c\u6bcf\u589e\u957f\u56e0\u5b50\u4e3a3\/2<\/li>\n\n\n\n
- \u65f6\u95f4\u590d\u6742\u5ea6\u7531\u5e95\u5c42\u51b3\u5b9a\uff0c\u4e3a<\/div><\/li>\n<\/ul>\n\n\n\n
\u9012\u63a8\u5f0f\u3001\u4e3b\u5b9a\u7406<\/h3>\n\n\n\n
\u5bf9\u4e8e\u5f0f\u5b50<\/p>\n\n\n\n
<\/div><\/p>\n\n\n\n\u6709<\/p>\n\n\n\n
<\/div><\/p>\n\n\n\nproof:<\/p>\n\n\n\n
\u6211\u4eec\u5728\u7b2ck\u5c42\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u53ef\u4ee5\u8868\u793a\u4e3a<\/p>\n\n\n\n
<\/div><\/p>\n\n\n\n\u603b\u65f6\u95f4T(n)\u662f\u4e0a\u5f0f\u5bf9k\u4ece0\u5230logb<\/sub>n\u6c42\u548c\uff0c\u56e0\u4e3a\u662f\u7b49\u6bd4\u6570\u5217\uff0c\u6240\u4ee5\u6bd4\u4f8b\u5c0f\u4e8e1\u53d6\u51b3\u4e8e\u7b2c\u4e00\u9879(\u5e38\u6570)\uff0c\u7b49\u4e8e1\u4e3a\u5bf9\u6570\uff0c\u5927\u4e8e\u53d6\u51b3\u4e8e\u6700\u9ad8\u6b21\u9879<\/p>\n\n\n\n\u5f52\u5e76\u6392\u5e8f\u3001\u9006\u5e8f\u5bf9<\/h3>\n\n\n\n\u5f52\u5e76\u6392\u5e8f<\/h4>\n\n\n\n
algo:<\/strong><\/p>\n\n\n\nfunction mergesort(a[1...n])\nif n>1:\n| return merge(mergesort(a[1...[n\/2]]),mergesort(a[[n\/2+1]...n]))\n| else return a\n\nfunction merge(x[1...k],y[1...l])\nif k=0:return y\nif l=0:return x\n...\u7ee7\u7eed\u9012\u5f52\u6216\u7528\u5faa\u73af<\/code><\/pre>\n\n\n\nmerge\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(k+l)\uff0cmergesort\u7684\u603b\u65f6\u95f4\u590d\u6742\u5ea6\u662fT(n)=2T(n\/2)+O(n)\uff0c\u6216O(n log n)<\/p>\n\n\n\n
\u8ba1\u7b97\u9006\u5e8f\u5bf9<\/h4>\n\n\n\n
\u60f3\u6cd5\uff1a<\/p>\n\n\n\n
\n- \u5c06\u6570\u7ec4\u5206\u4e3a\u5de6\u53f3\u4e24\u90e8\u5206<\/li>\n\n\n\n
- \u5206\u522b\u8ba1\u7b97\u4e24\u90e8\u5206\u4e2d\u7684\u9006\u5e8f\u5bf9<\/li>\n\n\n\n
- Combine\uff1a\u8ba1\u7b97\u6a2a\u8de8\u4e24\u4e2a\u90e8\u5206\u7684\u9006\u5e8f\u5bf9<\/li>\n<\/ul>\n\n\n\n
\u7b2c\u4e09\u6b65\u5f88\u96be\uff0c\u4f46\u5982\u679c\u5de6\u53f3\u4e24\u90e8\u5206\u6709\u5e8f\uff0c\u5c31\u53ef\u4ee5\u901a\u8fc7\u4e24\u4e2a\u6307\u9488\u5206\u522b\u79fb\u52a8\uff0c\u5feb\u901f\u8ba1\u7b97\u51fa\u9006\u5e8f\u3002\u4e0emergesort\u7ed3\u5408\u21d2Sort_and_Count<\/p>\n\n\n\n
Sort_and_Count(L)\ninput:List L;\noutput:\u9006\u5e8f\u5bf9\u53ca\u6392\u5e8f<\/em>\nif L.size()=1 then\n| return (0,L);\nend\nDivide L into A & B\n(rA<\/sub>,A)\u2190Sort_and_Count(A);\n(rB<\/sub>,B)\u2190Sort_and_Count(B);\n(rAB<\/sub>,L)\u2190Merge_and_Count(A,B);\nreturn (rA<\/sub>+rB<\/sub>+rAB<\/sub>,L);<\/code><\/pre>\n\n\n\n\u65f6\u95f4\u590d\u6742\u5ea6\u662fT(n)=2T(n\/2)+\u0398(n)\uff0c\u6216O(n log n)<\/p>\n\n\n\n
\u4e2d\u4f4d\u6570\/\u9009\u62e9\u95ee\u9898<\/h3>\n\n\n\n
\u9009\u62e9\u95ee\u9898\uff1a\u9009\u53d6\u6570\u7ec4\u4e2d\u7b2ck\u5c0f\u7684\u5143\u7d20\uff0c\u4e2d\u4f4d\u6570\u5373k=[n\/2]<\/p>\n\n\n\n
\u5b8c\u5168\u6392\u5e8f\u53ef\u4ee5\u5f97\u5230\uff0c\u590d\u6742\u5ea6O(n log n)\uff0c\u4f46\u505a\u4e86\u591a\u4f59\u7684\u5de5\u4f5c<\/p>\n\n\n\n
\u7b97\u6cd5\uff1a<\/p>\n\n\n\n
\n
![\" $n! \sim \sqrt{2\pi n}(\frac{n}{e})^{n}$ \"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-5a58e774e543a1bfd969337b7441ccfa_l3.png\" "\\"Rendered")
<\/div><\/p>\n\n\n\n![\"\begin{tabular}{lr}&11\quad13\\&5\quad26\\& delete \qual 2\quad52\\&1\ \,104\\\hline&143\end{tabular}\"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-1d5e86f6a47d74c7e9fc4aa1a2f4b908_l3.png\" "\\"Rendered")
<\/div><\/p>\n<\/div>\n<\/div>\n\n\n\n![\"$x\cdot y=\left\{\begin{array}{lr}& 2(x \cdot [y/ 2])\\& x+2(x \cdot [y/ 2])\\\end{array}\right.$\"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-0d5a73ba57c210a4ea1aec227472c81d_l3.png\" "\\"Rendered")
<\/div><\/p>\n\n\n\n![\"${\lim_{x \to +\infty}\frac{\pi (x)}{x/ln x}=1}$\"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-75d1f2c6cbef4aacb7bb7b15fd3c2506_l3.png\" "\\"Rendered")
<\/div><\/p>\n\n\n\n![\"${3^{k}\cdot O(\frac {n}{2^{k}})=(\frac{3}{2})^{k}\cdot O(n)}$\"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-549873fae6b46b4488cb0546a8f6efa9_l3.png\" "\\"Rendered")
<\/div><\/p>\n\n\n\n![\"${O(3^{\log_{2}{n}})=O(n^{\log_{2}{3}})}$\"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-192a1bdee9425811ec31fc7f4bcf9e5c_l3.png\" "\\"Rendered")
<\/div><\/li>\n\n\n\n![\"${O(n^{\log_{2}{3}})}=O(n^{1.59})}$\"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-411317efe901d449de5a6853bd536ddb_l3.png\" "\\"Rendered")
<\/div><\/li>\n<\/ul>\n\n\n\n![\"${T(n)=aT\left(\frac{n}{b}\right)+O(n^d)}$\"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-6e18475eb81efd05bc7fd227b2a40f3c_l3.png\" "\\"Rendered")
<\/div><\/p>\n\n\n\n![\"$T(n)=\left\{\begin{array}{lr}& O(n^{d})\\& O(n^{d}\log{n})\\& O({n^{\log_{b}{a}})}\\\end{array}\right.\begin{array}{lr}& d>\log_{b}{a}\\& d=\log_{b}{a}\\& d<\log_{b}{a}\\\end{array}$\"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-7dbde827a0c0239221ae30979abadf96_l3.png\" "\\"Rendered")
<\/div><\/p>\n\n\n\n![\"$a^k \times O(\frac{n}{b^k})^d=O(n^d)\times (\frac{a}{b^d})^k$\"](\"https:\/\/www.smzytyzg.tw.cn\/wp-content\/ql-cache\/quicklatex.com-78b83658be120dd0c8c2456f4df0d7ec_l3.png\" "\\"Rendered")
<\/div><\/p>\n\n\n\n