読者です 読者をやめる 読者になる 読者になる

2^n - 1 を素因数分解した結果一覧

雑記

http://melpon.org/wandbox/permlink/UPjHWBam24a75P9U

2^1-1 ,3
2^2-1 ,7
2^3-1 ,3,5
2^4-1 ,31
2^5-1 ,3,3,7
2^6-1 ,127
2^7-1 ,3,5,17
2^8-1 ,7,73
2^9-1 ,3,11,31
2^10-1 ,23,89
2^11-1 ,3,3,5,7,13
2^12-1 ,8191
2^13-1 ,3,43,127
2^14-1 ,7,31,151
2^15-1 ,3,5,17,257
2^16-1 ,131071
2^17-1 ,3,3,3,7,19,73
2^18-1 ,524287
2^19-1 ,3,5,5,11,31,41
2^20-1 ,7,7,127,337
2^21-1 ,3,23,89,683
2^22-1 ,47,178481
2^23-1 ,3,3,5,7,13,17,241
2^24-1 ,31,601,1801
2^25-1 ,3,2731,8191
2^26-1 ,7,73,262657
2^27-1 ,3,5,29,43,113,127
2^28-1 ,233,1103,2089
2^29-1 ,3,3,7,11,31,151,331
2^30-1 ,2147483647
2^31-1 ,3,5,17,257,65537
2^32-1 ,7,23,89,599479
2^33-1 ,3,43691,131071
2^34-1 ,31,71,127,122921
2^35-1 ,3,3,3,5,7,13,19,37,73,109
2^36-1 ,223,616318177
2^37-1 ,3,174763,524287
2^38-1 ,7,79,8191,121369
2^39-1 ,3,5,5,11,17,31,41,61681
2^40-1 ,13367,164511353
2^41-1 ,3,3,7,7,43,127,337,5419
2^42-1 ,431,9719,2099863
2^43-1 ,3,5,23,89,397,683,2113
2^44-1 ,7,31,73,151,631,23311
2^45-1 ,3,47,178481,2796203
2^46-1 ,2351,4513,13264529
2^47-1 ,3,3,5,7,13,17,97,241,257,673

mod [2^n - 1] は(比較的)高速に計算することができる
mod [2^n + 1]も何となく高速に計算できそうな気がするんだけれどとくに方法が思いつかない