| 講演内容アブストラクト | |
|
1.ユークリッドは素因数分解を知っていたか？ 斎藤 憲 知っていたに決まっているでしょう，というのがこの問に対する従来の答えでした． しかし『原論』の整数論（第7巻から第9巻）の命題と証明を丹念に調べていくと，すべての数は素因数の積であるという意識があれば，もっと要領よく証明ができるはずの命題が少なくありません． 今日はその中でも有名な完全数に関する定理をとりあげます．『原論』の整数論の最後（第9巻命題36）は，「2^n - 1 が素数ならば，P = (2^n - 1)2^(n-1) は完全数である」ことを（表現は少し違いますが）証明しています．ここで A = 2^n - 1 と置くと，P の約数で P 自身より小さいものは 1, 2, …, 2^(n-1) と A, 2A, …, 2^(n-2)A であり，直前の命題で等比数列の和を得ているユークリッドはこれらの和が P に等しいことを容易に証明しています．しかしPの約数がこれらのものに限られることの証明に，大変な手間をかけています． 四角形の分類におけるこの双対的様相を念頭におくと、ひとつの「四角形」が浮かび上がります。つまり「台形」＝「隣り合う２組の角の和が等しい四角形」に対応する、「隣り合う2組の辺の和が等しい四角形」という概念が自然に登場してもよさそうなものです。この「四角形」は何なのでしょうか。そもそも、この「双対性」の正体は何なのでしょうか． 彼の苦労の原因は，Pが 2・2・…・2・(2^n - 1) のような「素因数の積」として見えていなかったことにありそうです． なぜ見えなかったかといえば，『原論』には，数の積を ab とか abcd というふうに因数が見えるように表わす記法がなかったからだと思われます． 現代の初等整数論と一見同じようで同じではないユークリッドの整数論の世界を探索してみたいと思います． |
2.「アルゴリズム」とは何か？ 野崎 昭弘 「アルゴリズム」とは、ある問題を解くための「方法・手順」のことです。たとえば２つの自然数m, nの、最大公約数を求める「ユークリッドの互除法」は、昔から有名なアルゴリズムです。理論的には「その問題を解く方法が、そもそも存在するか」という「アルゴリズム存在の可能性」、現実社会では「解ける問題なら、なるべく短時間で解きたい」という「アルゴリズムの効率の問題」が重要です。前者は1930年代、後者は1960年代以降に盛んに研究され、私も1970年代後半からこの分野の研究に参加しました。 ここではおもに後者を取り上げて、この言葉の意味と重要性が実感できるように、ごくやさしい問題（ベキ乗の計算：x^10の値は、何回の乗算で求められるか？）から始めて、近年話題の「公開鍵暗号」の考え方の解説をしてみたいと思います（そのために「暗号」の初歩から説明をします）。 また時間があれば、高校数学で取り上げてもよい「アルゴリズムの問題」にも触れてみたいと思います。 |