2^64内基于米勒罗宾素性测试的素性证明算法

无心人

贴一些相关数据，
假设ψn表示能通过前n个素数为基的强伪素数检验的最小合数
ψ1 = 2047 = 23 * 89
ψ2 = 1373653 = 829 * 1657
ψ3 = 25326001 = 2251 * 11251
ψ4 = 32150 31751 = 151 * 751 * 28351
ψ5 = 215 23028 98747 = 6763 * 10627 * 29947
ψ6 = 347 47496 60383 = 1303 * 16927 * 157543
ψ7 = ψ8 = 34155 00717 28321 = 10670053 * 32010157
ψ9 = ψ10 = ψ11 = 3825 12305 65464 13051 = 149491 * 747451 * 34233211
ψ12 = 3186 65857 83403 11511 67461  = 399165290221 *  798330580441
ψ13 = 33170 44064 67988 73859 61981 = 1287836182261 * 2575672364521

即理论上，最少12个MR测试才能证明2^64以内所有素数