This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained

• how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1),
• how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1),
• how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP,
• how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation,
• how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP,
• how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and
• how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated.

It is furthermore for example explained

• how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP,
• how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and
• that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad.

The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.

Ifrågavarande avhandling innehåller en samling effektiva kvantalgoritmer samt klassiska för- och efterbehandlingsalgoritmer för en rad olika tal- och gruppteoretiska problem med konkreta kryptoanalytiska tillämpningar. Fokus ligger mer specifikt på heltalsfaktoriseringsproblemet (IFP), på det diskreta logaritmproblemet (DLP) och på problemet att bestämma ordningar (OFP), samt på vissa viktiga variationer av dessa problem. Exempelvis förklaras det

• hur OFP och fullständig IFP kan lösas effektivt i en körning av en reducerad version av Shors algoritm för OFP med mycket hög sannolikhet, vilket styrks med en nedre gräns på sannolikheten som är 1 − o(1),
• hur kort DLP i grupper av okänd ordning kan lösas effektivt och med ett övertag över Shors algoritm för DLP (som dessutom kräver att ordningen är känd), vilket styrks med en nedre gräns på sannolikheten att lyckas i en körning, där sannolikheten är 1 − o(1),
• hur RSA IFP kan lösas effektivt och med ett övertag över Shors algoritm för IFP, genom att reducera RSA IFP till kort DLP,
• hur DLP heuristiskt kan lösas effektivt, och med hög sannolikhet som är 1 − o(1), i en körning av en reducerad version av Shors algoritm för DLP som medger effektiv implementation,
• hur DLP kan lösas i grupper av okänd ordning, såsom Schnorrgrupper, genom att samtidigt lösa OFP och DLP till lägre totalkostnad men högre kostnad per körning jämfört med att först lösa OFP och därefter DLP,
• hur avvägningar — mellan antalet gruppoperationer som evalueras på kvantdatorn i varje körning och antalet körningar som krävs — kan göras i alla tidigare nämnda algoritmer, samt
• hur alla tidigare nämnda algoritmer kan simuleras effektivt klassiskt, för godtyckliga stora kryptologiskt relevanta probleminstanser, när lösningen till instansen är känd, vilket möjliggör skarpa skattningar av antalet körningar som krävs när avvägningar av tidigare nämnda slag görs.

Härutöver förklaras det exempelvis

• hur Regevs nya kvantalgoritm för IFP kan utökas till DLP och OFP, vilket leder till i) en reduktion av kretsstorleken och kretsdjupet med en faktor jämfört med Shor för dessa problem i , för N ett n-bitars heltal, på bekostnad av att körningar krävs, samt till ii) vissa förbättringar av Regevs ursprungliga algoritm för IFP,

• hur ovan nämnda algoritmer kan simuleras effektivt klassiskt, för stora probleminstanser på särskild form som är klassiskt lösbara, samt

• att Regevs klassiska efterbehandling, och den för våra utökningar, är robusta mot att en godtyckligt stor andel < 1 av körningarna är felaktiga.

Ovanstående har följdverkningar för kryptologi som baseras på IFP och DLP — inbegripet men inte begränsat till välanvända scheman såsom RSA, DSA och Diffie–Hellman. Algoritmerna i den här avhandlingen är alla derivat av, och gör alla betydande förbättringar av, Shors banbrytande arbeten. Några av bidragen är gemensamma arbeten med andra författare.