【問題】騙されないFermatテストの変形の一つは、Miller-Rabinテスト（Miller-Rabin test）（Miller 1976: Rabin 1980）という。 これは n が素数であり、a を n より小さい任意の整数とすると、a の (n-1) 乗は n を法として 1 と合同であるという、Fermat…

【問題】 脚注47のCarmichael数が本当にFermatテストを騙すことを示せ。 それには整数 n をとり、a 【解答】 まずはその脚注47をご紹介。 47 Fermat テストを騙す数は、Carmichael数（Carmichael numbers）といい、非常に稀だということ以外はよく分からない…

【問題】 Louis Reasoner は問題 1.24 がなかなかうまくいかなかった。彼のfast-prime?よりずっと遅いようであった。 Louis は友人の Eva Lu Ator に助けを求めた。 Louis のプログラムを見ていると、square を呼びだす代わりに乗算を陽に使うように変わって…

お仕事が忙し過ぎて体がもたん。。やる気が。。 【問題】 Alyssa P. Hacker は expmod を書くのに多くの余分なことをやったと不満で、結局ベキ乗計算法は知っているから、 (define (expmod base exp m) (remainder (fast-expt base exp) m)) と単純に書ける…