数学ナビゲーター掲示板

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

■50152 / 親記事)  素数生成法について
  
□投稿者/ 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 のみとなることになるので、素数であると確定できる。

    _____

    よろしくお願いいたします。
引用返信/返信 [メール受信/OFF] 削除キー/



スレッド内ページ移動 / << 0 >>

このスレッドに書きこむ

Mode/  Pass/

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

- Child Tree -
Edit By 数学ナビゲーター