>>70
剰余の順番に関しては確率がこんなんだからやで
3 / 5 = 0.600000
4 / 7 = 0.571429
4 / 9 = 0.444444
7 / 13 = 0.538462
9 / 17 = 0.529412
49 / 97 = 0.505155

テーブルは9, 97, 17, 13, 7, 5の物で良いんやで？
多倍長整数の剰余より32bit整数/64bit整数の剰余のほうが計算量が少ないから、
(32bitの場合) 2^24-1で剰余を取ったものに対して9, 17, 13, 7, 5の剰余で平方数かどうかを調べる
(64bitの場合) 2^48-1で剰余を取ったものに対して9, 97, 17, 13, 7, 5の剰余で平方数かどうかを調べる

なしてこんなことができるかってーと、
2^24-1(=16777215)の因数に5, 7, 9, 13, 17が、2^48-1(=281474976710655)の因数に5, 7, 9, 13, 17, 97含まれているからやで