GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/pythontelem

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/samples/estimation

samples/estimation/EkeraHastadFactoring.qs

198lines · modecode

RawDownload
Latest commit unavailable.
1/// # Sample
2/// Resource Estimation for Integer Factoring
3///
4/// # Description
5/// In this sample we concentrate on costing quantum part in the algorithm for
6/// factoring RSA integers based on Ekerå and Håstad
7/// [ia.cr/2017/077](https://eprint.iacr.org/2017/077) based on the
8/// implementation described in
9/// [arXiv:1905.09749](https://arxiv.org/abs/1905.09749). This makes it ideal
10/// for use with the Azure Quantum Resource Estimator.
11namespace Microsoft.Quantum.Applications.Cryptography {
12 import Std.Convert.*;
13 import Std.Math.*;
14 import Std.ResourceEstimation.*;
15 import Std.Arrays.*;
16 import Microsoft.Quantum.Unstable.Arithmetic.*;
17 import Microsoft.Quantum.Unstable.TableLookup.*;
18
19 // !!! IMPORTANT !!!
20 // When computing resource estimtes from the VS Code plugin directly on this
21 // file, make sure that you set the error budget to 0.333.
22
23 @EntryPoint()
24 operation EstimateEkeraHastad() : Unit {
25 // Try different instances of the algorithm by commenting in and out
26 // the following lines. You can find more RSA numbers at
27 // https://en.wikipedia.org/wiki/RSA_numbers
28
29 // RSA-100 (330 bits)
30 EkeraHastad(330, 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139L, 7L);
31
32 // RSA-1024 (1024 bits)
33 // EkeraHastad(1024, 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563L, 7L);
34
35 // RSA-2048 (2048 bits)
36 // EkeraHastad(2048, 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357L, 7L);
37 }
38
39 /// # Summary
40 /// Main algorithm based on quantum phase estimation
41 ///
42 /// # Reference
43 /// [ia.cr/2017/077, Section 4.3](https://eprint.iacr.org/2017/077)
44 operation EkeraHastad(numBits : Int, N : BigInt, g : BigInt) : Unit {
45 let x = ExpModL(g, ((N - 1L) / 2L), N);
46 let xinv = InverseModL(x, N);
47
48 let m = numBits / 2;
49 use c1 = Qubit[2 * m];
50 use c2 = Qubit[m];
51 use target = Qubit[numBits];
52
53 let ne = 3 * m;
54 let cpad = Ceiling(2.0 * Lg(IntAsDouble(numBits)) + Lg(IntAsDouble(ne)) + 10.0);
55
56 // The algorithm uses the coset representation to replace modular
57 // addition inside MultiplyExpMod with regular addition.
58 use padding = Qubit[cpad];
59
60 ApplyToEach(H, c1 + c2);
61 InitCoset(N, target, padding);
62 MultiplyExpMod(g, N, c1, target + padding);
63 MultiplyExpMod(xinv, N, c2, target + padding);
64
65 Adjoint ApplyQFT(c1);
66 Adjoint ApplyQFT(c2);
67 }
68
69 // ------------------------------ //
70 // Modular arithmetic (constants) //
71 // ------------------------------ //
72
73 /// Window size for exponentiation (c_exp)
74 internal function ExponentWindowLength_() : Int { 5 }
75
76 /// Window size for multiplication (c_mul)
77 internal function MultiplicationWindowLength_() : Int { 5 }
78
79 // ------------------------------- //
80 // Modular arithmetic (operations) //
81 // ------------------------------- //
82
83 /// # Summary
84 /// Encodes register in coset representation
85 ///
86 /// # Reference
87 /// [arXiv:quant-ph/0601097, Section 4.1](https://arxiv.org/abs/quant-ph/0601097)
88 internal operation InitCoset(mod : BigInt, xs : Qubit[], padding : Qubit[]) : Unit {
89 use helper = Qubit();
90 let cpad = Length(padding);
91 let n = Length(xs);
92
93 let combined = xs + padding;
94
95 for j in 0..cpad - 1 {
96 Controlled IncByLUsingIncByLE([helper], (RippleCarryCGIncByLE, mod, combined[j..j + n - 1]));
97
98 ApplyIfLessOrEqualL(X, mod, combined[j..j + n - 1], helper);
99 }
100 }
101
102 /// # Summary
103 /// Computes zs *= (base ^ xs) % mod (for a large register xs)
104 ///
105 /// # Reference
106 /// [arXiv:1905.07682, Fig. 7](https://arxiv.org/abs/1905.07682)
107 internal operation MultiplyExpMod(
108 base : BigInt,
109 mod : BigInt,
110 xs : Qubit[],
111 zs : Qubit[]
112 ) : Unit {
113 let expWindows = Chunks(ExponentWindowLength_(), xs);
114
115 within {
116 RepeatEstimates(Length(expWindows));
117 } apply {
118 let i = 0; // in simulation this i must be iterated over IndexRange(expWindows)
119
120 let adjustedBase = ExpModL(base, 1L <<< (i * ExponentWindowLength_()), mod);
121 MultiplyExpModWindowed(adjustedBase, mod, expWindows[i], zs);
122 }
123 }
124
125 /// # Summary
126 /// Computes zs *= (base ^ xs) % mod (for a small register xs)
127 ///
128 /// # Reference
129 /// [arXiv:1905.07682, Fig. 6](https://arxiv.org/abs/1905.07682)
130 internal operation MultiplyExpModWindowed(
131 base : BigInt,
132 mod : BigInt,
133 xs : Qubit[],
134 zs : Qubit[]
135 ) : Unit {
136 let n = Length(zs);
137
138 use qs = Qubit[n];
139 AddExpModWindowed(base, mod, 1, xs, zs, qs);
140 AddExpModWindowed(InverseModL(base, mod), mod, -1, xs, qs, zs);
141 for i in IndexRange(zs) {
142 SWAP(zs[i], qs[i]);
143 }
144 }
145
146 /// # Summary
147 /// Computes zs += ys * (base ^ xs) % mod (for small registers xs and ys)
148 ///
149 /// # Reference
150 /// [arXiv:1905.07682, Fig. 5](https://arxiv.org/abs/1905.07682)
151 ///
152 /// # Remark
153 /// Unlike in the reference, this implementation uses regular addition
154 /// instead of modular addition because the target register is encoded
155 /// using the coset representation.
156 internal operation AddExpModWindowed(
157 base : BigInt,
158 mod : BigInt,
159 sign : Int,
160 xs : Qubit[],
161 ys : Qubit[],
162 zs : Qubit[]
163 ) : Unit {
164 // split factor into parts
165 let factorWindows = Chunks(MultiplicationWindowLength_(), ys);
166
167 within {
168 RepeatEstimates(Length(factorWindows));
169 } apply {
170 let i = 0; // in simulation this i must be iterated over IndexRange(factorWindows)
171
172 // compute data for table lookup
173 let factorValue = ExpModL(2L, IntAsBigInt(i * MultiplicationWindowLength_()), mod);
174 let data = LookupData(factorValue, Length(xs), Length(factorWindows[i]), base, mod, sign, Length(zs));
175
176 use output = Qubit[Length(data[0])];
177
178 within {
179 Select(data, xs + factorWindows[i], output);
180 } apply {
181 RippleCarryCGIncByLE(output, zs);
182 }
183 }
184 }
185
186 internal function LookupData(factor : BigInt, expLength : Int, mulLength : Int, base : BigInt, mod : BigInt, sign : Int, numBits : Int) : Bool[][] {
187 mutable data = [[false, size = numBits], size = 2^(expLength + mulLength)];
188 for b in 0..2^mulLength - 1 {
189 for a in 0..2^expLength - 1 {
190 let idx = b * 2^expLength + a;
191 let value = ModulusL(factor * IntAsBigInt(b) * IntAsBigInt(sign) * (base^a), mod);
192 set data w/= idx <- BigIntAsBoolArray(value, numBits);
193 }
194 }
195
196 data
197 }
198}
199