情報処理安全確保支援士試験 情報処理安全確保支援士試験 平成29年度春期 午前Ⅰ 問3: 次の流れ図の処理で，終了時の x に格納されているものはどれか。ここで，与えられた a，b は正の整数であり，mod(x,y) は x を y で割った余りを返

問題本文

次の流れ図の処理で，終了時の x に格納されているものはどれか。ここで，与えられた a，b は正の整数であり，mod(x,y) は x を y で割った余りを返す。

選択肢

• ア.a と b の最小公倍数
• イ.a と b の最大公約数
• ウ.a と b の小さい方に最も近い素数
• エ.a を b で割った商

正解

イ. a と b の最大公約数

解説

流れ図はx←a,y←bとし、y=0になるまで t←x mod y、x←y、y←t を繰り返す。これはユークリッドの互除法そのもので、終了時のxには最大公約数(GCD)が残る。よってイが正解。約分や暗号(RSAの鍵生成等)でも用いられる、剰余を使った古典的かつ高速なGCD算法である。

選択肢ごとの解説

• ア.最小公倍数は GCD を求めた後に a×b/GCD で算出するもので、この手続きの結果ではなく誤り。
• イ.剰余を繰り返すユークリッドの互除法であり、終了時xに最大公約数が入る正解。
• ウ.素数判定や探索の処理は含まれておらず、最も近い素数は求まらないため誤り。
• エ.商ではなく剰余(mod)を用いて反復しており、a÷bの商にはならず誤り。