最初の数をテストするのに、x として任意に 17 を選んでも良いでしょう。
1: 17 mod 811749613 2: 17 mod 811749613 1: 533694123 mod 811749613
. 811749612 .
.
17 M 811749613 RET 811749612 ^
533694123 は 1 とは(ずいぶん)違うので、811749613 は素数ではありません。
上記のように数をテストするのはぎこちなくて不便です。 これを避けるにはいろいろ方法があって、代数的入力はその 1つです。 実は、ベクトルのマッピング操作を使うといくつかのテストを一度に実施できます。 2番目の数は、この方法でテストしてみましょう。
2: [17, 42, 100000] 1: [1 mod 15485863, 1 mod ... ]
1: 15485863 .
.
[17 42 100000] 15485863 RET V M ' ($$ mod $)^($-1) RET
結果は 3つとも 1 (modulo n) ですから、 15485863 が素数である可能性は非常に高いです。 (実は、この数は 100万番目の素数です。)
関数 `($$^($-1)) mod $' や `$$^($-1) % $' は整数演算でべき乗を計算してしまうので、絶望的に非効率的であることを知っておいてください。
Calc には k p コマンドがあって素数テストを行います。
このコマンドは、小さな数に対しては厳密なテストを行い、
大きな数に対してはここで使った Fermat テストの変形を使います。
k p を繰返し使うことによって、
大きな整数が素数であることを必要な確度で証明できます。
(訳注: 判定結果と一緒に誤判定の確率も表示される。)
Go to the first, previous, next, last section, table of contents.
利用度数