数据结构-给定一个正整数,求它的除数的个数

数据结构-给定一个正整数,求它的除数的个数

浮生未歇 发布于 2017-02-07 字数 145 浏览 1302 回复 5

在密码学中,求出一个数的因数是一个很重要的问题,通常是很难的,有时你都不知道能不能分解。有没有一个办法能首先判断出一个正整数的除数的个数?

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

偏爱自由 2017-10-05 5 楼

我觉得没有"首先"的方法,毕竟这个问题比判断一个数是不是质数有更多的信息量.

归属感 2017-08-24 4 楼

/*一共循环temp的根号次*/
for(int i=1;i <= Math.sqrt(temp);i++){
/*如果能被整除就加1*/
if(temp % i == 0)
count++;
}
count *= 2;//因为被开根号,所以根号后面的数字也有因子和前面的配对
if(temp % Math.sqrt(temp) == 0) //当数字正好被开根号,两个因子相同时
count--; //就减去一个

开根号是算因子次数最少的

偏爱自由 2017-08-24 3 楼

有个减少循环次数的初步想法(数A):
1、从A/2处开始循环即可;
2、将所有可用的都保存起来,每次会保存两个。24/8,可以保存8和3,下次就可以不计算3。
3、遇到类似2的次方的可用数据,那可以将2—2的n-1次方的数据都保存。如32可用,则16、8、4、2都是可用的,可以保存8个数。

清晨说ぺ晚安 2017-08-04 2 楼

对比较小的数来说方法是首先做质因数分解,然后把每个质因数指数系数+1再相乘,比如
28 = 2^2 * 7,总共有3 * 2 = 6个数能整除它,包括它自己和1:1 2 4 7 14 28
从排列组合原理上很好解释这个方法。

但是你都知道对于密码学意义上的“数”来说分解有多困难了,这个方法当然不行。

只有一个方法粗判断这个数是不是一个质数,运用费马小定理的(伪)逆定理:
费马小定理:
a ^ (p-1) = 1 (mod p)
对于任意a < p都成立。
比如3^4 = 81 = 1 (mod 5)
这个证明到处都有
而如果对于某个p和a(a ≠ 1),有
a ^ (p-1) = 1 (mod p)
这时候p不一定是质数,对于某个a来说的确存在一些p使得p不是质数却也满足这个等式。但是这些数非常少,比质数少得多(整数N是质数的概率大约是1/lnN),所以密码学上通常用几个不同的、随机的a来进行判断,如果都满足这个等式,那就认为p是个质数。因此要找出一个质数其实不是很难。RSA算法首先需要找出两个大质数,就是用的这种方法。

但是一般意义上分解大数仍然是非常困难的。

清晨说ぺ晚安 2017-05-02 1 楼

这个问题好解决吧,除了1和本身外,循环除下1到自身之间的每个整数,算下有几个除得尽的。
至于你的密码学中非对称加密的公、私钥(p、n,q、n)中n分解问题,是可以计算出来的。攻击方法有:穷举攻击、数学攻击、计时攻击、选择密文攻击,四种手段。
求正数除数的个数和分解一个非常大的整数n为两个素数,不相同。
对于RSA密钥长度为128字节的,我们安全老大已经可以分布式计算算出对应公钥的私钥,只需30多台机器和20多天。
我在怀疑现在美国国防部还是否在用RSA或者是仅仅靠增加密钥长度来维持。毕竟DES、AES、RSA只是国防部使用时间过期后,公开给大家使用的算法。