作者flere (人间失格)
站内Prob_Solve
标题[问题] 快速质因数分解的方法
时间Tue Feb 7 14:24:56 2012
想请问一下
如果我有一个数N想质因数分解,N<10^14
藉此得到N的因数可能个数
所以我先建质数表到10^7
发现约有10^6个质数
这样去做质因数分解的话
如果有一个质数非常靠近10^14
我就每次都必须把10^6个质数全部test完才可以结束
如果资料里有很多这种数的话处理时间肯定非常慢
请问有比较快的质因数分解方法,或是可以快速判断这个数就是质数的方法吗??
毕竟表我没办法建到10^14这麽大> <
谢谢: )
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.200.13
1F：→ freef1y3:没有快速质因数分解方法，不过好像有快速判断质数的方法 02/07 15:34
2F：推 suhorng:Pollard-rho algo 02/07 16:02
3F：推 tjjh89017:快速判断质数好像是用随机策略吧 02/07 16:03
4F：→ suhorng:常见的那种叫 Miller-Rabin 02/07 16:04
5F：→ flere:谢谢!!!! 02/07 16:16
6F：推 DJWS:质因数分解的时间复杂度目前还不知道是，也没有P-time演算法 02/07 20:12
7F：→ DJWS:判断质数则是有P-time演算法，叫做AKS Algorithm 02/07 20:12
8F：→ DJWS:AKS是2002年才发明的第一个P-time演算法，在那之前大多是用 02/07 20:14
9F：→ DJWS:前面几位推文所说的方法，虽然都是P-time但不保证答案正确 02/07 20:15
10F：→ DJWS:(第一句补充) 是属於哪一类， 02/07 20:16
11F：→ kdjf:如果被你找到的话, RSA就不用玩了啊 （天下大乱!!! 02/07 22:22
原来如此XDDD
因为写了一题质因数分解的
但是TLE到现在OAO所以才想说是不是有比较快的办法: P
感谢大家: )
※ 编辑: flere 来自: 140.114.200.13 (02/07 23:28)
12F：→ EdisonX:放 code 上来讨论 ? 02/08 01:39
13F：→ flere:就在刚刚加了cut後终於过了: ) 02/08 03:17
14F：→ suhorng:该不会是ZeroJudge上的题目吧....XD 记得那边有一系列的 02/08 08:09
15F：→ flere:是阿XDD不过写完也都会丢去uva就是了XD 02/08 13:18
16F：→ flere:就是写到uva 10290一直不过,zero的是过了,可是uva要开比较 02/08 13:19
17F：→ flere:小的质数表才会过> < 02/08 13:20
18F：→ bleed1979:我有写信给uva说10^6质数表也可以过，不过似乎没改善。 02/08 19:32
因为我见到3e7,只能在zerojudge上过而已
而且还跑了2.多秒
在uva也想开到3e7有什麽好方法吗??
基本上我都是写
for(i=2~N)
if(i is prime)
for(j=2*i~N,j+=i)
j不是质数
很普通的去建表而已OAO
※ 编辑: flere 来自: 140.114.200.13 (02/08 20:02)
19F：→ firejox:bit array? 02/08 20:10
20F：→ ilway25:上学期修的课有搞不清楚状况的助教出分解RSA-100的作业... 02/10 13:24
21F：→ flere:那是啥??怎麽状况感觉很好笑XDD 02/10 16:30
22F：推 suhorng:分解一个100位(十进位)的数字... 02/10 18:12
23F：→ kdjf:如果那不是两(几)个大质数的相乘, 就不是大问题啊XD 02/10 19:40
24F：→ flere:SOGA~ 02/10 20:52
25F：→ suhorng:可是既然叫RSA不就该恰好是两个质数的乘积? 02/10 22:18