关于欧拉函数的一些记注

澹泊明志宁静致远。这几天一直在对欧拉函数比较在心,想了很久,觉得有必要给自己写点什么东西下来。

1.任意给定一个数,其欧拉阶关于比特长度是多项式的。计算欧拉阶似乎与整数分解存在某种联系。

2.n阶矩阵欧拉函数与传统欧拉函数也有类似的结果,比如积性、基于标准分解式的计算公式。

3.关于欧拉函数的方幂估计式退化为一般欧拉函数的估计,考虑估计范围的大小。可以参考华罗庚的《数学导引》和谭谊家(福州大学)的两个估计式。

4.关于一阶欧拉函数和二阶欧拉函数的比值求和函数的渐进估计为x/logloglogx。这类分析的结果似乎对于数值计算缺乏操作上的可行性帮助。

5.吴传坤在1994年证明了对于rsa中的n,计算欧拉函数等价于寻找某个整数t,其欧拉函数值等于48t/(n-1)。可以考虑研究t的特征。

6.吴传坤在1992年给对了对于rsa的一种攻击,其算法复杂度本质上是指数的,但是从实际操作来看,可以通过对两个素数比值的精度估计降低这个计算难度,还需要做进一步的估计。同时提出gcd(p-1,q-1)应该比较小,也就是说phi(n)应该包含小的素因子。如此一来,是否只需要考虑二阶欧拉函数就可以了?

7.对于任意的正整数k,存在m,使得phi(x)=m这个欧拉函数方程恰有k个解。

Dickson (2005, p. 137) states that the conjecture was proved by Carmichael (1907), who also developed a method of finding the solution (Carmichael 1909). The result also appears as in exercise in Carmichael (1914). However, Carmichael (1922) subsequently discovered an error in the proof, and the conjecture currently remains open.

8.欧拉函数的逆的计算问题,结果是可以多项式时间计算出来,只是在某些情况下结果输出可能是指数复杂度的,前提是n的分解已经给出。然而,要判断一个数是否有欧拉函数的逆,可以说是一个NP问题。
参考这里:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.7209

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注