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

ssikkiss

因为我的水平有限，对开平方涉及的数学原理不甚了解，所以有此一问。
从目前我所了解的知识来看，似乎开平方的算法都随结果的长度增加而快速增加，不管是牛顿法，弦切法，更不用提笔算法了。而且这种增加是差不多正比于结果的长度的平方的。
我的不切实际的希望是：
计算出小数点后N位，花N个单位时间；计算到小数点后N＋1位，花N＋1个单位时间。

最初我考虑这个问题，是想用无理数来做伪随机数，毕竟无理数的性质完美的符合了真随机数的标准！
2年前我把这个问题贴在“安全矩阵”（一个密码学网站），在那里得到了否定的的意见。的确从基本数学原理看是不可能做到的。今天再次看到那个帖子，干脆就再贴在这里看看，听听更多的意见。
如果这个问题能解决或半解决（半解决就是象乘法那样，虽不能把时间从N×N降到N，但能降到logN）,就能用来产生优良的随机数，进而可以实现以下算法：

我想实现一个流密码方案
1.用户输入一个初始密钥,我们把它从中间切断,得到2个子密钥A,B

2.把子密钥A转化成一个64bit数字N1,把子密钥B转化成一个64bit的数字N2

3.计算M1=(N1 * N1)+1,M2=(N2*N2)+1 ；（这一步，使得M1和M2的开方运算能得到无理数。否则有可能算出根号4＝2这样的结果）

4.开始对M1和M2分别开平方,把所得结果看做2进制,然后每32bit切断,就得到2个32bit的整数流,可以把这2个整数流记为数组K1()和K2().

5.对数组的每个元素i,计算K(i)=K1(i)  XOR  K2(i) ；（这一步，使得分析者不能通过密钥流K()还原出K1()和K2(),也就无法推知M1和M2，这样，分析者无法预测下一个K(i)）

6.对第4,5步所得结果,舍弃前100个值,从第101个开始对外输出,用来当做流密码加密文件；（从第101个开始才输出，进一步使得M1和M2无法预测）


这就是我当时设想的大致方案,
现在看来,计算开平方确实是一个难以逾越的障碍,使得它的速度会非常慢,也就没什么实际意义了

[ 本帖最后由 ssikkiss 于 2008-6-29 05:17 编辑 ]

无心人

开平方只能比乘法慢
永远速度不可能超越同级别的乘法

gxqcn

加密分对称加密和非对称加密两类算法。
楼主设想的显然不是非对称加密，
而对称加密算法对速度要求很高，才有实用价值，比如RC4。

楼主的算法是不现实的，无论是加密端还是解密端都消耗不起，
因为随着数据流的流逝，密码的计算越来越慢，无法形成稳定的速度，
再快的机器，再大的存储空间都会被这个算法给折腾死的。

mathe

现代密码学已经非常成熟了，有很多现成的方法可以用来评估一种加密算法是否可靠。不过经验教训是随便拍脑袋设计出来的看是复杂的变换往往是不可靠的，熵漏往往挺高的

无心人

呵呵

如果自己用
可以采取复杂函数方法
但要注意加解密存在算法可逆和程序可逆的不同
但密码加密的块不能太大
原因也是影响速度

ssikkiss

是啊，我就是觉得它太慢，所以才问，是否有快速的开平方方法。
其实开平方只是这里的一个例子，因为我想实现“无限不循环”，所以用了开平方。当然其代价就是计算的时候时间和空间的需求都会越来越多
也可以用其他的方法，但绝对会有周期，不可能“无限不循环”

ssikkiss

因为开平方是我知道的第一个得到无理数的方法，要是有其他能得到无理数，而计算起来又快的方法多好啊

无心人

你完全可以把4个字节的双字按一定顺序错乱
再平方后取中间四个字节

ssikkiss

这个是书里说过地，而且是会循环的

无心人

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