素数というのは難しいものです。 私たちは学校で、それらが 1 と自分自身以外に約数を持たない数であること、そして数学者はそれらが無限に存在することを何千年も前から知っていることを学びます。 コマンドに基づいてそれを生成することは、それほど難しいことではないようです。

しかし、そうです。 任意に大きな素数を構築することは非常に複雑です。 基本的に XNUMX つの計算オプションがありますが、どちらにも欠点があります。 ランダム性を利用して推測によって素数を見つけることもできますが、その方法には一貫性がなく、毎回異なる素数が生成される危険があります。 あるいは、より信頼性の高い決定論的なアルゴリズムを使用することもできますが、計算コストが高くなります。

XNUMX月にコンピューター科学者のチームが 示されました 一種のハイブリッドアプローチも機能する可能性があると考えています。 彼らは、ランダムなアプローチと決定論的なアプローチを効果的に組み合わせて、特定の長さの素数を出力し、アルゴリズムが何度実行されても高い確率で同じ素数を出力するアルゴリズムを公開しました。 このアルゴリズムはランダム性と複雑性を興味深い方法で結びつけており、一部のエンコード方式が大きな素数の構築に依存している暗号化にも役立つ可能性があります。

「彼らは一連の試みを行い、それぞれが異なる長さの素数を構築しようとし、そのうちのXNUMXつがうまくいくことを示した」と述べた。 朗詠テル、高等研究所の理論コンピュータ科学者でしたが、この研究には関与していませんでした。 「これは決定論的に選択された素数を出力する構造ですが、その過程でコインを投げてランダムな選択を行うことができます。」

プライムの効率的なレシピを作成するという課題には深い根があります。 擬似乱数アルゴリズムを研究しているオファー・グロスマン氏は、「素数がどのように分布するのか、あるいは素数間のギャップについては、実際にはあまりわかっていない」と語る。 そして、素数をどこで見つけられるかわからない場合、素数を最初から生成する簡単な方法はありません。

時間が経つにつれて、研究者は前述のアプローチを開発しました。 最も簡単な方法は推測することです。 たとえば、1,000 桁の素数が必要な場合は、1,000 桁の数値をランダムに選択して、それをチェックします。 「それがプライムでない場合は、別のものを試し、また別のものを試し、見つかるまでそれを繰り返します」と彼は言いました。 ラフル・サンタナム、オックスフォード大学のコンピューター科学者であり、新しい論文の共著者です。 「素数がたくさんあるため、このアルゴリズムでは、比較的少ない反復回数で、高い確率で素数となる数値が得られます。」 しかし、ランダム性を使用すると、毎回異なる数値が得られる可能性が高いと同氏は述べた。 一貫性が必要な場合、たとえば、大きな素数の可用性に依存するセキュリティの暗号化手法を採用している場合、これは問題になる可能性があります。

もう 1,000 つのアプローチは、決定論的アルゴリズムを使用することです。 開始点を選択し、数値の素数性を順番にテストし始めることができます。 最終的にはいずれかが見つかることになっており、アルゴリズムは最初に見つかったものを一貫して出力します。 ただし、時間がかかる場合があります。2 桁の素数を探している場合は、XNUMX 桁の計算でも可能です。⁵⁰⁰ 宇宙の年齢よりもはるかに長いステップがかかるだけでは、成功を保証するのに十分ではありません。

2009 年、数学者でフィールズ賞メダリストのテレンス・タオは、より良い成績を収めたいと考えていました。 彼は数学者に、計算時間制限内で指定されたサイズの素数を見つけるための決定論的アルゴリズムを考案するよう要求しました。

その制限時間は多項式時間として知られています。 アルゴリズムは、必要なステップ数が次の多項式関数以下の場合、問題を多項式時間で解決します。 n、入力のサイズ。 (多項式関数には、次のような正の整数乗された変数を含む項が含まれます。 n² または4n³.) 素数構築のコンテキストでは、 n は、必要な素数の桁数を指します。 計算的に言えば、これにはそれほどコストはかかりません。コンピューター科学者は、アルゴリズムによって多項式時間で解決できる問題を簡単だと説明します。 対照的に、難しい問題には指数関数的な時間がかかります。つまり、指数関数 (2 などの項を含む) で近似されたステップ数が必要になります。ⁿ).

研究者たちは何十年もの間、ランダム性と硬度の関係を研究してきました。 素数の構築問題は、ランダム性を許容し、毎回異なる数値を受け取ることに満足している場合は簡単であると考えられ、決定論を主張する場合は難しいと考えられていました。

タオの挑戦に果たせる者はまだ誰もいないが、新作はそれに近い。 これは、マサチューセッツ工科大学のコンピューター科学者、シャフィ・ゴールドワッサー氏とエラン・ガット氏が 2011 年に導入したアプローチを大きく活用しています。 彼らは、「擬似決定論的」アルゴリズムについて説明しました。これは、大きな素数を見つけるなど、ランダム性の利点を活用し、高い確率で毎回同じ答えを生み出すことができる検索問題の数学的レシピです。 彼らはレシピ内のランダムビットの効率を使用し、結果ではランダム化が解除され、決定論的に見えます。

それ以来、研究者たちは擬似決定論的アルゴリズムを研究してきました。 2017年、ウォリック大学のサンタナム氏とイゴール・オリベイラ氏（新しい研究にも貢献） 記載された 素数を構築するための擬似決定論的アプローチは、ランダム性を使用し、説得力のある決定論的に見えましたが、「準指数関数的」時間で機能しました。つまり、指数関数よりも高速ですが、多項式時間よりは遅くなります。 そして2021年、Tellと リージェ・チェン、カリフォルニア大学バークレー校のコンピューター科学者、 探検した 難しい問題を使用して擬似乱数生成器 (ランダムな出力と区別できない一連の数値を生成するアルゴリズム) を構築する方法。 「[私たちは]硬度と擬似乱数の間に新たな関係を発見しました」とチェン氏は語った。

2023 年の春にようやくピースが集まりました。 計算の複雑さに関するブートキャンプ バークレーのサイモンズ計算理論研究所で、研究者たちは過去の結果を織り交ぜながらこの問題に協力し始めた。 チェン氏によると、新しい研究では、オックスフォード大学のコンピュータ科学者で共著者のハンリン・レン氏が、チェン・テルの結果とサンタナム・オリベイラのアプローチを新しい方法で組み合わせるという最初のアイデアを持っていたという。 その後、チーム全体が新しい論文を作成するためにアイデアをより完全に発展させました。

サンタナム氏によると、結果として得られた擬似決定論的アルゴリズムは、過去の研究を調べる新しい方法を使用して、多項式時間で素数を生成したという。 このツールはランダム性を利用して特定の長さの素数を出力したことが証明されており、このツールはランダムな推測よりも正確で、決定論的な処理よりも計算効率が高くなります。

サンタナム氏によると、新しいアルゴリズムは非常にシンプルで、幅広い検索問題に適用できるという。実際には、多項式時間でメンバーシップを決定できる、素数などの高密度の数のサブセットに適用できる。 しかし、完璧ではありません。 このアルゴリズムは無限に多くの入力長に対応しますが、すべての桁の長さをカバーできるわけではありません。 まだいくつかの値が存在する可能性があります n アルゴリズムが決定論的に素数を生成しないものもあります。

「その小さな警告をなくすことができたら素晴らしいでしょう」とグロスマン氏は言う。

サンタナム氏によると、最終的な目標は、ランダム性をまったく必要としないアルゴリズムを見つけることだという。 しかし、その探求はまだ開かれています。 「私たちが利用したいのは決定論です」と彼は言いました。

しかし同氏は、擬似ランダムプロセスは強力なツールであり、素数の構築などのプロジェクトは、数学、コンピューターサイエンス、情報理論、その他の分野のアイデアを結びつけるために擬似ランダムプロセスを使用する方法のXNUMXつにすぎない、とも指摘した。

「これらの素晴らしい観察結果が他にどこにつながるのかを考えてみるのはとても楽しいです」とテル氏は語った。