Definitions
諸定義

定義に関する注意事項

高校までの教材は文部科学省が決める学習指導要領に基づいて 検定されているため，同じ用語はどの文章に出て来ても同じ定義，意味をもつ． しかし，大学で使用する教科書，論文ではそうとは限らない． 一般に用語の定義の一貫性はその文書の中でしか 保証されないことに注意する必要がある．

ウェブ等で専門外向けの他の解説を探して同じような語句を見つけたとしても 必ずしも同じ意味とは限らず，辻褄が合わなくなることがある． 教科書，論文を読んでわからない部分があった場合，定義については あくまでその文書（または明示されている参考文献）の中の定義を 確認しなければいけないことを肝に銘じておかなければならない．

しかし，自然数，素数などの基本的な定義については明記していない 教科書も多い． 専門外向けの解説など，文化が異なると 暗黙の了解となっている定義が異なることがある． 不幸にも本科目の分野はその代表的な分野である． 例えば自然数に 0 を含める定義と含めない定義があるが， どちらが正しい定義か，と考えるのは無意味で， 今読んでいる文書ではどちらの定義を前提としているのかを正確に理解 しなければならない．こういった定義は分野ごとに暗黙の了解が あることが多く，差異があってもある程度のパターンしかなく， 文脈で判断できるので専門家は問題とは感じていないようだが， 初学者にとっては無用の障害になる可能性がある．

以上のことから本科目で使用する教科書で使用できる 基本的な定義をここにまとめた． あくまで岡本栄司氏著，「暗号理論入門」に対応した定義であることに留意すること． 教科書に明示されていない定義については教科書と矛盾しない ものを選んだ．

この教科書で使用できる定義のまとめ

整数は定義済みとする．

自然数

0 以上の整数（注: 0 も含む）

約数

a を整数，b を正整数とする． a を b で割った余りが 0 のとき b は a の約数であるという． （注: a として 0 や負の数も許す． すべての正整数は 0 の約数）

素数

2 以上の整数で 1 と自分自身以外の約数をもたないもの

公約数

整数 a, b 両方の約数である ものを a, b の公約数という

最大公約数

整数 a, b の 公約数のうち最大のものを a, b の 最大公約数という．gcd(a, b) で表す．

互いに素

整数 a, b の 最大公約数が 1 のとき， a, b は互いに素であるという．

オイラー関数

自然数 n に対して {0,1,2,...,n - 1} のうち n と互いに素なものの個数を オイラー関数 φ(n) で表す． （注：本定義では gcd(0,1) = 1 なので 0 と 1 は互いに素，ゆえに φ( 1 ) = 1）