3．反復処理（原始根）

反復処理の方法をマスターすれば, コンピュータで大量の計算をできるようになり（地球物理の学生の意見）, プログラミングの基礎の最初の山を越したことになる！　例題をよく読んで, 変数の内容がどう変化しているのか, 頭の中で「シミュレーション」してみるとよい.

反復処理に挑戦する前に・・・・プログラムの強制終了

反復処理のプログラムに間違いがあると, 期待に反して「いつまで経ってもプログラムが終了しない」ことがあります. 実行中のプログラムを強制的に終了させるには, キーボードの下段にあるコントロール（Ctrl）キーを押したまま, アルファベットのｃを押すこと.

反復処理の基本形

for ( A ； B ； D ) C;


Ａは空か文. 反復される前に一度だけ実行される.

Ｂは空か条件式. Bが空がBが真な条件式ならば反復が継続される.

Ｃは空か文. 反復の各段階で実行される文

Ｄは空か文. 次の反復の段階に移るときに実行される文

ここで, C；の部分は, （if文の場合と同様に）, ブロック　｛文１；文２；文３；・・・文ｎ；｝　であってもよい. ここで n は０以上の勝手な整数です. ブロックはひとつの文のように扱われます.

注意：どんなときでも, 基本形は厳密に守りましょう. 例えば for の次の括弧の中にはセミコロン；をちょうど２つ書きましょう. 勝手に省略するのは御法度です.

for 文 for(A; B; D)C; が終了した直後では条件式 B は偽になっています.



漸化式で定義された数列を求めるときは, 同じような計算を反復します. 例えば, フィボナッチ数列

(1) F1=1, F2=1, Fi=Fi-1+Fi-2 (i ≥ 2)

の 9 頁目を計算してみましょう. Fi の値は直前の二つの頁 Fi-1 と Fi-2 の値さえ覚えていれば計算できます. Fi を計算するプログラムは, Fi-1 の値を格納する変数 fibonacci と Fi-2 の値を格納する変数 old_fibonacci があれば良く, 変数 fibonacci と old_fibonacci を同時に, fibonacci + old_fibonacci と fibonacci に更新します. このとき, まず F3 の値を計算するために式(1)を1回使い, Fn を計算するには式(1)を合計 n-2 回使います. つまりFn を計算するには変数 fibonacci と old_fibonacci を合計 n-2 回更新します. 
/*
Fibonacci.c
フィボナッチ列の第 9 項目をプリントするプログラム
*/

main() {
    int n ;
    int fibonacci ;
    int old_fibonacci;
    int xx;

    old_fibonacci = 1;
    fibonacci = 1;

    for (n=3; n<=9; n++){
        xx = fibonacci; /* 次の行は 変数fibonacciに格納されている値を更新するので, 
                           その前に fibonacci に既に格納されている値を変数 xx に保存する */
	fibonacci = fibonacci + old_fibonacci;
	old_fibonacci = xx;
    }

    printf("%d\n", fibonacci);

    return 0;
}


演習3-1. フィボナッチ数列 Fn (n ≥ 1) の一般項の数式を与えよ.



次に, 画面に3の0乗から8乗までの冪を9個順番に表示するプログラムを考えてみよう. 変数を使うと, 例えばこんな風に（も）書けます：

/*
simple_power.c
3の0乗から8乗までプリントするプログラム
*/

main() {
    int n ;


    n=1 ;                /* <== 注目：まず最初に n を 1 に初期化 */ 
    printf("%d\n", n) ;
    n=n*3 ;              /* n の値に3をかけたもので n の値を更新 */
    printf("%d\n", n) ;
    n=n*3 ;
    printf("%d\n", n) ;
    n=n*3 ;
    printf("%d\n", n) ;
    n=n*3 ;
    printf("%d\n", n) ;
    n=n*3 ;
    printf("%d\n", n) ;
    n=n*3 ;
    printf("%d\n", n) ;
    n=n*3 ;
    printf("%d\n", n) ;
    n=n*3 ;
    printf("%d\n", n) ;
    
    return 0 ;
}

この例では, 変数nを使って意図的に 「printf("%d\n", n); n=n*3 ; 」という全く同じパターンを作っていることに注目して下さい. そうすると, その部分を「 printf("%d\n", n) ; n=n*3; を9回反復せよ　」と記述できれば便利, と誰でも思います. Ｃ言語では, それをfor文を使って, 以下のように記述します：プログラムの流れを右に図示しました. プログラムを「読む」際に, 変数の状態変化も頭の中で想像してみると良い.

初期化しないと，その変数（メモリー）の中身に何が入っているのか，一般には不定ですので, 値を設定していない変数に自分の都合のよい値（例えば０）が入っていると仮定してはいけません. 
/* 
simple_beki.c
forによる反復(ループ）により
3の0乗から8乗までプリントするプログラム
*/

main() {
   int n;
   int i;


   n=1;


   for (i=0; i<9 ; i=i+1) {
      printf("%d\n", n) ;
      n=n*3;
   }
   return (0) ;
}

演習3-2.　2005年度情報基礎Aの大槻先生らによるプリントの「C言語を使ったプログラミング:基礎編」の問題６と７

反復処理を使いこなすコツは, 変数をうまく使って, 同じパターンの繰り返し構造をいかにひねり出すか, にある. その変数の出発値の設定（変数の初期化）も重要なポイント.



演習3-3.　上のプログラム simple_beki.c を改造し, 法 7 で 3の0乗から8乗までをプリントするプログラムを書き, 実行し, 1から6までの全ての整数が出力されることを確認せよ.

演習3-4.　演習3-3のプログラムを改造し, 法 7 で 27 の 0 乗から 8 乗までをプリントするプログラムを書き, 実行し, 6と1の繰り返しが出力されることを確認せよ.



27 の 7乗 10460353203
1ワードが32ビットである場合, int型変数が格納できる最大の整数 = 2 の 31乗 -1 2147483647

27 の 7 乗を 7 で割った余りを求めるのに, 次の公式を用い, 大きな数 xy を計算せずに済ませます.

(xy) % m = ((x % m) * (y % m)) % m

証明は z % m ≡ z (mod m) であることと, 合同式の性質 「a ≡ b (mod m) かつ c ≡ d (mod m)ならば ac ≡ bd (mod m)」を用います.

　冪乗を計算するための時間について -- 冪乗法

xの8乗を求めるのに上のプログラムでは 掛け算を7回行いましたが,
x8 =((x2)2)2
であるから, 掛け算は3回でよ いことが証明できます. 数 x の正整数 z 乗を求めるのに掛け算は z-1 回必 要に見えますが, 冪乗法という方法を用いれば, 2 log2 z 以下の 回数の掛け算で, x の z 乗が求められます. この冪乗法で冪を計算するプロ グラムも, やはり反復を用い, また, 剰余演算 % を用います. 詳しくは 冪乗法を見て下さい.

例題3-5.　p　= 11 とする. 次をプログラムを書け.



答え.
/*
kotae.c
例題3-5 の答え
*/

main() {
　　　int n;
　　　int i;
　　　int x;
　　　int p;

　　　p=11;

　　　printf("11-1以下の正整数 x を入力してください\n");
　　　scanf("%d", &x);

　　　n=1;

　　　for (i=0; i<p-1; i=i+1) {
　　　　　　printf("%d\n", n) ;
　　　　　　n=(n*x) %p; /* n が大きくならないようにするために
　　　　　　　　　　　　　　　　乗算をする毎に剰余を取る */
　　　}

　　　return (0) ;
}

x=1,2,..., 10 に対して x の 10 乗は常に　1になっています. 一般に,

Fermat の小定理. p が素数ならば x の p-1 乗を p で割った余りは1（ｘ＝1,...,p-1）

が成立します. RSA暗号でも使われています. その簡単な証明はいくつかります. より一般的な定理である Euler の定理はEuler 関数を用いていますが, その証明は, この講義でやる「ユークリッドの互除法」で紹介します.

RSA暗号を使って文章を暗号化して送付すると, その暗号文を無関係な人に傍受されても, その無関係な人が元の文章を解読するのに
時間がかかります. その背景には因数分解の困難さがあります. 因数分解の困難さについては, 次の「条件分岐（素朴な因数分解）」を見てみましょう.

入力 x=2,6,7,または8であるとき出力には1,2,...,11-1が全て現れます. x=2 の素数p=11の剰余系における冪は順に 1,2,4,8,5,10,9,7,3,6,1 です. 一般に, 素数 p の剰余系は適当な要素 g をもち, 剰余系の全ての要素が, 剰余系において g の冪になっています.

一般に,

素数 p の剰余系は必ず原始根 g を持ちます(教科書28節). すなわち


どんな素数 p に対してp 未満の適当な正整数 g があり,
p未満のどんな正整数 a も g の適当な冪と, 法 p で合同.

例えば, 素数 p=5 は原始根 g=2 を持ちます. 実際 p=5 の剰余系では g0=1, g1=2, g2=4, g3=3, g4=1 となります.

剰余系の与えられた要素が原始根の何乗かを問う問題は, 計算が面倒な問題とされていて, 公開鍵暗号の一つであるElGamal暗号のアルゴリズムの原理になっています. ElGamal暗号は, アメリカの連邦標準技術局（ＮＩＳＴ）の標準暗号です. ElGamal暗号は1月の授業でプログラムを作る予定です(詳しくはここ).

演習3-6.　2以上の比較的小さな正整数 x, y を入力されて, x が y の原始根ならば yes をプリントし, さもなければ no をプリントするプログラムを書け. x が y の原始根ならば どんな i=1,..., y-2 に対しても xi ≠ 1 (mod p) であることを利用し, 例題3-5 kotae.c を改造せよ.

演習3-7.　次を証明せよ. 勝手な素数 p に対して, (p-2)! = -1 (mod p).

演習3-8. p を奇素数とし, a を p 未満の正整数とする. 以下を証明せよ(教科書29節参照).
  1. ∃x（a ≡ x2 (mod p)） ⇒ a(p-1)/2 ≡ 1 (mod p)

  2. a(p-1)/2 ≡ 1 (mod p) ⇒ ∃x（a ≡ x2 (mod p)）
    ヒント. 素数 p のどんな原始根 g も位数が p-1 である(すなわち gn = 1 (mod p) ならば p-1 は n を割り切る）ことを用いよ.

  3. a(p-1)/2 ≡ 1 (mod p) または a(p-1)/2 ≡ -1 (mod p)
    ヒント. (a(p-1)/2 - 1 )(a(p-1)/2 + 1 )≡ 0 (mod p) を証明し, そのことから, 導け.


演習3-9.
  • 次のプログラムと, それにYとして user-id に現れる４桁の数, 適当な正整数を入力したときの出力を確認せよ.

    原始根・暗号関係の参考文献
    1. 「計算数学」, 朝倉書店, 和田秀雄著.
    2. ジョセフ・H・シルヴァーマン, はじめての数論 原著第3版 (発見と証明の大航海ーーピタゴラスの定理から楕円曲線まで） , ピアソン・エデゥケーション, 2007. 第9章「合同式, べき乗, そしてフェルマーの小定理」.
    3. 同上, 第21章「法pでのべき乗と原始根」
    4. 同上, 第22章「数論世界の対数ー原始根と指数」
    5. 「暗号・ゼロ知識証明・数論」, 情報処理学会監修, 岡本龍明・太田和夫共編
    6. 情報セキュリティ」, 情報処理学会編集, 宮地充子, 菊池浩明編著, 平成１６年



    条件式　　　　条件分岐
    （オイラー　　　（素朴な因数分解）
    関数）