全体を保存するデータ保存の一種です。
内緒で教えて
次の言葉は、作家の井上ひさしさんの至言です。
むずかしいことをやさしく
やさしいことをふかく
ふかいことをおもしろく
おもしろいことをまじめに
まじめなことをゆかいに
ゆかいなことをいっそうゆかいに
テキストを読むと、なんと難しく説明していることか。
分かってしまえば大したことではないことを、厳密と称してことさらに分かりにくく論じています。
何のことかイメージがわきません。
このシリーズでは、伝統的な方法では説明がとても難しいと思える事柄をいろいろな分野からとりあげ、
夫を織り交ぜながらその意味を中心に分かりやすく面白く伝えたく思います。
分かったふりをして今までなんとか逃れてきたあなたに、内緒で教えましょう。
内緒で教えて 一覧
| ブロックチェーン | ブロックチェーン数式表現 | ハッシュ | 鍵についてに一般論 |
| 量子コンピュータ：二重性 | 量子コンピュータ：重ね合わせ | 光を当てずにものをみる | 量子コンピューター |
近頃(2017年)、ビットコインがようやく世の話題に上るようになり、その基礎となる技術としてブロックチェーンが関心を集めるようになりました。
これは、これからの世を根本的に変えるかもしれない可能性を秘めた技術です。
その説明を読んでもよくわからないということをしばしば聞きますので、今回はこれについて平易に解説いたしましょう。
昨日、テレビ通販で注文していた品物が届き、運んでくれた人にその代金を渡しました。
知らない人に安心して代金を渡すのは信用が成り立っているからです。
億単位の価値のあるものの代金の払い込みを考えれば、その信用を裏付けるための仕組みは簡単でなく、
仕組みの維持には莫大な費用が掛かるであろうことが想像できます。この信用を銀行や国が支えているのです。
その信用維持の費用は、代金の払い込み時に上乗せされ、品物はそれだけ高くなります。
信用の維持を銀行や国家という権威が支える今の仕組みは、非常に高価なのです。
今の信用維持の仕組みは当然であると誰もが信じていました。
この信仰にも似た確信をIT技術を以て打ち砕いたのがブロックチェーンなのです。
考えてみれば、権威が裏付けするものは、取引の内容の記録でありその記録が正しいことの保証です。
すなわち、合意の上一度書かれた記録が二度と書き換えられないことです。
ブロックチェーンは記録の書き換え（改竄）の防止を、IT技術で成し遂げたのです。
ブロックチェーンの内容の説明に入ります。
ブロックチェーンは、多くの記録データの集まりを1ブロックと見立て、発生するそれらブロックをを次々と繋いでいき、
全体を保存するデータ保存の一種です。
何がすごいかというと、ブロックに一度書き込んだデータは事実上書き直す(改ざんする)ことができない仕組みになっていることです。
記録した内容に嘘がつけないから、内容の信用の基になるのです。
現在の経済システムでは、送金等に伴う信用の裏付けに多大なコストがかかるので、
このブロックチェーンという技術は経済システムを根本的に変えるであろうといわれています。
書き直せない理由の説明に入ります。
1つのブロックは、2つの部分からなっています。
部分1 ： 記録しておきたい内容：多くの文字からなっている
部分2 ： 1つ前のブロックのデータ（前の部分1＋前の部分2）に関連して決まる鍵（のようなもの）
部分2の決め方は、前のブロックデータにハッシュという処理をかけ、ブロックデータをある数値ｘに対応させます（たとえば、50ケタの数値）。
その数値ｘに部分2の値を作用させれば前もって決められた性質が現れるような部分2の値ｙを見つけ出します。
これが、部分2の値(鍵)となります。
ブロックチェーンの工夫は、この部分2のカギを見つけ出す作業が膨大な手間(コスト)がかかるように設定されていることです。
これを見つけるには膨大な数の候補を一つ一つ試すしか手段がなく、多くの捜索者が分散して捜索作業を行います。
捜索は金鉱から金を掘る作業をイメージして、マイニングと呼ばれます。
見つかった部分2の値ｙはナンスと呼ばれます。（そして、運よく見つけた人がそのブロックの設定に貢献したとして報酬をもらうのが、
ビットコインの仕組みです。）
つぎに、この仕組みが改ざんを防止する詳しい理由を述べましょう。
次の説明図Aは、今までの説明を図示したものです。
いま、下の図Bにおいて今のブロックをa1とし、前のブロック（a0）の記録内容に改ざんが行われたとしましょう。
すると前から辿って今のブロック(a1)に来たとき、ブロック(a1)から見れば前のデータに基づくハッシュ値ｘは以前のものと異なります。
そこで、自分のところ(a1)に記録されているナンス値はこれに合わず、前(a0)のデータが以前とは違ったことが分かります。
すなわち、改ざんされたことが分かります。
（注：ナンス値は見つけ出すのはコストがかかるが、正当な値かどうかの検算は容易）
改ざんの場合 後のブロックのナンスが合わない＝改ざんが判明
上の図で、a0の記録内容を改ざんしました。
a0の改ざんを強引に誤魔化そうとするには、a1のナンス値をa0の改ざんに合わせて計算し直すことになります。
これはコストがかかります。a1を修正すると、つぎにa2のナンス値が合わなくなります。
かくして、すべてのナンス値の再計算となり、膨大なコストがかかることになります。
改ざんを完了するには、分散化されて蓄えているすべてのブロックチェーンについて、この個々の改ざん作業を行う必要があります。
これは、事実上不可能なので、この不可能性がブロックチェーンの信頼性の基本となるのです。
ブロックチェインを式で表すと、その構造が明らかになります。
ブロックが 0 から始まって1，2，3，…,n とつながっているとしましょう。
一般にi期に発生した記録を
、i期のナンスを
とする。すると、次の関係があります。
これは、
今期のナンス値は、前期のデータ d(i-1) と前期に計算されたナンス値 c(i-1) （すなわち前期の全データ）のハッシュ値をまず計算し、
つぎにそのハッシュ値に対応するナンス値を算出する
ことの表現です。
関係式を漸化的に繰り返せば、次のようになります。
すなわち、i期のナンス値はそれ以前に発生したすべてのデータ系列ｄに依存しています。
ブロックの最後のナンス値は、それ以前に発生したすべてのデータに依存することになっています。
そこで、データを改ざんするときは改ざん以降のすべてのナンス値の再計算が要ることになります。
これは事実上工数の面から不可能です。さらに、分散された保存データ全てについても変えなければならず、改ざんは不可能となるのです。
ハッシュとは、あるデータ(通常長いデータ：key)を指定した範囲内のどれかの数値に対応させることです。
Keyを得て、それを範囲内のどこかに対応付ける関数Hをハッシュ関数といいます。
ハッシュ関数Hは、次のような性質を持つように工夫してあります。
（1）計算が容易
（2）計算値が与えられた範囲内にランダムに散らばること。
（3）keyが少しでも違えば、計算値は全く離れたものであること。
ハッシュはkeyに対応する内容をハッシュ値と関連付けた場所に格納するときに使われます。すなわち、keyの検索が非常に効率的になるのです。
異なったキー key1,key2 がたまたま同じハッシュ値になることがあります。これを衝突と呼びます。
衝突に対する対応策はいろいろ工夫がありますが、説明は省きます。
ナンス値は、前のブロックのデータを保全するカギに当たります。
これを算出するのが簡単であれば、壊れやすいカギに相当します。
頑丈なカギとは、保護すべきデータに対応するナンス値を算出するのに莫大なコストがかかることに対応します。
ここで、カギについての一般論に入りましょう。いま、考える対象は暗号を解くためのカギとします。
暗号の伝達には、送信者とその送信者が伝えたい文(平文)とそれを受け取る受信者がいます。
送信者は平文を、第3者が見ても分からないように、あるカギで暗号化し受信者に伝えます。
受信者はこれをあるカギで元の文に修復します。
暗号化および複合化に用いるカギについて、次の2つの方式があります。
共通鍵方式
公開鍵方式
共通鍵方式
暗号化と復号に同じ（共通の）鍵を使うもので、通常の方式です。
この方式では暗号文を受け取る対象が多くなると、すべての対象に同じ鍵を配らねばなりません。
その時、どこからか一つでも鍵が漏れると、暗号システムは全体が崩れます。
すなわち問題は、システムの維持が大変難しいことです。
公開鍵方式
共通鍵暗号に生じる鍵配送問題は、送信者と受信者の両者がただ1つ共通の鍵を用いるために起きる問題です。
その解決のため、両者が異なる鍵を用いる方法、すなわち公開鍵暗号が考案されました。
これは、鍵Aで鍵をかければAでは開かず鍵Bで開くことができ、鍵Bで鍵をかければBでは開かず鍵Aで開けることができるものです。
このような鍵のシステムができると、ABいずれかの一方を公開して、次のような巧妙な暗号を保持するシステムを作ることが出来ます。
1. 通信を受ける者（受信者）は自分の公開鍵（暗号化のための鍵）P（ABの何れか） を全世界に公開する。
2. 受信者に対して暗号通信をしたい者（送信者）は、公開鍵 P を使ってメッセージを暗号化してから送信する。
3. 受信者は、公開鍵 P と対になる秘密鍵（復号のための鍵）S（PがAならSはB,PがBならSはA） を密かに持っている。
この S を使って受信内容を復号し、送信者からのメッセージを読む。
4. 暗号通信を不正に傍受しようとする者（傍受者）が、送信者が送信した暗号化されたメッセージを傍受したとする。
傍受者は、公開鍵 P は知っているが、秘密鍵 S は受信者だけが知っている情報であるので分からない。
P から S を割り出すことは（計算時間の点から）極めて難しい。そのため、暗号文を復号することはおよそできない。
このような仕組みを、公開鍵暗号といいます。
公開する鍵Pは秘密にする必要がないので、共通鍵システムの場合に大変なコストがかかった維持の問題が解決されています。
RSA暗号:典型的な公開鍵暗号方式
公開鍵暗号にはさまざまな方式があります。ここでは典型的な公開鍵暗号方式であるRSA暗号方式を説明しましょう。
この方式の安全性は素因数分解の困難性に基づいています。
大きな素数 p, q が与えられたとき、その積 n = pq を計算することは容易です。
しかし逆に、素数の積 n が与えられたとき、n = pq と素因数p,qに分解することは難しい。
素数同士の組み合わせを、一つ一つ調べねばならないからです。
ここで暗号化には n を、復号には p か q を必要とするようなうまい仕組みを作っておきます。
そして、n を公開鍵として公開します。傍受者は n から p,q を割り出そうとするでしょうが、これは時間が掛かりすぎて現実的ではありません。
軍事用暗号の場合、専用のコンピュータで専門のプログラムを走らせても解読には数億年～数兆年を要するように設計されています。
これは、事実上解読不可能と言ってよいものです。
素数の創り方
数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではありません。
このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用います。
こういった自然数の生成は高速に行える確率的素数判定法によりふるいをかけ、それをパスした自然数(確率的素数)を用いいます。
確率的素数は、判定回数を増やすことで素数でない確率を極めて低くすることができます。
以上でブロックチェーンとそれを構成する主な要素の説明を終えます。
ブロックチェーンでは、暗号の解読が難しいことが前提で、現在の技術体系ではこの前提は成り立ちます。
しかしながら、量子の世界ではこれが解けるかもしれないのです。
量子暗号について解説も用意しておきましょう。
1. 二重性(相補性)
微粒子の世界では非常に不思議なことが起こっています。
光は小さな粒の性質と波の性質とを併せ持つことが知られています。粒が波のように振動するのではありません。
粒と波の2つの性質が共存するのです(二重性あるいは相補性)。
この意味が本当に分かる人はいないといわれています。
我々の目にする世界には思い当たらない振る舞いですが、微粒子の世界では現実にあるのです。
カントは理性への限界を指摘し、理性の理解できない事柄をいくつか挙げています(時間や空間の無限性の有無等)。
微粒子の世界における挙動は、カントの言う理性の限界以上に通常の理性に反しており、微粒子世界の力学はその現実の上に構築されているのです。
これから不思議な世界を覗きましょう。
いま、半透鏡と鏡を組み合わせて次のような装置(干渉計)を作ります。
半透鏡とは、入ってきた光を半分反射し半分通過させるもの、鏡は反射のみを行うものです。
常識的に考えれば、光は半透鏡1で半分ずつ２つのルートに分かれます。
各ルートの光は半透鏡2でそれぞれ分かれながら、AおよびBの2つの方向にそれぞれ合わされます。
したがって、AとBのそれぞれでちょうど半分ずつ観測されるであろうと推察されます。
ところが違います。
実際の観測では、ルート1とルート2の距離が厳密に同じならば、Aからしか観測されません。
この理由は、光の波としての性質が作用するからです。
すなわち、波としての反射に伴い2つのルート間に波の位置のずれ(位相のずれ)がおこり、半透鏡2で各ルートの光が合わさるとき、次の図のようにずれが重なるからです。
この波としての性質の働きの存在が、この場合光がAからしか観測されない理由となります。
光は粒子という証拠もありますが、同時にこのように波としか考えられない現象もあります。
この波と粒子の二重性は、確かにあるとしか言いようのないものですが、普通の理性ではとても理解できません。
参考（位相について）
波は振動するのでいろいろな位置の状態があります。これを位相と呼びます。
2つの波の位相は、ずれる場合があります。次の図の波は、位相が波長の1/4ずれたものです。
位相が半波長ずれた2つの波が重なれば、互いに打ち消しあい波が現れません。
極微の世界には、この二重性を超えたもっと不思議なことがあります。それは、重ね合わせという現象です。
二重性の説明での装置(干渉計)をもう一度使い、今度はその装置に光子1個を入れることを考えます。
1個の光子は最終単位ですから、これは半透鏡に当たっても半分にはなりえません。
したがって、1粒としては2つのルートのいずれか一方しかとれないはずです。
ルートの一つに観測計を入れて観測すると、その道を通ったか通らないかのいずれかが分かります。
何回も測れば、2つの道のそれぞれを通る確率が均等に0.5であることが分かります。
しかしです。経路に観測器を入れることなし（すなわち、観測せず）に最終結果を測れば、光は何度測ってもAからしか観測されません。
粒子は1粒なのです。どちらかのルートしか通れないはずです。
それならば、AあるいはBで半々に観測されるはずです。しかし、実験結果は違うのです。
多くの粒子(光子)を入れる場合、光跡はルート1とルート2に半々に分かれ、それらが波の性質を持つので2つのルートによる位相の差の合成として、
結果がAからしか観測されないと理由づけることが出来ます。
しかし今回は粒子は1個なのです。1個でもAからしか観測されないという事実は、2つのルートを波として同時に通ったとしか考えられません。
すなわち観測しなければ、1つの粒子は2つのルートを同時に通る波の重ね合わせ状態にあると考えれば理由が付くのです。
これは普通の常識では理解できません（おそらく、誰も）。
粒子を観測 → ルート1、ルート2の何れかにある1つの粒子の確認
観測しない → 粒子は2つのルートに同時にある重ね合わせ状態
いま、微粒子は0か1の2つの状態の内いずれかをとるとします。
この1つの微粒子が重ね合わせの状態にあるときは0と1の状態に同時にあることになります。
このような各々重ね合わせにある微粒子が2つあるとき、それらは次のような2**2＝4つの状態を同時にとるものとなります。
同様に、6個の重ね合わせにある微粒子は26＝64個の次のような状態を同時にとるものとなります。
模様で表せば、次のようになります。
観測すると、この中の1つが偶然により選択されて現れます。
ｎ個の微粒子の重ね合わせ状態は、なんと2ｎ個の状態を同時にとっているのです。
ｎが10のときは210で約1000、ｎが20のときは220でなんと約100万の組み合わせ状態を重ね合わせているのです。
たった20個の粒子で、それが重ね合わせの状態にあるなら100万のあらゆる組合せを含んでいるのです。
量子コンピューターは、量子の重ね合わせの特質を利用するものです。
物があるかどうかは、見ればわかります。見るということは、光を当て反射した光子を目で感知することです。
ところが光子の重ね合わせの性質を考えれば、光子を物に当てずに物の存在を確認できる場合があるのです。
いま、光子1個をおなじみの干渉計に入れるとします。
ルート1とルート2の距離は厳密に同じに調整されているとしましょう。
この上で、物をルート2上に置いたり置かなかったりするとして、A方向あるいはB方向での光子の観測について考えます。
（1） 物が置かれていないとき
入力された1個の光子は半透鏡1により2つの経路の重ね合わせになり、それが合わさって干渉の末Aからしか観測されません。
これはすでに分かっていることです。すなわち、物がなければAから観測されます。
（2） ルート2上に物を置いたとき
物が置かれているかどうかは、粒子がぶつからねば分かりません。そこで、1個の光子は粒子として次のようにふるまうと考えられます。
（1） 確率1/2でルート1を選ぶ。
このときは、粒子は鏡で反射され半透鏡2で確率1/2で通過（すなわちAで観測）し、残りの確率1/2で反射(すなわちBで観測)する。
（2） 確率1/2でルート2を選び、置かれているものに当たる。
このときは、光子はものに反射してAあるいはBのいずれにも達しない。
以上より、観察して起こり得ることは次の3つです。
（1） AでもBでも観察されない
これは、物が置かれていた証拠です。
（2） Aで観察された。
これは、次の2つの何れかです。
1） 物が置かれていなかった
2） 物が置かれており、光がルート1をとりかつ半透鏡2を通過した。
（3） Bで観察された。
これは、物が置かれており、光がルート1をとり（光子は物に当たっておらず）かつ半透鏡2を反射した。
すなわち、Bで光子が観測された事実があれば、物がありしかも光がものに当たっていない場合です。
Bで観測されたという事実は、物自体の観測をせずに物があることを示す証拠となっています。
それを見ないでかつその物の存在の証拠となっているのです。不思議なことです。
重ね合わせとは、多くの異なった状態が同時に存在することです。
これは、われわれが経験するマクロな世界では、理性的には考えられないことです。
しかし、極微の世界では存在すると考えざるを得ないのです。
この重ね合わせ状態を観測すると、多くの状態の一つが現れます。
その頻度は、多くの状態のそれぞれが波としてもつ振幅に依存します。
すなわち、重ね合わせ状態を見ようとすれば、何が現れるかは確率的であり確定的でないのです。
重ね合わせ状態をインプットとする場合、その多くの状態に対する計算は一度に行なわれます。
しかし、結果も重ね合わせ状態なので、観測の結果得られるものは重ね合わせ状態の一つで、欲しいものが見られないという致命的な欠陥があります。
量子コンピューターとは、この致命的な欠陥を非常に巧妙な手順で補い、ものすごい計算効率をとりだす方法なのです。
以下に、検索と素因数分解についての量子的な方法について述べましょう。
4.１ 量子検索
いま、ファイルに多くのデータ(データ数n)が蓄えられているとします。
検索とは、ある特定のデータaを指定して、それをファイルの中から見つけ出す作業を指します。
ファイルに蓄えられているデータの追加削除がないとき（すなわち、ファイルデータが安定しているとき）は、
ファイルの並びを検索のカギとなる内容に従って整理(ソート)しておきます。
この整理されたファイルから特定のデータaを探すには、非常に効率よく行える方法があります(検索はlog(n)のオーダー：2分探索という)。
しかし、蓄えるファイルへのデータの追加削除が非常に激しいときは、そのたびにファイルを整理状態に組み替えねばなりません。
この作業は大変な手間がかかり、実際的ではありません。
都度の整理を避ければ、データはファイルに乱雑に積み重ねられたような状態にあります。
ここで考える検索は、このような乱雑な内容のファイルが対象です。
ファイルにｎ個のデータがあるとします。
この中にある aというデータを探します。
データの並びに規則性がないから、これが求めるaであるか一つ一つ調べるしか方法がありません(順次検索)。
aは最初で見つかることも最後で見つかることも同様に起こり得ます。
したがって、見つけ出すに要する検索回数は (1+n)/2 すなわち 約 n/2 と考えます。
データ数ｎが大きいとき(例えば100万)は、この平均検索回数 n/2 は大変な回数です。
量子アルゴリズムを用いてこの問題に対処しようとする試みが研究され、グローバーという人がうまい方法を発見しました。
以下、この検索アルゴリズムについて述べましょう。重ね合わせ状態から巧妙に情報を加工して、有用な知識を取り出す方法です。
グローバーの検索アルゴリズムの手順
ファイルにｎ個のデータがあるとします。
File = ( d(1), d(2) , ... , d(n) )
データの番地を指す量子アドレスを、つぎのようにｍビットで表します。
量子アドレスビット = ( a(1), a(2), ..., a(m) )
今、問題を複雑にしないため、データ数 ｎは ｍビットで丁度表せるとします。
問題は、あるデータ ｂ を指定して b = a(k) なる ｋ（すなわち ｂ と一致するもの） を見つけることです。
手順1 すべての量子アドレスビットを0に設定する。
手順2 量子アドレスを重ね合わせの状態にする。すると、ｍ個の各ビットは0と1の重ね合わせの状態であるから 2**m = n の
データのすべてのアドレスを指す大きさになる。
量子アドレス ： (0,0,0,…,0),(0,0,0,…,1),…
,(1,1,1,…,1) の重ね合わせ
この重ね合わせのアドレスの各々は 
の振幅を持つ波で、観察すると振幅の2乗（すなわち1/n）で表される確率で選ばれる。
手順3 量子アドレスビットに量子データベース回路を作用させる。
この回路は、ｂを指定して、b = a(k)
すなわち、位相を反転することでその位置ｋに印をつけるのである。
（ここで、その反転した位相を探すことを思いつくが、それにはデータ総数ｎのオーダーの検索工数がかかり意味がない）
手順4 量子アドレスビットに折り返し量子回路を作用させる。
この折り返し回路とは、確率振幅の平均値に対して各状態を折り返す操作である。
この結果、次のようになる。
(A) では a(k) 
より少し下がる。図では誇張して書いてある。
ｎが非常に大きい数なので実際はほとんど下がらない。
（B) では折り返し後、平均を中心に反転するので、 a(k)は約 
の高さになる。
折り返すごとに、全体の平均の2倍ほど
全体の平均は初めほとんど下がらないが、繰り返しが多くなると次第に小さくなる。したがって、a(k)
a(k)
すなわち、観測して選ばれたデータがｂに一致するものであることがわかる。
以上の手順により、順次に探せばｎのオーダーの検索回数を
グローバーの手順を文章で表せば、次のようになります。
「アドレスビットを重ね合わせ状態にして、探索の全域を覆うようにする。
それに量子データベース回路を作用させる。
この回路は、量子アドレスビットの合致した位置の位相を反転する。
その後、量子アドレスビットに折り返し量子回路を作用させ、重ね合わせ状態の合致位置の振幅を拡大する。
この折り返し操作を繰り返し、合致位置の振幅拡大を繰り返す。
振幅が大きくなることは、観測すればその位置が見つけやすいことを意味する。」
4.2 量子素因数分解 ショアのアルゴリズム
大きい数の素因数分解は非常に時間がかかります。この性質が、今の暗号システムの安全性を担保する基礎となっています。
しかし、量子の世界の重ね合わせの性質を使えば、素因数分解も時間のかからないものになるといわれています。
暗号システムにとっては大問題です。
以下では、量子暗号システムについて述べましょう。
アルゴリズムの構造
N ：分解対象の数値
x ：Nと共約数を持たないNより小さい数
問題：
（ｒは偶数）であるｒを見つけたい。
見つかると、
これは、左辺の2つのいずれかがNの因数であることを意味します。
このとき、ｒの特性として、
これは、
すなわち、ｒ を見つけるのは 
フーリエ展開とは、周期的に変化する関数に周期関数 sin,cos を当てはめ、その関数の持つ周期を見つけ出す数学的技法です。
周期がｒなら、ｒの倍数の波が取り出され、それ以外の展開係数は0であることが推察できます。
フーリエ展開例(参考)
つぎの図は、与えられた周期関数をいくつかの波の集まりとして表現(フーリエ展開)したものです。
量子素因数分解の手順
N ：分解すべき数
手順に次の数を使います。
ｑ ： ｑ＞N なる数
量子レジスタ 
のように表現します
a ： 量子アドレスビット
0からq－1までのすべての数字を表せるもの
ｂ ： 0からNまでの数が表せる大きさ
求めたいものは、ｂに重ね合わせ状態で記録したデータの周期ｒです。
手順1 量子レジスタの初期セット 
0にセット
手順2 aを重ね合わせ状態にする。0からq－1の数字の重ね合わせとなる。
量子レジスタa,bの重ね合わせ状態の表現 
手順3 
の余り計算値をｂにいれる。
量子レジスタｂには次の内容が重ねあわされている。
手順4 量子レジスタｂの観測
観測の結果、ある
るアドレス
は
そこで、アドレス部分aにはそのような周期ｒだけ離れた位置の重ね合わせが記録される。
aの非ゼロの間の距離は一つ一つ調べればわかることだが、その回数は
Nが40ケタならば調べる回数は20ケタになる。
1秒に1010回の調査をするとしても20ケタの調査は1010秒かかることになる。
1年は60×60×24×365秒=3.15×107秒なので300年はかかることになる。したがって、単純に調べることは不可能である。
手順5 量子レジスタa（アドレス）に量子フーリエ変換をかける。
その結果、q/r の整数倍のところに確率振幅(存在率を示す)が現れる。
したがって、この結果を観測すればλを整数としてλq/r が得られる。
得られた値をｑ（既知数）で割ると λ/r
ｒの判定
奇数の時 → やり直し
偶数の時 → 
この手順はうまくいかないときもあるが、log(log(r))のオーダーの繰り返し回数で見つかることがわかっています。
ショアの手順の要点
「周期ｒを求めるために、剰余値の計算を行う。
その剰余値ｂはｒの周期関数なので、その周期を求めるためフーリエ展開を行う。
結果の周期（重ね合わせ状態で記録されている）を観測すれば、それはｒと関連するものが得られる。
その情報を加工して、ｒを算出する。
ｒを用いて素因数を求める。」
