親記事 / 返信無し
□投稿者/ yangmask 一般人(1回)-(2019/11/07(Thu) 15:45:37)
| はじめまして。yangmask(ヤングマスク)と申します。
以下の定理について考えているのですが、正しいかどうか検証していただけないでしょうか。
_____
(定理1)
(1). フェルマー、ミラーテストを通過する 確率的素数N があるとする。
N = 素数k × 2^x + 1 の時、
(2). g^((N-1)/2) mod N ≡ -1 で、かつ、 (3). g^((N-1)/k) mod N ≠ 1
となるg が見つかれば、Nは素数である。
_____
(証明)
(1) を通過する整数の共通点周期は、 N-1 か、N-1の約数のみである。
まず、(2) のテストにより、N-1/(偶数の約数) の疑いが晴れる。
また、N-1 から偶数成分を除いた奇数k は素数なので、 (3)のテストのみで、N-1/(奇数の約数) の疑いも晴れる。
よって、上記すべてのテストに合格する整数N の共通周期は N-1 のみとなることになるので、素数であると確定できる。
_____
よろしくお願いいたします。
|
|