Shorのアルゴリズムって、こういう感じ？

良くわかってないんだけど・・・

６月２１日、
マルレク・サブゼミ 「3時間で学ぶ Shorのアルゴリズム入門」
https://shor.peatix.com/

に行ってきた。結局、こういう風に聞こえたんだけど、あってる？
（たぶん、あってないけど、キーワードは抑えている気もするので、参考まで・・・）


Shorのアルゴリズム→結局、素因数分解をするアルゴリズム？

ある数のN乗をある数で割ると、ｋが１，２，３、・・・と増えるに従い、
割った数のあまりは、ある特定の値しか出てこない、
つまり、周期性を持っていることに気づく。
→これをフェルマーの小定理っていうんだって！東大の大学院を受験したとき、これを
　試験場で気づき、そこから問題解いてたら、時間足らなくて落ちたので、多分、東大の
　大学院行くような人は知っているんだろう・・・

この周期性を使って、素因数分解を解く。

つあり、素因数分解はあるかず＊あるかずで表すけど、
　　一方を上記の「割る数」にして
　　他方を上記の周期としてもとめるわけ。


具体的には、
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1452-24.pdf
の２０７ページの上のほうに書いてある１～６をする。
量子コンピューターを使うのは、３のところ