能力值：
( LV2，RANK：10 )
|
-
-
2 楼
学习学习！！楼主辛苦了。
|
能力值：
( LV4，RANK：50 )
|
-
-
3 楼
O(n^0.5)
除了穷举，随便一个算法都比这个快
广义筛法约为LN[1/3，c]
|
能力值：
( LV2，RANK：10 )
|
-
-
4 楼
看了看,算是一种思路吧,不过算n的欧拉数的时间复杂度比目前最优的筛法要大不少...
这是国内人独创的? 感觉以前怎么见过..
|
能力值：
( LV2，RANK：10 )
|
-
-
5 楼
关于一个概念性的东西想谈谈我的看法：
lim f(n)/n < ....
f(n)表示欧拉函数，(因欧拉函数的那个字符不方便输入）
其实这个数列是不收敛的，取其子列p^1,p^2,...p^m...(p>=2)，显然有f(n)/n - 1=-1/p为一个常数。由柯西收敛准则可以知道这个数列f(n)/n是发散的。或者应该说1是其中的一个聚点吧。好奇问问有没有人专门去研究过f(n)/n呢？也许前人已经有过一些不错的结果了，期待ing
|
能力值：
( LV12，RANK：779 )
|
-
-
6 楼
计算欧拉函数的代价，等价于因子分解，这些都是已有的结论。这种文章也写出来凑数。可见浮躁。
|
能力值：
( LV2，RANK：10 )
|
-
-
7 楼
确实有所听闻，但是一直没有找到有关的文章证明，可否提供一些线索呢？
另外，我觉得“等价”是一个很严格的概念，如果前提假设不一样，就不一定等价了。
如果有一个欧拉函数的计算函数了，请问如何分解因子？我简单想过一下这个问题。
假设n的所有素因子都是一次的，n=p1*p2*...*pm。
那么，欧拉函数f(n)=(p1-1)*(p2-1)*...*(pm-1)。假设gcd(n,f(n))=1.
然后呢？我想到这个就做不下去了，怎么根据f(n)和n算出所有的p1,p2,...pm？
希望有人可以指点一下。
|
能力值：
( LV2，RANK：10 )
|
-
-
8 楼
我是菜鸟，看了2页完全不懂！
|
能力值：
( LV12，RANK：779 )
|
-
-
9 楼
(1)已经因子分解，可计算欧拉函数。
(2)已知欧拉函数，有非常简单的概率算法可以求得非平凡因子。
这些来自以前看过的论文，这些算法也早就是已知的。并不是新的东西。
大意如下：
通过求解 wj^2 = 1 (mod n)，gcd(wj-1, n) ，对于RSA数来说，其结果是一定的。对于多因子，可以类推。
因为欧拉函数必定是一个偶数，所以通过不断除以2，
得到phi=r * 2^s，
令a = rand(1, n), a为随机数。
w0 = a^r (mod n),
for ( j = 0 ; j < s ; j++)
必然有某个wj ^2 = 1 mod (n),
也就是
w1=w0^2(mod n),
w2 = w1^2(mod n), ...
那么必然，当 wj^2 = 1 (mod n) , 注意欧拉函数的性质， gcd(a,N) = 0, 必然 a^phi = 1 (mod N)。
gcd(wj-1,n) = 1
gcd(wj-1,n) = n
gcd(wj-1,n) = p
gcd(wj-1,n) = q
有1/2概率求出一个非平凡因子，选取不同的a， 一般2次即可。
这也是为什么，知道任何一对 E，D （即得到k*phi），就能分解N的原因。
具体操作请看RDLP，代码是3年前写的。v1.01 25th Aug. 2007
我在三年前写RDLP的时候， 几乎翻阅了我能找到的所有与RSA相关的paper，国外的或者国内的。
对国内的期刊，只有2个字“失望”。再加上2个字，“必然失望”。
如果你有时间，你可以发现，现在还有一遍一遍炒剩饭的paper出来。
好像蒋春晖脑袋一拍，就能思考出大数分解的方法。这样的研究态度，与民科何异。
|
能力值：
( LV2，RANK：10 )
|
-
-
10 楼
多谢指点，在<Cryptography theory and practice>P204中找到了这个算法。
|
|
|
|
