请问开平方有什么快的方法？

Mgccl

算$\pi$也可以... 还有...不需要算$\sqrt{n}$,算$\frac{1}{\sqrt{n}}$ 第二个快一点,但是还是O(M(n)),M(n)代表乘法的复杂度.

ssikkiss

只要你用定长数字 包括浮点 都会循环

定长数字当然会循环 但题意是计算开平方，只要你愿意，你想计算多长就计算多长（视待加密文件的长度而定） 计算机能够存储多长，计算出的数字都不会循环，当然虽然到后面很长的时候会算不动 [ 本帖最后由 ssikkiss 于 2008-6-29 05:11 编辑 ]

ssikkiss

$pi$

ssikkiss

算$pi$不行，因为大家都这样算，就没有随机性可言了。（随机性）。而算开方，没人知道我是用那个数字来开方的，我把100位后的才输出，正是可以加强这点；而把用户的初始密钥分为2分，计算2个数的开方，结果取他们的异或，这样，根本不可能从输出的密钥流算出这两个被开方的数来。就无法预测下密钥流中的下一个密钥。（不可预测性）。 感谢你提出的算$1/sqrt(n)$,确实是个不错的建议！

mathe

评价加密的算法可靠性不是仅仅靠周期长度来评价。一个好的加密算法是即使你公开算法和原文和密文，还是没办法得到密码的

无心人

搞100位不必要 最安全的加密是一次一密 保证明文不是纯文本的话 你用AES256 密码用目前的随机算法生成，然后你手工筛选 加密一块，换一个密码 或者随机更换，估计除非有人严刑逼供你 否则多快的机器也解不开 比你算法的简单

无心人

这样，你准备个防盗笔记本 记录1024个密码，都是32位，随机字符 字母数字各一半，大写小写各一半， 相邻是连续数字或者是连续字母的不超过2个连续 第一次用一个密码加密1024字节 然后第二密码加密2048字节 后面的密码依次加密加倍的密文 我想只要你笔记本不丢 没人能破解 即使有人侥幸破解一部分 也不可能还原文件

liangbch

从目前我所了解的知识来看，似乎开平方的算法都随结果的长度增加而快速增加，不管是牛顿法，弦切法，更不用提笔算法了。而且这种增加是差不多正比于结果的长度的平方的。

如果有速度很快的乘法支撑，开平方的复杂度应该介于O(n) 和O(n^2)之间，基本上正比于计算精度，甚至小于o(n)。例在本站这个帖子 http://bbs.emath.ac.cn/thread-143-1-3.html 中表明，在计算sqrt(2)是，当计算精度从10万位提高到100万位时，精度提高了10倍，计算时间的增加却小于10倍。

ssikkiss

谢谢楼上提供的信息！看来开平方的速度业不错！我准备实现一下这个方案了！ 回前几楼：所有流密码的目标都是向一次一密靠拢!我相信如果有真随机算法，就能实现一次一密

无心人

一次一密 代价很高 如果你要求绝对保密 而且不能承受泄密的代价 可以考虑 双方要同步约定密码