数論アルゴリズムの数学的基礎

書籍

オンデマンド版

大活字版

書籍

雑誌

電子版

読み上げ可能電子版

オーディオブック

著：長谷川　雄之

出版社：学術図書出版社

同一作品の他版

アクセシブルブック

内容紹介

〈まえがきより〉
本書は，理工系の学生を対象として，初等整数論とその応用について解説する目的で書かれた．
整数は身近にありながら極めて深遠なる存在であって，それゆえに太古の昔から人々の興味を惹きつけてきた．そして，人類の長い努力の成果として，たくさんの重要な事実が解き明かされてきた．しかし，それでもなお多くの未解決問題が残っている．
加えて，20 世紀以降，整数論に大きな影響を与える社会的できごとがあった．コンピュータの出現と情報通信技術に支配された社会の到来である．数十桁あるいはそれをはるかに超える桁数の整数はコンピュータなしには扱えない．そして，コンピュータをもってしても，巨大な整数に関連する特定の計算（たとえば素因数分解）が実行不能になってしまう．こうしたことが情報通信に必須となる暗号技術への整数論の応用を生んだのである．本書では，こういった応用面の話題も一部採り入れた．
初等整数論の解説にあたってとりわけ念頭に置いたのは，割り算の余りを強く意識してもらうことである．抽象的な代数学の手法に慣れ親しんだことのない人にとっては，まず具体的なイメージの湧きやすい割り算の余りで思考するほうが適していると考えたからである．そういった事情から，抽象的な概念を用いた説明は極力排した．一方で，群・環・体の理論の入門を理解してしまえば，多くのことが容易に導けるようになることも事実である．その方面の解説は他書に譲りたい．
擬似コードは載せていないが，代わりにどのような手続きで計算していけばよいのかがわかるような計算例を多く盛り込んだ．

第1章　ユークリッド互除法
　1.1　整数の整除
　1.2　ユークリッド互除法
第2章　合同式
　2.1　合同式
　2.2　未知数を含む合同式（1次の場合）
　2.3　孫子の定理
　2.4　未知数を含む合同式（高次の場合）
第3章　オイラー関数
　3.1　オイラー関数
　3.2　数論的関数の畳み込み
第4章　原始根
　4.1　原始根
第5章　平方剰余の相互法則
　5.1　平方剰余の相互法則
　5.2　2次合同式の解の計算（I）
　5.3　ヤコビ記号
第6章　ミラー–ラビン判定法
　6.1　擬素数
　6.2　カーマイケル数
　6.3　強擬素数とミラー–ラビン判定法
第7章　リュカ数列
　7.1　リュカ数列
　7.2　リュカ–レーマー判定法
第8章　2次ふるい法
　8.1　2次ふるい法の基礎事項
付録A　数表
　A.1　フェルマー数の素因数分解の現況
　A.2　既知のメルセンヌ素数
　A.3　カーマイケル数