{"version":"https://jsonfeed.org/version/1.1","title":"苏迟但到的主页","home_page_url":"https://kexohproject.pages.dev","feed_url":"https://kexohproject.pages.dev/json/","description":"<p>你好，欢迎访问个人主页！</p><p>擅长密码学，安全分析，数字水印等技术。</p><p>你可以联系我通过:findmykexin@gmail.com或者知乎私信。</p><p>我的知乎链接：<a href=\"https://www.zhihu.com/people/su-chi-dan-dao\" rel=\"noopener noreferrer\" target=\"_blank\">苏迟但到 - 知乎 (zhihu.com)</a></p><p>我的github链接：<a href=\"https://github.com/kexinoh\" rel=\"noopener noreferrer\" target=\"_blank\">kexinoh</a></p>","icon":"https://kexohcdn.gptapi.cyou/kexohproject/production/images/channel-2e54d141ee195646ca12a9d16507a908.jpg","favicon":"https://kexohcdn.gptapi.cyou/kexohproject/production/images/favicon-340a2925d02a0386f3b954a032834917.jpg","authors":[{"name":"苏迟但到"}],"language":"zh-cn","items":[{"id":"R6LZkcy7Njq","title":"以m比特为密钥的RSA加密和解密n比特长的数据的时间复杂度分别为多少？","content_html":"<p data-pid=\"-QhHCzJK\">期望时间复杂度计算为：</p><p data-pid=\"stZG0eLc\"><img src=\"https://www.zhihu.com/equation?tex=f%28n%2Cm%29%3D%5Bn%2Fm%5D%2A%28%5Cfrac%7Bm%7D%7B2%7D%2Af%28m%2C%2A%29%2Bm%2Af%28m%2C%2A%29%29\" alt=\"f(n,m)=[n/m]*(\\frac{m}{2}*f(m,*)+m*f(m,*))\" eeimg=\"1\"/> </p><p data-pid=\"GpooLoqI\">其中 <img src=\"https://www.zhihu.com/equation?tex=f%28m%2C%2A%29\" alt=\"f(m,*)\" eeimg=\"1\"/> 指对m比特的进行相乘的复杂度。</p><blockquote data-pid=\"TwgfFGU_\">在计算机进行乘法计算的时候，传统的计算方法采用了类似竖式计算的方法——正如我们在小学课堂里面所学到的那样，因此时间复杂度是O(n ^ 2)。在进行大数（比如说数字位数超过2048）乘法计算的时候，目前的做法是Schönhage–Strassen算法，该算法利用快速傅里叶变换，将算法的复杂度降到O(n log n log log n)。<br/><br/>最近，Harvey 和Van Der Hoeven 在HAL贴出了两人合著的新论文“Integer<a href=\"https://www.zhihu.com/search?q=multiplication%20in%20time&amp;search_source=Entity&amp;hybrid_search_source=Entity&amp;hybrid_search_extra=%7B%22sourceType%22%3A%22article%22%2C%22sourceId%22%3A%2262143130%22%7D\" class=\"internal\">multiplication in time</a>O(n log n)”，宣称已经发现时间复杂度为O(n log n)的整数乘法算法。<br/>作者：留德华叫兽<br/>链接：<a href=\"https://zhuanlan.zhihu.com/p/62143130\" class=\"internal\"><span class=\"invisible\">https://</span><span class=\"visible\">zhuanlan.zhihu.com/p/62</span><span class=\"invisible\">143130</span><span class=\"ellipsis\"></span></a><br/>来源：知乎<br/>著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。</blockquote><p data-pid=\"s_t5YnaT\">在通常意义下，为 <img src=\"https://www.zhihu.com/equation?tex=f%28n%2Cm%29%3D%5Bn%2Fm%5D%2A%281.5%2Am%5E3%29%3DO%28m%5E2%29\" alt=\"f(n,m)=[n/m]*(1.5*m^3)=O(m^2)\" eeimg=\"1\"/> </p><p data-pid=\"1L9f1p16\">在极限下，为 <img src=\"https://www.zhihu.com/equation?tex=f%28n%2Cm%29%3D%5Bn%2Fm%5D%2A%281.5%2Am%5E2+%5Clog+m%29%3DO%28n%2Am%5Clog+m%29\" alt=\"f(n,m)=[n/m]*(1.5*m^2 \\log m)=O(n*m\\log m)\" eeimg=\"1\"/> </p><p data-pid=\"sTT7WrZY\">空间复杂度包含：</p><p data-pid=\"hRlmxxUF\"><img src=\"https://www.zhihu.com/equation?tex=f%28n%2Cm%29%3Dn%2Bk%2Am%3DO%28m%2Bn%29\" alt=\"f(n,m)=n+k*m=O(m+n)\" eeimg=\"1\"/> </p><p data-pid=\"Z-Y6XJTS\">其中k是常数项，具体取决于算法。</p><p></p>","content_text":"期望时间复杂度计算为：\n\nf(n,m)=[n/m]*(\\frac{m}{2}*f(m,*)+m*f(m,*))\n[https://www.zhihu.com/equation?tex=f%28n%2Cm%29%3D%5Bn%2Fm%5D%2A%28%5Cfrac%7Bm%7D%7B2%7D%2Af%28m%2C%2A%29%2Bm%2Af%28m%2C%2A%29%29]\n\n其中 f(m,*) [https://www.zhihu.com/equation?tex=f%28m%2C%2A%29] 指对m比特的进行相乘的复杂度。\n\n> 在计算机进行乘法计算的时候，传统的计算方法采用了类似竖式计算的方法——正如我们在小学课堂里面所学到的那样，因此时间复杂度是O(n ^\n> 2)。在进行大数（比如说数字位数超过2048）乘法计算的时候，目前的做法是Schönhage–Strassen算法，该算法利用快速傅里叶变换，将算法的复杂度降到O(n\n> log n log log n)。\n> \n> 最近，Harvey 和Van Der Hoeven 在HAL贴出了两人合著的新论文“Integermultiplication in timeO(n log\n> n)”，宣称已经发现时间复杂度为O(n log n)的整数乘法算法。\n> 作者：留德华叫兽\n> 链接：https://zhuanlan.zhihu.com/p/62143130\n> 来源：知乎\n> 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n\n在通常意义下，为 f(n,m)=[n/m]*(1.5*m^3)=O(m^2)\n[https://www.zhihu.com/equation?tex=f%28n%2Cm%29%3D%5Bn%2Fm%5D%2A%281.5%2Am%5E3%29%3DO%28m%5E2%29]\n\n在极限下，为 f(n,m)=[n/m]*(1.5*m^2 \\log m)=O(n*m\\log m)\n[https://www.zhihu.com/equation?tex=f%28n%2Cm%29%3D%5Bn%2Fm%5D%2A%281.5%2Am%5E2+%5Clog+m%29%3DO%28n%2Am%5Clog+m%29]\n\n空间复杂度包含：\n\nf(n,m)=n+k*m=O(m+n)\n[https://www.zhihu.com/equation?tex=f%28n%2Cm%29%3Dn%2Bk%2Am%3DO%28m%2Bn%29]\n\n其中k是常数项，具体取决于算法。\n\n","date_published":"2023-09-30T09:05:23.000Z","_microfeed":{"web_url":"https://kexohproject.pages.dev/i/mrsan-R6LZkcy7Njq/","json_url":"https://kexohproject.pages.dev/i/R6LZkcy7Njq/json/","rss_url":"https://kexohproject.pages.dev/i/R6LZkcy7Njq/rss/","guid":"R6LZkcy7Njq","status":"published","itunes:title":"New Article Title for iTunes","date_published_short":"Sat Sep 30 2023","date_published_ms":1696064723000}}],"_microfeed":{"microfeed_version":"0.1.2","base_url":"https://kexohproject.pages.dev","categories":[{"name":"Education","categories":[{"name":"Language Learning"}]},{"name":"Technology"}],"subscribe_methods":[{"name":"RSS","type":"rss","url":"https://kexohproject.pages.dev/rss/","image":"https://kexohproject.pages.dev/assets/brands/subscribe/rss.png","enabled":true,"editable":false,"id":"4KlfbtkEfzy"},{"name":"JSON","type":"json","url":"https://kexohproject.pages.dev/json/","image":"https://kexohproject.pages.dev/assets/brands/subscribe/json.png","enabled":true,"editable":false,"id":"DVFm7TYiNSq"}],"description_text":"你好，欢迎访问个人主页！\n\n擅长密码学，安全分析，数字水印等技术。\n\n你可以联系我通过:findmykexin@gmail.com或者知乎私信。\n\n我的知乎链接：苏迟但到 - 知乎 (zhihu.com)\n\n我的github链接：kexinoh","copyright":"©2024","itunes:type":"episodic","items_sort_order":"newest_first"}}