平成１１年度７月　最適化とアルゴリズム研究部会

• 日時：7月24日（土） 14:00 〜 17:30
• 場所：上智大学7号館12階第1215号室
• 参加者：26名

• 発表１： 張 紹良氏 （東京大学 物理工学専攻）

  『大規模計算と前処理について --- SDPに現れる密行列に対する前処理』

  There is a strong need for the fast solution of large and dense linear systems which arise from Semidefinite Programming using the primal-dual interior-point method. Since direct methods are often too expensive in terms of computer memory and CPU-time requirements, then the only alternative is to use iterative methods. Here, an incomplete orthonalization preconditioner for the conjugate gradient method will be proposed. The efficient feature of the preconditioner will be confirmed by several numerical experiments.

• 西関 隆夫氏（東北大学 大学院 情報科学研究科）

  『絶対に安全な秘密鍵をトランプで共有する方法 --- 木，オイラー閉路，次数実現』

  秘密鍵を共有するプロトコルを設計する問題は暗号の最も基本的な問題の 一つである．従来のプロトコルは素因数分解問題など数論的な問題の困難さに もとずいていたので，絶対的に安全とは言えない．盗聴者が無限の計算能力を 持っていても絶対に安全，即ち情報理論的に安全な秘密鍵共有はトランプの カードをランダムに配布してゲームを行なうことにより実現することができる． 本講演ではこれらの最新の成果を概説する． 講演を理解するのに暗号の知識はいらない．初等的なグラフ理論や組合せ理論 の知識があれば充分です．