找回密码
 欢迎注册
楼主: ssikkiss

[求助] 请问开平方有什么快的方法?

[复制链接]
发表于 2008-6-29 03:01:19 | 显示全部楼层
算$\pi$也可以...
还有...不需要算$\sqrt{n}$,算$\frac{1}{\sqrt{n}}$
第二个快一点,但是还是O(M(n)),M(n)代表乘法的复杂度.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-29 04:45:19 | 显示全部楼层
只要你用定长数字
包括浮点
都会循环

定长数字当然会循环
但题意是计算开平方,只要你愿意,你想计算多长就计算多长(视待加密文件的长度而定)
计算机能够存储多长,计算出的数字都不会循环,当然虽然到后面很长的时候会算不动

[ 本帖最后由 ssikkiss 于 2008-6-29 05:11 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-29 04:52:26 | 显示全部楼层
$pi$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-29 04:59:59 | 显示全部楼层

回复 11# Mgccl 的帖子

算$pi$不行,因为大家都这样算,就没有随机性可言了。(随机性)。而算开方,没人知道我是用那个数字来开方的,我把100位后的才输出,正是可以加强这点;而把用户的初始密钥分为2分,计算2个数的开方,结果取他们的异或,这样,根本不可能从输出的密钥流算出这两个被开方的数来。就无法预测下密钥流中的下一个密钥。(不可预测性)。
感谢你提出的算$1/sqrt(n)$,确实是个不错的建议!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-29 05:54:57 | 显示全部楼层
评价加密的算法可靠性不是仅仅靠周期长度来评价。一个好的加密算法是即使你公开算法和原文和密文,还是没办法得到密码的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-29 10:10:48 | 显示全部楼层
搞100位不必要
最安全的加密是一次一密
保证明文不是纯文本的话
你用AES256
密码用目前的随机算法生成,然后你手工筛选
加密一块,换一个密码
或者随机更换,估计除非有人严刑逼供你
否则多快的机器也解不开
比你算法的简单
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-29 10:15:30 | 显示全部楼层
这样,你准备个防盗笔记本
记录1024个密码,都是32位,随机字符
字母数字各一半,大写小写各一半,
相邻是连续数字或者是连续字母的不超过2个连续
第一次用一个密码加密1024字节
然后第二密码加密2048字节
后面的密码依次加密加倍的密文

我想只要你笔记本不丢
没人能破解
即使有人侥幸破解一部分
也不可能还原文件
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-29 13:47:12 | 显示全部楼层
从目前我所了解的知识来看,似乎开平方的算法都随结果的长度增加而快速增加,不管是牛顿法,弦切法,更不用提笔算法了。而且这种增加是差不多正比于结果的长度的平方的。

   如果有速度很快的乘法支撑,开平方的复杂度应该介于O(n) 和O(n^2)之间,基本上正比于计算精度,甚至小于o(n)。例在本站这个帖子 http://bbs.emath.ac.cn/thread-143-1-3.html 中表明,在计算sqrt(2)是,当计算精度从10万位提高到100万位时,精度提高了10倍,计算时间的增加却小于10倍。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-29 15:50:19 | 显示全部楼层
谢谢楼上提供的信息!看来开平方的速度业不错!我准备实现一下这个方案了!
回前几楼:所有流密码的目标都是向一次一密靠拢!我相信如果有真随机算法,就能实现一次一密
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-29 16:27:02 | 显示全部楼层
一次一密
代价很高
如果你要求绝对保密
而且不能承受泄密的代价
可以考虑

双方要同步约定密码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 01:55 , Processed in 0.050993 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表