1976年、 Whitfield DiffieとMartin Hellmanは、公開キー暗号化の革新的なアイデアを盛り込んだ記事「New Trends in Cryptography」を公開しました。 そして、 1977年8月に3人の科学者ロナルドライベスト 、 アディシャミール 、 レナード アドル マンがジャーナルサイエンティフィックアメリカンに記事を発表し、整数環での計算を使用してアルゴリズムを詳細に説明しました。 多くの人が知っているように、アルゴリズムのアイデアは条件付き片側関数の存在です-長い長さの素数のセットによる通常の乗算
（f： P x P- > P * P ）、これは計算上逆にすることが困難です。 つまり、 n = p * q（pとqは素数）を知ること、大きなnに対してpとqを見つけること（または数nを因数分解すること）は、難しい作業のようです。
同じ問題で、有名な数学者で科学者のマーティン・ガードナーは、アルゴリズムの著者の同意により、 RSA-129と呼ばれる数学的問題を発表しました。 その中で、彼は数字のペア（n、e）を書きました。公開鍵、数字nの長さは小数点以下129桁、eは1007に等しく、暗号化されたメッセージそのものです。 彼はメッセージの解読者に100ドルの報酬を約束し、それを年に2％で銀行に預けました。 アナリストによると、このような膨大な数を既存の因数分解アルゴリズムとそれらのコンピューターの能力で因子に分解するには、20,000年の連続操作が必要になります（Ron Rivestは、125文字で40クアドリレンを想定）。 しかし、状況は変わりました...
その後、1994年に、アメリカ軍の若い暗号作成者であるArjen LenstraがQuadratic Sieveアルゴリズムの改良を開発しました。これにより、妥当な時間で最大130桁の妥当な係数を見つけることができます。 アルゴリズムの漸近的動作はO（e sqrt（log n * log log n） ）でした。ここで、eは自然対数の底です。 ところで、自明な因数分解アルゴリズムの漸近的な振る舞いは
答えは次のとおりです。
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577
×32769132993266709549961988190834461413177642967992942539798288533
数字pとqの長さは、それぞれ64文字と65文字でした。 Martin Gardnerによって暗号化されたフレーズは、「 The Magic Words are Squeamish Ossifrage 」で、「 Magic words are Shy Osprey 」、またはロシアのウィキペディアによると「 Magic words are squeamish lamb 」です。 その後、4年後に140桁の小切手番号がレイアウトされるまで、推奨されるキーの長さは140文字に増加しました。 1998年、ビルゲーツは、200の文字を分解するために会社に無制限の資金とコンピューティングリソースを提供したと発表しました。 現時点では、この目標はRSA-200のタスクである2005年にすでに達成されています。 100ドルのうち、計算するのは難しくありません。17年間の利子は約140ドルで、これがフリーソフトウェアファンドに振り替えられました:-)
このストーリー全体は、アルゴリズムの作成者とRSAの特許を取得し、その結果として9億ドルの利益を受け取った会社の創設者にとって素晴らしいPRでした。
それが賢明なお金を稼ぐことの意味です;）
出典：SSU教授Saliy Vyacheslav Nikolaevich
不正確な点については事前におaび申し上げます。
コメントの修正に感謝します！