AIと数学 -- AIはどのような問題をどのように解いたのか　(3)

 【 AIと数学 -- AIはどのような問題をどのように解いたのか　(3)　】

僕が何度かセミナーで取り上げながら、そのことを忘れていた問題がもう一つありました。それが、７番目の問題 いうです。それは、n次元のLattice空間で格子点に一番近いベクトルを求める問題です。このトピックについては、2022年9月のセミナー「ラティス暗号入門」で詳しく取り上げています。

このセッションでは、まず、AIがどのような問題を解いたのかを知ってもらうために、この "Closest Vector Problem" がどのような問題であるのかを、これまでのマルレクのセミナー「ラティス暗号入門」の資料を通じて紹介しようと思います。といっても、改めて過去の資料を読んでほしいということなのですが。

このセミナー「ラティス暗号入門」では、"Closest Vector Problem" を解くことの難しさを利用した量子耐性を持つ（量子コンピュータでも破れないという意味）新しい暗号技術「ラティス暗号」技術の紹介がメインテーマです。そこでは、ラティス暗号」技術の中核である Oded Regevが開発した、"LWE (Learning with Errors)" という手法と"Closest Vector Problem"の関係が論じられています。

ただし今回、OpenAIが公開した"Closest Vector Problem (CVP)" についての論文は、それとは違ったアプローチを取っています。そこでは、代表的な「NP完全問題」である 「3SAT問題」からの決定論的多対一の多項式時間還元によって GapCVP がNP困難であることを直接証明しています

----------------------------

2022/09/30「ラティス暗号入門」 まとめページ
https://www.marulabo.net/docs/cipher3/
コンシェルジェαバージョン
https://www.marulabo.net/20220933md/

「ラティス暗号入門」 講演資料 pdf 
https://drive.google.com/file/d/1F7ShzeRuDl0mLCe69kX32fgD5tm-Thqi/view?usp=sharing

講演ビデオ Part 1 「ラティス入門」
https://youtu.be/v1xnh40C5uE?list=PLQIrJ0f9gMcOLK3eePEamNsUemew4hBLS

講演ビデオ Part 2 「ラティス暗号 LWE」
https://youtu.be/_iV4R7Zz4Xs?list=PLQIrJ0f9gMcOLK3eePEamNsUemew4hBLS

講演ビデオ Part 3 「ラティスとラティス暗号」
https://youtu.be/hkw5m-Sbcs4?list=PLQIrJ0f9gMcOLK3eePEamNsUemew4hBLS

セミナーに向けたショートムービーの再生リスト
https://www.youtube.com/playlist?list=PLQIrJ0f9gMcPtw-6OwIOO2rFKu_A-7OfF

-------------------
関連セミナー
-------------------

● 2019/06/03「暗号技術の現在 -- ポスト量子暗号への移行と量子暗号」まとめページ
https://www.marulabo.net/docs/cipher/
コンシェルジェαバージョン
https://www.marulabo.net/20190603md/

● 2022/08/27「暗号技術の現在」まとめページ
https://www.marulabo.net/docs/cipher2/
コンシェルジェαバージョン
https://www.marulabo.net/20220827md/

● 2022/09/30「ラティス暗号入門」 まとめページ
https://www.marulabo.net/docs/cipher3/
コンシェルジェαバージョン
https://www.marulabo.net/20220933md/

コメント

コメントを投稿

このブログの人気の投稿

宇宙の終わりと黒色矮星

イメージ
【宇宙の終わりと黒色矮星】 図のようなストーリーで、「宇宙の終わりとエントロピー」という投稿を準備していたのだが、いろいろ雑念が湧いて気がすすまなくなる。その理由は別稿で。 この図は、「閉じられた部屋でのガスの拡散」というわかりやすいモデルで理解されるエントロピーの増大の法則が、あるフェーズから、宇宙規模でみれば、「全ての物質のブラックホールへの吸収・収斂」として現れると言うことを主張している。最初、ペンローズのこの話を読んだときには、目からウロコだった。 このストーリーにはもっと先がある。最近のシミュレーションでは、指数関数的に膨張する宇宙では、巨大なブラックホールに捕捉されるのは、宇宙全体の物質の10%程度だという。恒星起源のブラックホールは 10^67 年で、銀河系中心の巨大ブラックホールも 10^99年で、ホーキング放射で「蒸発」し姿を消す。 ブラックホールに捕捉されなかった宇宙の残りの90%の物質は、元それが属した銀河系から孤立したまま星の一生の進化を続ける。太陽の1.2倍程度の質量を持つ星は「白色矮星」になるのだが、「白色矮星」は 10^17年で「黒色矮星」に変わる。 「黒色矮星」は、現代の「宇宙の終末論」では、もっとも注目されている天体なのだが、それはまだ観測されていないと言う。というのも、この天体は光を出さないからだ。「黒色矮星」の中心は、最も安定な原子である鉄の「結晶」でできていて、温度は絶対零度近くに冷却されている。 「黒色矮星」は、とても長生きする天体である。陽子崩壊がおきるなら、黒色矮星の寿命は 10^32年程度だが、もし陽子が安定しているとすれば、太陽の 1.24倍程度の質量を持つ「黒色矮星」は、10^1600年後に突然崩壊して超新星爆発を起こす。もっと軽い、太陽の1.16倍程度の質量を持つ「黒色矮星」は、10^32000 年後（！）に超新星爆発を起こす。 このシナリオによれば、宇宙は、とてつもなく長い長い退屈な時間をかけて、その死を迎える。「黒色矮星」の超新星爆発は、宇宙の死を飾る最後の打ち上げ花火である。その後には、宇宙には何も起こらない。 この記事は、ジョン・バエズの "Black Dwarf Supernovae" を基にしたものだ。https://johncarlosbaez.wordpress.com/202...
続きを読む

機械の言語能力の獲得から考える embeddingの共有・蓄積・検索の未来

イメージ
機械の言語能力の獲得から考える embeddingの共有・蓄積・検索の未来 #01 「機械が言語能力を獲得した」ということについて https://maruyama097.blogspot.com/2025/12/blog-post_25.html #02 ことばから文字へ https://maruyama097.blogspot.com/2025/12/blog-post_51.html #03 情報の共有と情報の集積 https://maruyama097.blogspot.com/2025/12/blog-post_37.html #04 文字からembeddingへ −− 大規模分散システムの成立 https://maruyama097.blogspot.com/2025/12/embedding.html #05  文字からembeddingへ −−意味の分散表現論の系譜 https://maruyama097.blogspot.com/2025/12/embedding_25.html #06  意味の分散表現論の登場 https://maruyama097.blogspot.com/2025/12/blog-post_27.html #07  文の意味のベクトル表現の発見 https://maruyama097.blogspot.com/2025/12/blog-post_30.html #08  Interlude 1 −− ChatGPTが生まれた日 https://maruyama097.blogspot.com/2026/01/interlude-1-chatgpt.html #09 Interlude 2 −− OpenAI の分裂が残したもの https://maruyama097.blogspot.com/2026/01/interlude-2-openai.html #10  Transformerの登場 https://maruyama097.blogspot.com/2026/01/transformer.html #11  1/31 マルレク「機械の言語能力の獲得を考える」へのお誘い https://maruyama097.blogspot.com/2026/01/131...
続きを読む

1 + 196883 = 196884

【 1 + 196883 = 196884  −− ある数学的認識の飛躍の物語 】 このコラムのタイトル「1 + 196883 = 196884」 は、当たり前すぎて、かえって意味不明かもしれません。 ただ、もしも、あなたのクレジット・カードの最初の6桁の数字に1を足したものが、あなたのマイナンバーカードの最初の6桁の数字と完全に一致していたとすれば、この式は、単なる足し算以上の意味を持ちます。 もっとも、クレジット・カードとマイナンバー・カードの場合、こうした数字の一致は、全くの偶然と考えていいと思います。 このコラムの「1 + 196883 = 196884」の場合も、左側に現れる数字196883と右側に現れる数字196884は、実は、数学の別の分野から取られたものです。 ただ、クレジット・カードとマイナンバー・カードの数字の偶然の一致とは異なって、この等式は、一見無関係に見える数学の分野間の驚くべき繋がりを示唆する、重要な発見の糸口となりました。 1 + 196883 = 196884 という一見自明の等式は、20世紀の数学的認識のある飛躍の物語の、最初の主人公なのです。 【  John McKayが気づいたこと 】 1978年ごろ、McKayは、あることに気づきます。 当時は、「モンスター群」の存在は証明されていなかったのですが、FischerとGriessは、モンスター群が「存在するならば」、その最小の非自明な既約表現（最も基本的な「対称性のパターン」を捉える方法）の次元は 196883 であると予想していました。 McKayは、この数字 196883 が、数論の分野で基本的な対象である j-不変量 j(τ) の q-展開（フーリエ級数展開に類似したもの）に現れる係数 196884 に極めて近いことに気づきます。     「1 + 196883 = 196884 だろう ! 」 そればかりではありません。McKayは、さらにj(𝜏) の最初のいくつかの項の係数が、モンスター群 M の既約表現の次元 r(n) の単純な線型結合として表現できることに気づきます。 【 数学者の直感 】 先に進む前に、あらためて問題を整理しておきましょう。 第一。ここでの議論には、二つの全く異なる数学的対象、「j-不変量」と「Monster...
続きを読む