Periodenbestimmung der Funktion k -> a^k mod N mittels Fouriertransformation

Anwendung auf die Faktorisierung ganzer Zahlen (Shors Algorithmus)

with(numtheory):

omegalist := proc (m) # # Numerische Berechung der komplexen m-ten Einheitswurzeln # local omega; option remember; omega := exp(2*Pi*I/m); [seq(evalf(omega^k),k=0..m-1)]; end:

omegalist(16);

period := proc(N,m,a,p) # # N : die zu faktorisierende Zahl f\374r den Shor-Algorithmus # m : Potenz von 2 f\374r Fourier-Transformation (es sollte N^2 < m < 2 N^2 sein) # a : Element von Z_N, dessen Ordnung mod N # (= Periodenl\344nge der Funktion k -> a^k mod N) # bestimmt werden soll # p : Periode in der Fourier-Transformierten # # liefert die Wahrscheinlichkeit, dass Periode p gemessen wird # local ol; ol := omegalist(m); norm(map(evalf,collect(add(ol[p*k mod m + 1]*X^(a^k mod N),k=0..m-1),X)),2)^2/m^2; end:

testperiod := proc (N,m,a) # # Summe der Wahrscheinlichkeiten # add(period(N,m,a,p),p=0..m-1) end:

testperiod(17,32,5);

display_period := proc(N,m,a) # # Spektrogramm der Periodenmessung f\374r k -> a^k mod N # [seq([p,period(N,m,a,p)],p=0..m-1)]; plot(%); end:

Faktorisierung von N=35

Daten: a=2, m=256

display_period(35,256,2);

Beispiele f\374r Messwerte: y = 107, 159, 192, 213

convert(107/256,confrac,'cvgts');

cvgts;

convert(159/256,confrac,'cvgts');

cvgts;

convert(192/256,confrac,'cvgts');

cvgts;

convert(213/256,confrac,'cvgts');

cvgts;

order(2,35);

A := 2^(6) mod 35;

gcd(A+1,35);

gcd(A-1,35);

Faktorisierung von N=35

Daten: a=11, m=256

display_period(35,256,11);

M\366gliche Messwerte: y= 85, 171

convert(85/256,confrac,'cvgts');

cvgts;

convert(171/256,confrac,'cvgts');

cvgts;

order(11,35);

Dieser Wert ist f\374r die Faktorisierung nicht brauchbar!

Faktorisierung von N=55 Daten : a=3, m=512

display_period(55,512,3);

Beispiele f\374r Messwerte: y = 179, 410, 333, 359

convert(179/512,confrac,'cvgts');

cvgts;

convert(410/512,confrac,'cvgts');

cvgts;

convert(333/512,confrac,'cvgts');

cvgts;

convert(358/512,confrac,'cvgts');

cvgts;

order(3,55);

A := 3^10 mod 55;

gcd(A+1,55);

gcd(A-1,55);