恆等式的啟示

我們處理大數的素因子分解 (Prime Factorization) 時,當然可以使用傳統的試除法 (Trial Division) 來作分解,但這會用上很多的時間。(詳可參考另文《素數判別法》)  現在恆等式 (Identity) 給 了我的啟示,可否助我們減省計算的時間呢?諸位看一看便明白。

 

勒讓德符號

從平方差談起

從平方和談起

歐利費奧利分解法