代数学入門   Introduction to Algebra

東京電機大学未来科学部1年 FI科 他 (月曜5限)

担当: 原 隆

場所: 　 オンライン講義

講義内容 (シラバスより):
整数 (0,±1,±2,...) は最も「素朴な」数の概念であり、あまりにも身近な数であるため、ともすれば実数などと比べて非常に単純な数の様にも考えられがちである。しかし、〈整数の世界〉が〈実数の世界〉とはまた違った意味で非常に奥深く魅力的な構造を持っていることは古来より知られており、現代に至るまで数多の数学者達を魅了し、研究へと駆り立ててきた。さらに近年では、暗号理論など我々の生活に密接に関わる分野にも整数の理論が応用されるようになってきている。

この講義では初等整数論の初歩について学習する。整数を割った「余り」の概念の復習から始め、「余りの数の世界」に於ける様々な法則の金字塔たるフェルマーの小定理、オイラーの定理を理解することを目指して講義を進める。時間が許せば応用的なトピックスについても扱う予定である。　

教科書: 遠山啓著『数の不思議 — 初等整数論への招待』 (SBクリエイティブ)
参考書: 楫元著『工科系のための初等整数論入門 — 公開鍵暗号をめざして』 (培風館)

このページには主に講義のメモ (個人的な備忘録に近いです) 及び配布物等を掲載してゆく予定です。

お知らせ / 更新履歴

• 9月16日   これまでの授業ページを更新しました。とってもおそくなってすみません m(_ _)m
• 9月16日   本講義の参考資料および演習問題の解答をすべてアップロードしました。後期の講義もすべてオンラインとなる可能性が高いため、予習や復習の便宜を図って 今年度は参考資料をすべて事前に公開することにします。
• 初回講義は 9月21日 (月) です。

参考資料一覧

• ガイダンス資料, オンライン講義化に伴う変更点   (予め読んでおくこと!! )

0. 参考資料0 (導入: ピタゴラス数について)
1. 参考資料1 演習問題解答 (割り算の定理と最大公約数、ユークリッドの互除法)
2. 参考資料2 演習問題解答 (互除法の原理とその証明、1次不定方程式の解の構造)
3. 参考資料3 演習問題解答 (ベズーの補題と1次不定方程式の特殊解、素因数分解の存在と一意性定理)
4. 参考資料4 演習問題解答 (合同式の定義と基本性質、合同式を使ってみよう)
5. 参考資料5 演習問題解答 (1次合同方程式とその解法)
6. 参考資料6 演習問題解答 (連立1次合同方程式と中国式剰余定理)
7. 参考資料7 演習問題解答 (フェルマーの小定理とオイラーの定理)
8. 参考資料8 演習問題解答 (オイラーのトーシェント関数の基本性質)
9. 参考資料9 演習問題解答 (暗号理論への応用1: RSA公開鍵暗号)
10. 参考資料10 演習問題解答 (暗号理論への応用2: エルガマル公開鍵暗号)

講義内容

2020年12月21日 (月)

• 暗号理論への応用 (続)
  • 原始根と離散対数問題
  • ディフィー–ヘルマンの鍵共有プロトコル
  • エルガマル公開鍵暗号のプロトコル: ディフィー–ヘルマンの鍵共有に基づいて
• 参考資料
  • 参考資料10 演習問題解答 (暗号理論への応用2: エルガマル公開鍵暗号)
• 映像資料: Taher Elgamal Computer Security Day Interview (英語)
  2010年にスペインのマドリード工科大学で開催された Information Security Invernational Day DISI 2010 の際に収録されたエルガマル博士のインタビュー。冒頭 (1:45〜4:00辺り) で彼は「コンピューターの能力の劇的な進展に伴って、公開鍵暗号は鍵の桁数を増やすことで安全性を保ってきたが、暗号理論は数学に基盤をおいているので、(数学的に工夫を凝らせば) もっと少ないコストで安全性の高い暗号を開発できる可能性はある。ただ、電子商取引 (e-commerce) の場面で既に実装されている暗号システムを変更するには莫大なコストがかかるため、現状では既存の唯一つの暗号システムを用いて、鍵の桁数を増やす方向で安全性を確保するという対応しか出来ていないのが問題である」という趣旨の発言をしている。実際、現在ではより安全性の高い楕円曲線暗号なども実用可能な状態にまで開発が進んでいるにも拘らず、多くのウェブサイトなどでいまだにRSA公開鍵暗号が採用されているのも、システム刷新の際の莫大なコストが障碍となっているケースが多いとのことで、エルガマル博士の指摘は喫緊の課題であると言える。博士は後半も興味深いコメントをされているので、セキュリティに興味のある人は是非最後まで聴いてみよう。
  なお、エルガマル博士 (エジプト人) もインタビュアー (スペイン人) も英語のネイティヴ・スピーカーではないため、会話が若干たどたどしく聞こえるかもしれない。こういった光景は国際学会の場などはめずらしくもないが、英語のリスニングでネイティヴ・スピーカーの発音ばかりを聴いてきた人にとっては新鮮であっただろう。互いに母語を異にする人同士でも意思疎通を可能にする、まさに「共通語」としての英語という言語の真骨頂である。
• 小レポート12    問題および解答

2020年12月14日 (月)

• 暗号理論への応用
• RSA公開鍵暗号
  • RSA公開鍵暗号のプロトコル
    • 鍵生成プロトコルとメッセージ伝達方法について
    • 計算演習: RSA公開鍵暗号の鍵生成プロトコルと暗号化、復号プロセス
    • RSA公開鍵暗号の安全性 — (大きい数の) 素因数分解の困難性
• 参考資料
  • 学期末レポート・成績評価について   (学期末試験のアナウンス)
  • 参考資料9 演習問題解答 (暗号理論への応用1: RSA公開鍵暗号)
  • 楫元著『工科系のための初等整数論入門 --- 公開鍵暗号をめざして』(培風館) 第6章
    たった15ページ (!! ) で RSA 公開鍵暗号のエッセンスを見事に纏めてあります。講義ではやはり駆け足の説明になってしまいましたので、RSA公開鍵暗号の詳細に興味がある方は是非ご一読を。暗号の話題も散りばめられていて楽しいです。
• 映像資料: RSA-129 — Numberphile (英語)
  良質な数学動画を提供し続けている Numberphile シリーズ。今回は、何とあの RSA の1人である Ronald L. Rivest のインタビューを掲載。コンピューター登場の黎明期には4京年 (!! ) かかるだろうと思われていた巨大数RSA-129の素因数分解チャレンジが17年後には解かれてしまったエピソードや、RSAの共同提案者 Shamir, Adleman との思い出など、聴き所は満載。インタビューのロングバージョンへのリンクもあるので、興味のある方は是非そちらもどうぞ。暗号の開発者のインタビューなんてなかなか聞く機会もないと思うので、貴重な体験が出来ると思いますよ?! (ちゃんとした英語字幕も付けられると思います)
• 小レポート11    問題および解答

2020年12月7日 (月)

• フェルマーの小定理とオイラーの定理 (続)
  • オイラーのトーシェント関数の計算法
    • φ(p^e) の値の求め方
    • トーシェント関数の乗法性
    • 例題: 一般の自然数に対するトーシェント関数の値の計算法 — トーシェント関数の乗法性を用いて
    • トーシェント関数の乗法性の証明の概略
• 参考資料
  • 参考資料8 演習問題解答 (オイラーのトーシェント関数の基本性質)
• 映像資料: 非対称暗号化 — ごく簡単な解説 Asymmetric encryption — Simply explained (英語)
  インターネットが最早生活の必需品となりつつある今日に於いて、公開鍵暗号は無くてはならないものとなっています。情報化社会に於いて何故公開鍵暗号が必要とされるのか、そもそも「公開鍵暗号方式」とは何者なのか? — 今宵は情報セキュリティの分野では常識となっている「公開鍵暗号」について学んでみましょう。比較的ゆっくりで平易な英語なので、リスニングの練習にもぴったり☆
• 小レポート10    問題および解答

2020年11月30日 (月)

主張のため オンデマンド学習 (公開鍵暗号について)

2019年11月23日 (月)   勤労感謝の日

• フェルマーの小定理とオイラーの定理 (続)
  • オイラーのトーシェント関数とオイラーの定理
    • オイラーのトーシェント関数: 定義と例題
    • オイラーの定理の主張: 法が合成数の場合へのフェルマーの小定理の拡張
    • オイラーの定理の証明の概略: “法と互いに素な数” に制限して “aの段” の数を掛け合わせる
• 映像資料: 「ケーニヒスベルクの橋の問題」は数学をどのように変えたのか？ — ダン・ファン・デア・フィーレン How the Königsberg bridge problem changed mathematics — Dan Ban der Vieren (英語)
  7本もの橋が架かったケーニヒスベルクの街。2度同じ橋を渡ることなくすべての橋を渡る方法があるでしょうか—? 「ひと筆描き」の問題の元祖とも呼べる「ケーニヒスベルクの橋渡し」の問題。この難問に対して「そのような方法は無い」ことを示したのがレオンハルト・オイラーです。普通の人なら「このルートでもない、あのルートでもない」と試行錯誤しそうなところを、オイラーは「島と橋のつながり具合」に目を付けて、華麗に問題を解決してしまったのです。オイラーのこの卓越した視点は、現代のトポロジーやグラフ理論の先駆けとも言えるでしょう。
• 小レポート9    問題および解答

2020年11月16日 (月)

• 合同式 (続)
  • フェルマーの小定理とオイラーの定理
    • フェルマーの小定理
      • フェルマーの小定理の主張
      • フェルマーの小定理の例: mod 5, mod 7 の場合
      • 応用: 「大きい羃乗」を素数 p で割ったときの余りの計算、法 p での逆元の求め方
      • フェルマーの小定理の問題点: 法が合成数のときにはそのままの形では成り立たない!!
        → 法が合成数のときの拡張がオイラーの定理 (次回扱います)
      • フェルマーの小定理の証明
        • mod p の世界での “九九の表” を作ってみる
        • mod p の世界での “九九の表” の特徴;
          どの “段” も 1,2,...,p –1 がちょうど一度ずつ現れる
        • “九九の表” を利用した証明の概略
        • 一般の設定での証明
          「“九九の表” のどの “段” も 1,2,...,p –1 がちょうど一度ずつ現れる」ことをどのようにして証明するか?
• 参考資料
  • 参考資料7 演習問題解答 (フェルマーの小定理とオイラーの定理)
• 映像資料: ピエール・ド・フェルマー: 偉大なる思想家の経歴 Pierre de Fermat: Biography of a Great Thinker (英語)
  「立方数を2つの立方数の和に分けることは出来ないし、4乗数を2つの4乗数の和に分けることも出来ない。一般に羃の指数が $2$~より大きければ、その羃乗数を2つの羃乗数の和に分けることは出来ない。私はこのことに関して、真に驚くべき証明を発見したのであるが、それを書き記すにはあまりにも余白が狭過ぎる。」
  ディオファントスの『算術』の余白に書き込まれたこの問題が360年もの間数学者達を悩ませることになった “お騒がせ” 数学者、フェルマー。彼は “無限降下法” というテクニックを用いて、様々な整数問題を解決に導いた人でもあります。今回の動画では、そんなフェルマーについて迫ってみましょう。
• 小レポート8    問題および解答

2020年11月9日 (月)

• 合同式 (続)
  • 連立1次合同方程式と中国式剰余定理
    • 『孫子算経』の “数当て問題” — 「余りの情報からもとの数を求める」
    • 中国式剰余定理 — 連立1次合同方程式の解の存在と一意性
    • 連立1次合同方程式の解法: ウォーミングアップ (一般の連立1次合同方程式の解法は次回)
    • 例題: 『孫子算経』の問題の解法
    • 連立1次合同方程式の解法: 一般の場合
      “右辺を1箇所だけ残して残りを0にした連立合同方程式の解を足し合わせる”
• 参考資料
  • 参考資料6 演習問題解答 (連立1次合同方程式と中国式剰余定理)
• 映像資料: 警察と泥棒: 漢兵を徴兵するのに余りを用いること 點指兵兵 點用餘數點漢兵 (中国語)
  (恐らく) 中国の数学教育番組的な動画。所謂 “韓信點兵” 算についての解説。数学の時間 (?) に居眠りをしていると、夢の中に中国の武将 韓信(ハンシン) が現れて……、という内容 (だと思います)。
  中国語が分からなくても、何となく漢字の雰囲気で内容が推察出来るのは、同じ漢字言語圏ならではの感覚なのでしょうね。“韓信點兵” の歴史的背景や、“韓信點兵” 算の計算法 (『算法統宗』に掲載されている「謎の詩」の意味) についても解説されています。中国語・中国文化を履修されている人は、リスニング教材として活用してみてはいかがでしょう (^^;
• 小テスト7    問題および解答

2020年11月4日 (水)

• 合同式 (続)
  • 1次合同方程式とその解法 (続)
    • 法 n での逆元の定義と具体例
    • 逆元の存在定理: a が法 n と 互いに素 なら a^–1 が存在する
    • 1次方程式 ax=d の解法 (復習) — 両辺に x の係数の逆数を掛ける
    • 1次合同方程式 ax≡b (mod n) の解法2: 合同式を a と n の最大公約数で “約分” してから x の係数の逆元を両辺に掛ける
    • 1次不定方程式の合同式を用いた解法
      適当な法で modulo して x か y の1次合同方程式に帰着する
• 映像資料: 歴史の中の数学者: ガウス Mathematicians of History: Gauss (英語)
  「歴史上最も偉大な数学者を挙げよ」と問われたら、真っ先に名前が挙がるであろう天才数学者ガウス。その業績は驚くべきもので、この映像資料で挙げられているだけでも
  • 1+2+...+100の計算公式の発見
  • 正十七角形の作図法の発見
  • 合同式と平方剰余の相互法則
  • 電磁気学に於けるガウスの法則の発見
  • 確率統計に於けるガウス分布
  • 線形代数学に於けるガウスの消去法
  • 天文学への貢献
  など、数学の範疇に留まらず様々な分野で名を残していることが窺えるでしょう。興味のある方は是非ガウスの生涯や業績を調べてみよう!!
• 小テスト6    問題および解答

2020年10月26日 (月)

• 合同式 (続)
  • 合同式を使ってみようⅡ: 大きな羃乗数を割った余り
    • 方針: 底を法より小さい数で取り換える → “1と合同になるような羃乗”を探す
    • 羃乗の底と法が 互いに素 なら、必ず1と合同になるような羃乗が存在する — フェルマーの小定理オイラーの定理の帰結
  • 1次合同方程式
    • 1次合同方程式とは? — (実数の世界での) 1次方程式と比較して
    • 1次不定方程式との関係
      ax ≡ d (mod n) を満たす整数 x が存在する ⇔ ax - ny = d を満たす整数組 (x, y) が存在する
    • 1次合同方程式の解の存在と一意性定理
      • 解の存在の必要十分条件: 1次不定方程式に対するベズーの補題の帰結
      • 1次合同方程式 ax≡b (mod n) の解法1: a|b のとき
• 参考資料
  • 参考資料5 演習問題解答 (1次合同方程式とその解法)
• 映像資料
  • 干支 - 十二支の話（日本語版）アニメ日本の昔ばなし／日本語学習 (日本語)
    昔々、神様が「元旦の朝、一番目から十二番目までにここにやって来たものを、1年交代で動物の大将にする」という触書を出したものだからさぁ大変。牛やら虎やら兎やら、はては天空の龍まで巻き込んで、一世一代の大競走が繰り広げられました。ところが猫は、鼠から「元旦の次の日の朝に到着したもの」という誤った触書の内容を教えられて……
    十二支にまつわる日本の逸話。「なぜ猫は十二支に入っていないのか」「『犬猿の仲』の由来」「猫が鼠を追いかけまわすようになった理由」など、ちょっと情報過多なんじゃないのという位色々なことの “由来” を説明しているお話。まぁこの位は、日本人として把握しておいても良いんじゃないでしょうかね?
• 小レポート5    問題および解答

2020年10月19日 (木)

• 合同式
  • 合同式とは?
    • 定義とその意味 — “整数を n で割った余りで分類する”
    • 合同式の基本性質: 合同式の加減乗について
      ※ 講義ではあまり強調しませんでしたが、合同式同士の 割り算は一般には出来ない ことに注意!! (そのうち補足します)
  • 合同式を使って遊んでみようⅠ: 暦算
    • 暦算: “〇年後 / 〇年前は何曜日?”
    • 閑話休題: 閏年, 干支と暦について
    • 曜日の計算の仕方の復習: “1週間=7日間” で割った余りに注目する
    • 合同式の威力: 先にすべて n で割った余りにしてから加減乗算をしても良い!!
      → 計算量が飛躍的に少なくなる!!
• 参考資料
  • 参考資料4 演習問題解答 (合同式の定義と基本性質、合同式を使ってみよう)
• 映像資料
  • 后羿と10の太陽: 中国の伝承 Hòu Yì and The Ten Suns: A Chinese Folktale (英語)
    遙か昔の帝堯の治世、天帝 (帝夋) の息子である10個の太陽が一度に地上に現れ、中国の地は灼熱地獄と化しておりました。天帝はこの問題を解決すべく、弓の名手たる后羿(こうげい) (中国読: ホウイー) を地上に遣わしました。しかしあろうことか后羿は、天帝の息子たる太陽を1つを残してすべて射落としてしまったのです。激怒した天帝は后羿とその妻嫦娥(じょうが) (中国読: チャンガ) を神籍から抜いてしまいます。困り果てた后羿は、崑崙(こんろん)山 (中国読: クンルンシャン) に棲まう西王母のもとを訪ね、宮殿と引き換えに不老不死の妙薬を貰うことに成功します。家に戻った后羿は妙薬を隠しますが、嫦娥はそれを見つけてしまいました。或る日庭を散歩していた嫦娥は、好奇心を抑えられず不老不死の妙薬を飲んでしまいます。すると嫦娥の身体はあれよあれよと浮かび上がり、后羿が慌てて引き止めようとするも間に合わず、満月へと消えていってしまったのでした。
    『射日神話』『大羿射日』として伝わる中国の有名な故事。現在も暦や占術で用いられる十干 (甲乙丙丁戊己庚辛壬癸) が10の要素からなるのは、この伝承に由来するのではないかとも言われています (諸説あります)。
• 小レポート4    問題および解答

2020年10月12日 (木)

• 1次不定方程式 (続)
  • 補足: 1次不定方程式の整数解の図形的意味: 直線上の格子点の座標
  • ベズーの補題: 定数部分が x と y の係数の最大公約数で割り切れるならば、1次不定方程式は整数解を持つ
  • 1次不定方程式が整数解を持つときは、ユークリッドの互除法の “逆再生” によって特殊解を求められる
  • 例題: ユークリッドの互除法の “逆再生” による1次不定方程式の特殊解の構成
• 整数の素因数分解とその一意性
  • 素数の定義
  • 素因数分解の存在と一意性定理
  • ユークリッドの補題 — ベズーの補題の応用として
  • 素因数分解の一意性の証明方針
• 参考資料
  • 参考資料3 演習問題解答 (ベズーの補題と1次不定方程式の特殊解、素因数分解の存在と一意性定理)
• 映像資料
  • 幾何学の父 ユークリッド: ユークリッド幾何学への招待 Euclid as the father of geometry: Introduction to Euclidean geometry (英語)
    ユークリッド『原論』でお馴染みの古代ギリシアの数学者ユークリッド (エウクレイデース)。現在の「定義」「公理」「命題」「証明」型の数学様式の端緒は『原論』にまで遡ると言っても過言ではない。小難しい『原論』の著者にして「幾何学に王道なし」の名言を残す、いかにも厳格そうなイメージのユークリッド。そんなユークリッドが創設した “ユークリッド幾何学” の世界を、しばし覗いてみよう!!
    ※ 英語字幕も利用出来るので、「我こそは」と思う人はリスニングにもチャレンジしてみよう!
• 小レポート3    問題および解答

2020年10月5日 (月)

• 1次不定方程式
  • 不定方程式 (ディオファントス方程式) の定義と例
    ピタゴラス数の決定、フェルマーの最終定理など: ディオファントス問題は見かけ以上に難しい!!
  • 1次不定方程式の整数解が存在する必要条件: 係数の最大公約数が右辺の数を割り切ること
  • 実は逆も成り立つ: 係数の最大公約数が右辺の数を割り切るならば整数解が存在する (次回)
  • 1次不定方程式の解の構造 — ひとつ整数解が存在すれば、無限個の整数解が存在する
  • 例題: 特殊解が与えられたときの、全ての整数解の求め方
• 参考資料
  • 参考資料2 演習問題解答 (互除法の原理とその証明、1次不定方程式の解の構造)
• 映像資料
  • 【算数クイズ】古代ギリシャの数学者「ディオファントスの一生」（IQテスト・脳トレ）brain plus*
    ディオファントスの墓石に記されているという数学の問題。まぁ単なる1次方程式ではあるが、果たして解けるであろうか? 頭の体操だと思って挑戦してみよう!! ……それにしても、墓碑銘にまで数学の問題を残すとは、根っからの数学者だったんですねぇ。。
• 小レポート2    問題および解答

2020年9月28日 (月)

• ピタゴラス数について
  • ピタゴラス数の定義、例
  • ピタゴラス数は「整数の範囲で考えるから難しい」 (ディオファントスの問題)
  • 命題: x²+y²=z² のとき、x, y の少なくとも一方は偶数
  • 証明の概略: 「余りで分類する」 → 合同式の世界へ
• 約数と倍数
  • 割り算の定理
  • 約数と倍数, 最大公約数
  • ユークリッドの互除法
• 参考資料
  • 参考資料0 (導入: ピタゴラス数について)
  • 参考資料1 演習問題解答 (割り算の定理と最大公約数、ユークリッドの互除法)
• 映像資料
  • Numberphile ルート2   Root 2 (英語)
    ルート2についてのあれこれ。中盤に出て来る「ピタゴラス教団とルート2」の話は非常に有名で、以前しくじり先生の中田偉人伝でも取り上げられていました。
    終盤ではルート2が無理数である (分数で表せない) ことの証明も扱っていますので、忘れてしまった方は是非ご覧下さい。ゆっくりとした非常に聞き取り易い英語ですし、字幕も付けられますので、リスニングの練習にも活用出来るのでは?
• 小レポート1    問題および解答

2020年9月21日 (月)

• 履修に関するガイダンス   ガイダンス資料, オンライン講義化に伴う変更点
※ 次回授業日は9月30日です!! 履修予定の方は、登録期間中に履修登録を済ませておくこと!!
※ 次回の小テストでは、反転授業として ユークリッドの互除法を復習してきたことを前提として 出題します。参考資料1の演習問題1-2.を解けるようにしておくこと!! (昨年度の小テスト1も参照)

講義日程

9月   9日, 16日 (敬老の日), 23日 (秋分の日), 30日
10月   7日, 14日 (体育の日), 17日 (月曜授業実施日), 21日, 28日
11月   4日 (休校日 / 旭祭), 7日 (月曜授業実施日 / 休講), 11日, 18日, 25日
12月   2日, 9日, 16日, 23日, 30日 (冬季休講日)
1月   6日 (冬季休講日), 13日 (成人の日 / 休校日), (20日)