臨
9 雪 αoo1
§
9
0．0001
1e−005
1e−006
0 50 100 150
200
250「egister 1
図5．3：出力。が観測される確率（対数スケール）
付録 プログラム
Shorのアルゴリズムにもとつく15の素因数分解プログラム．量子コンピュータの 動作をC言語によりシミュレートする．
／／ Program na皿e 四quantum．c闘
〃begin
＃include ＜stdio．h＞
＃include ＜math．h＞
＃inc：Lude ＜stdlib．h＞
＃defille CN 15
＃define PCA 7
＃define PSQ 243
＃defille PI
＃define SEED 19933．14159265358979
プログラムの本体は quantum．c である．
／／ Composite Number lln四 ＝ target for farctoring
／／Pick a ra皿dom integer 闘a曾l co−prime to n
／／ Pick a smooth 脇q曾8 ／／Pi
／／ Seed for rand function
int find＿period＿quantumO，find＿period＿classicO，measure＿reg20，
greatest．c。㎜。n．divis。rO；
void initialize O，fourier＿transfor皿0，measure＿regiO，
． 〜：ontinued＿fraction＿expansion O；
■nt t■mes●
タ
unsigned long int reg1［PSQ］，reg2［PSQ］，f：Lug［PSQ］，q［PSQ］，samp＝Le；
float ra豆0；
lo丑g idum；
double prob［PSQ］；
F工LE ＊fp；
／／ begin of 皿ain
int main（ void ） ｛int TIMES，period，counter，idum；
TIMES＝（i且t）log（PSQ）；
idum＝SEED．
ウ ran（＆idum）；
fp＝fopen（鯛data．tx七曾8，鱒wll）；
printf（㈹Composit n1』nber ＝ ％8d＼旦 Co−prime intege：r冨％8d＼n Slnooth number ＝ ％8d＼n seed ＝ ％8d＼n
fp。i。t垂（茎講。鑑P織n≧躍・P三A織SEED・TエMES）；
Co−prime integer ＝ ％8d＼n Smooth number ＝％8d＼n
seed 富 ％8d＼nt imes ＝ ％8d＼n＼n量。，CN，PCA，PSQ，SEED，T工MES）；
39
付録プログラム
40
／／ repeat log（q） times belov
for（times＝0；times〈T工MES；times＋＋）｛
printf Cl［％4d］＼n謄㌧times＋1）；
fprintf（fp，曾1［％4d］＼n曹㌧times＋1）；
iロitializeO；
priLtf（IIPeriod classic 3 ％d ＼丑量㌧find＿period＿classicO）；
fprintf（fp，脚Period c：Lassic ＝ ％d ＼nI㌧find＿period＿classicO）；
counter羅measure＿reg20；
fourier＿transform（counter）；
measure＿reg10；
printf（闘Measure reg1 ＝ ％d＼1ゴ㌧sa皿ple）；
fprintf（fp，鴨Measure reg1 ＝％d＼n，㌧sample）；
if（sample＝＝O）｛
printf（loFailed l （Measured value is O）＼n四）；
fprintf（fp，瞬Fai：Led豊 （Measured va］．ue is O）＼nll）；
｝ else｛
continued＿fraction＿expaロsion（sample，PSQ）；
period＝find＿period＿quantum O；
printf（量lPeriod．quantum ＝ ％d ＼n四，period）；
fprintf（fp，llPeriod quantum ＝ ％d ＼n薯㌧period）；
if（period％2＝＝1）｛
priロtf（11Failed璽 （Period is odd）＼n四）；
fprintf（fp，四Failed！ （Period is odd）＼nl，）；
｝
else if（reg2［period／2］＝＝一1）｛
printf（巳1Failedl （a＾｛Period／2｝＝一1）＼n鱒）；
fprintf（fp，四Failed！ （a＾｛Period／2｝＝一1）＼n睡）；
｝ else｛
printf（慶1a＾｛Period／2｝ ＝ ％d＼nl㌧reg2［period／2］）；
fprintf（fp，鱒a＾｛Period／2｝ ＝ ％d＼n8㌧reg2［period／2］）；
printf（願1GCD（ ％d ， ％d ） ＝ ％d＼n睡，
CN，reg2［（int）（period／2）］一1，
greatest．co㎜on−divisor（CN，reg2［（int）（peri。d／2）］一1））；
fprintf（fp，胴GCD（ ％d ， ％d ） ＝ ％d＼n四，
CN，reg2［（int）（period／2）］一1，
greatest＿common＿divisor（CN，reg2［（int）（period／2）］一1））；
printf（11GCD（ ％d ， ％d ） ．＝ ％d＼n四，
CN，reg2［（int）（period／2）］＋1，
greatest．co㎜on−divisor（CN，reg2［（int）（period／2）］＋1））；
fprintf（fp，mGCD（ ％d ， ％d ） ＝ ％d＼n四，
CN，reg2［（iロt）（period／2）］＋1，
greates七．co㎜on．divisor（CN，reg2［（int）（period／2）］＋1））；
｝ ｝
printf（1へn唖1）；
fpri且tf（fp，鱒＼1ゴ馨）；
｝
fclose（fp）；
｝
／／ end of main
付録プログラム
41
／／ initialize reg1， reg2， prob void initialize O
｛
■nt ■ ，
for（i＝O；i〈PSQ；i＋＋）｛
reg1［i］＝i；
｝
reg2［O］＝1；
for（i＝1；i〈PSQ；i＋＋）｛
reg2［i］＝re
g2［i−1］＊PCA％CN；
｝
／＊
for（i＝O；i＜PSQ；i＋＋）｛
prob［i］＝1／PSQ；
｝
＊／
｝
int measure＿reg20
｛
／／皿easure the state of reg2 int i，rd，counter；
rd竃（int）（PSQ＊ran（＆idum））；
fprintf（fp，11⊃4easure reg2 ＝ counter＝O・
り
fo「（1；ぞ麟呈1≧｝l12［。d］）｛
counter＋＋．
つ f＝Lug［i］＝1；
｝ else｛
f＝Lug［i］＝O；
｝ ｝
return（C◎un七er）；
％d＼n量1，reg2［rd］）；
｝
／／ fourier transform ＆ result
void fourier＿transform（int couロter）
｛
int i，j，ac；
double re，im，tota：L；
／／
total＝0；
for（i＝O；i〈PSQ；i＋＋）｛
re＝0；im＝0；
fprintf（fp，量1［reg1 ＝ ％4d］＼n闘，i）；
for（j冨O；j〈PSQ；j＋＋）｛
if（flug［j］＝＝i）｛
ac＝2＊（j＊i％PSQ）；
re＝re＋cos（（P工＊ac）／PSQ）；
止山呈ll懸蓋／ES舞乙；／％d Pi，。。．％f， im．％f＼nll，
ac，PSQ，cos（（PI＊ac）／PSQ），sin（（PI＊ac）／PSQ））；
fprintf（fp，量1％f ％f＼nl蓼，
cos（（PI＊ac）／PSQ），sin（（PI＊ac）／PSQ））；
｝ ｝
付録プログラム
／／
prob［i］＝（re＊re＋im＊im）／（counter＊PSQ）．；
total冨total＋prob［i］；
if（prob［‡］〉＝0．00）｛
fp士intf（fp，鵠reg1 冨％4d， prob ＝ ％f＼nu，i，prob［i］）；
fprintf（fp，11％4d ％f＼nll，i，prob［i］）；
｝
fprintf（fp，鱒Total of re ＆ im ％f ％f＼n曾㌧re，im）；
｝
printf（四Total of Probabi：Lity 罧％f＼n巳㌧total）；
fprintf（fp，朋Total of Probability ＝ ％f＼n曹㌧tota1）；
｝
v◎id measure＿reg10 ／／measure the state of reg1
｛
illt i・
り
double pr，subtota1；
pr＝（double）（ran（＆idum））；
subtotal＝0・
り
for（i冨O；i＜PSQ；i＋＋）｛
subtQta1＝subtotal＋prQb［i］；
if（subtotal＞pr）｛
samp：Le＝i；
break；
｝ ｝
｝
／／ continued fraction exPansion
v◎id continued＿fract ion＿expansion（int numerator，int deno皿inato：r）
｛
illt i，residue；
for（i＝O；i＜PSQ；i＋＋）q［i］＝o；
f。「（と〒91皇ぞ撒盆臓9δ諾1蓋。minat。r）、
residue＝numerator％denominator；
numerator＝denominator；
denominator＝residue；
／／ printf（1露q［％d］＝％d＼nl㌧i，q［i］）；
｝
｝
／／
int
｛
find period 曾lr闘 by quantum method find．＿period＿quantum O
と器b圭6P9：9｝・P2・qO・q1・q2・pe「 od；
b＝（double）1／（double）（2＊PSQ）；
1§illlll！lo］；
for（i冨1；q［i］1＝O；i＋＋）｛
P2＝q［i］＊P1＋pO；
q2＝q［i］＊qi＋qO；
if（q2＞＝CN） break；
pO＝p1；p1＝p2；
42
付録プログラム
43
／／
／／
／／
qO＝q1；q1＝q2；
printf（llP／Q ＝ ％d ／ ％d＼nI㌧P2，q2）；
printf（Ilc／q＝％d ＼n，1，sample［times］）；
printf（唖1：Lambda／r ＝ ％f ＼ロu，（doub：Le）P2／q2）；
a＝（double）p2．／q2一（double）sa皿ple／PSQ；
pri豆tf（量1％10f ％10f ％10f ％10f四，
a，b，（double）1／（2＊CN＊CN），（double）1／（2＊period＊period））；
fprintf（fp，四％10f ％10f ％10f ％10f亀1，
a，b，（double）1／（2＊CN＊CN），（double）1／（2＊period＊period））；
if（一a〈b ＆＆ aくb）｛
printf（四 〇＼nll）；fpri且tf（fp，曾l o＼n闘）；
｝
e工se｛ ． 一
printf（四 x＼1ゴ1）；fpri且tf（fp，四 x＼n簡）；
｝
period冨q2；
｝
return（period）；
｝
／／ find period 響Irll by classical method，
／／ i．e． find first 駐1r鱒 such that 闘a＾r ＝ 1， r l＝ OI1
／／ which will be used for checking the answer．
int find＿period＿classicO
｛
iロt i，periodclassic；
fo「（1；1麟呈1≧11！
periodclassic＝i；
return（periodclassic）；
｝ ｝
｝
／／ greates t；common divisor
int greatest．co㎜on．divis。r（int c，int d）
｛
int residue；
while（d！＝0）｛
residue＝c％d；
c＝d；
d＝residue；
｝
return（C）；
｝
／／elld
乱数発生には次の関数 ran．c を利用した［18］．
／／ Progra皿name 四ran．c四
／／begin
＃define 工A 16807
＃defille IM 2147483647
付録プログラム
44
＃defiコe AM （1．0／工M）
＃define IQ 127773
＃define 工R 2836
＃define NTAB 32
＃define ND工V （1＋（IM−1）／NTAB）．
＃defiロe EPS 1．2e−7
＃define RNMX （1．0−EPS）
float 「aL（long ＊idu阻）
｛
int j；
10ngk；
static lo且g iy＝0；
static long iv［NTAB］；
float temp；
if （＊idum 〈＝ O ll liy）｛
if （一（＊idum） 〈 1） ＊idum＝1；
else ＊idum ＝ 一（＊idum）；
for （j＝NTAB＋7；j＞＝O；j一一）｛
k＝（＊idum）／IQ；
＊idum＝工A＊（＊idu皿一k＊工Q）一一工R＊k；
if （＊idum ＜ 0） ＊idum ＋＝ 工M；
if （j 〈 NTAB） iv［j］ ＝ ＊idum；
｝
iy＝iv［0］；
｝
k＝（＊idum）／工Q；
＊idum＝工A＊（＊idum−k＊IQ）一工R＊k；
if （＊idu皿 〈 0） ＊idum ＋＝ IM；
」＝iy／NDIV；
iy器iv［j］；
iv［j］＝ ＊idu皿；
if （（temp＝AM＊iy） ＞ RNMX） returロ RNMX；
else return te皿P；
｝
／／end
引用文献
［1］D．Deutsch， （〜駕αη施m 77｝εoη1，舌んεα協rcん一理r伽g Pr￠ηc￠μeαη4診んeση勿er3αZ 9錫αη伽mOom郷オe〆， Proc． R． Soc． Lond．， Vo1．A400， pp．96−117，1985。
［2］A．Ekert and R． Jozsa， （2駕αη施m com郷診α伽ηαη43ん。而ル。診。幅πgαな10短孟んm，，
Reviews of Modem Physics， Vb168， No．3， pp．733−753，1996．
［3］福元信之，「連分数の研究」，兵庫教育大学修士論文，平成8年度．
國濱頼光，「因数分解と素数判定」，兵庫教育大学修士論文，平成3年度．
［5】井桁和浩，小澤正直，西野哲朗，細谷暁夫，竹内繁樹，北川勝浩，「特集量子コン ピュータ」，数理科学10月号，サイエンス社，1998．
［6］D．Kahn， Tゐe Oo4e6reαたer5，， Revised and Updated， Scribner，1996．
［7］木田祐司，牧野潔夫，「コンピュータ整数論」，日本評論社，1994．
［8］（原著）Neal Koblitz， オOour8e 2π1鴨励eγ跣eo卿侃d O瑠p舌og脚吻 ， Second Edition， Springer，1994．
（邦訳）櫻井幸一訳，「数論アルゴリズムと楕円暗号理論入門」，シュブリンガー・
フェアラーク東京，1997．
［9］A．K Lenstra， H．W． Lenstra，Jr．（eds．）， The Dθ勿e勿㎜e漉。弗んε亙錫勅er F鰯 3伽e，，Lect． Notes Math．1554， Springer−Vbrlag，1993．
［10］圓井大介，「連分数と恥rey数列」，兵庫教育大学修士論文，平成10年度
［11］水上勉，「素数定理とふるい法」，兵庫教育大学修士論文，平成9年度．
［12］中山泰和，「Lucas数列と素数判定」，兵庫教育大学修士論文，昭和62年度．
［13エ西川史郎，「Riema皿nのζ関数について」，兵庫教育大学修士論文，平成6年度．
［14］西野哲朗，「量子コンピュータ入門」，東京電機大学出版局，1997．
45