作者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