The Mathematical Shape of Shor's Algorithm

This note treats the quantum procedure as a black box. Its purpose is to explain the algebraic information that Shor's algorithm recovers and why that information compromises RSA and elliptic-curve discrete-logarithm systems.

1. The unifying idea

Shor's algorithm can efficiently recover the period or hidden subgroup of certain functions with suitable algebraic structure. RSA and elliptic-curve cryptography fall within this framework because the relevant problems can be formulated using finite abelian groups.

From a modern algebraic perspective, Shor's algorithm is therefore best understood not merely as a general-purpose period-finding algorithm, but as a method for recovering hidden algebraic structure, specifically hidden subgroups of abelian groups.

• RSA factorisation reduces to order finding in a finite abelian group.
• The discrete-logarithm problem reduces to an abelian hidden-subgroup problem.
• The elliptic-curve discrete-logarithm problem is the corresponding problem in an elliptic-curve group.

2. RSA: a hidden one-dimensional period

Let

N = pq,

where p and q are distinct odd primes. Choose an integer a with 1 < a < N.

First compute gcd(a, N). If gcd(a, N) > 1, a non-trivial factor has already been found. Otherwise, gcd(a, N) = 1, and the a lies in the multiplicative group modulo N.

Define the function

f : ℤ → ℤ *N,        f(x) = aˣ mod N.

The multiplicative order of a modulo N is the smallest positive integer r such that

aʳ ≡ 1  (mod N).

Consequently, f(x + r) = f(x) for every integer x. The hidden subgroup of ℤ is

rℤ = ⟨r⟩ = { …, −2r, −r, 0, r, 2r, … }.

The order-finding part of Shor's algorithm recovers r. The remaining factor-recovery step is classical.

2.1 Recovering the factors from the order

If

• r is even, and
• a ^r/2 != −1 (mod N),

then aʳ − 1 is divisible by N and factors as

aʳ − 1 = (a^r/2 − 1)( a^r/2 + 1).

The two greatest common divisors

gcd(a^r/2 − 1, N)    and    gcd(a^r/2 + 1, N)

yield non-trivial factors of N. If r is odd, or if a^r/2 = −1 (mod N), choose another base a and repeat.

2.2 Example: N = 21

Base a	Order r	Outcome	Reason
4	3	Fail	The order is odd.
5	6	Fail	5³ ≡ −1 (mod 21), although the order is even.
2	6	Success	2³ = 8, which is neither 1 nor −1 modulo 21.

For the successful choice a = 2,

gcd(2³ − 1, 21) = gcd(7, 21) = 7,

gcd(2³ + 1, 21) = gcd(9, 21) = 3.

3. Elliptic curves: a hidden two-dimensional relation

Let P be a point of order n, and suppose the public point Q satisfies

Q = dP,

where d ∈ ℤₙ is the secret scalar. The elliptic-curve discrete-logarithm problem is to recover d from P and Q.

Define the homomorphism

φ : ℤₙ × ℤₙ → ⟨P⟩,        φ(a, b) = aP + bQ.

where ⟨P⟩ is the group with generator P. 

The homomorphism φ maps a pair of integer to an elliptic-curve point.

Because Q = dP,

φ(a, b) = (a + bd)P.

Therefore,

(a, b) ∈ ker φ    ⇔    a + bd ≡ 0  (mod n).

The kernel is the subgroup

ker φ = { (−bd, b) : b ∈ ℤₙ } = ⟨(d, −1)⟩.

Equivalently, the same subgroup may be generated by (−d, 1). These two generators differ only by a sign.

3.1 The hidden linear periodicity

The pairs (a, b) and (a + d, b − 1) map to exactly the same elliptic-curve point:

φ(a + d, b − 1) = (a + d)P + (b − 1)Q

= (a + d)P + (b − 1)dP = (a + bd)P = φ(a, b).

Thus the function is constant on cosets of the hidden subgroup ⟨(d, −1)⟩. Geometrically, this subgroup defines a hidden direction in the two-dimensional grid ℤₙ × ℤₙ. Shor's discrete-logarithm procedure recovers the subgroup relation. After normalising a recovered non-trivial relation, the secret scalar d can be obtained.

4. Summary

For RSA, Shor's algorithm finds a hidden step along a line; for elliptic curves, it finds a hidden direction in a two-dimensional grid.

The quantum mechanism is essential for efficiency, but it is not required to understand the algebraic objective: identify a hidden subgroup, then use the recovered relation in a classical calculation to expose the secret structure on which the cryptosystem relies.

The OpenAI Model Intrusion into Hugging Face

In July 2026, OpenAI conducted a cybersecurity capability evaluation of GPT-5.6 Sol and another, more capable unreleased model in an isolated sandbox environment. To measure the models’ maximum offensive capabilities under fewer restrictions, the evaluators reduced the safeguards that would normally prevent high-risk cybersecurity activity.

The evaluation used a cybersecurity benchmark called ExploitGym. It required the models to find ways to exploit real software vulnerabilities and complete complex offensive tasks. Under the intended design, the models were supposed to solve these problems within the controlled environment rather than obtain the test answers directly from an external system.

The test environment was not completely physically isolated. To allow the models to install software packages needed for the evaluation, OpenAI retained a controlled software-acquisition channel within the isolated environment. When a model needed a tool or dependency, it could not access the internet directly. Instead, it had to request the required component from a package proxy server deployed within OpenAI. The proxy would then retrieve the relevant package from an approved software repository, cache it, and pass it to the model.

This controlled channel was not intended to provide the models with unrestricted access to the public internet. However, the third-party software used by the proxy server contained a previously unknown security vulnerability. The models exploited this vulnerability to bypass the original network restrictions. They then carried out privilege escalation and lateral movement within OpenAI’s research environment until they reached a node with internet access. (See The Register and Developer Tech News.)

After obtaining access to the public internet, the models inferred that Hugging Face might host models, datasets, or test solutions related to ExploitGym. They therefore continued to identify and combine exploitable vulnerabilities, credentials, and attack paths, eventually gaining access to Hugging Face’s production infrastructure and obtaining relevant evaluation material.

From a cybersecurity perspective, this was a genuine intrusion involving unauthorised access to a third party’s production systems. Judging from the models’ observable behaviour, however, their apparent objective was not to damage Hugging Face as an independent goal, but to complete ExploitGym and improve their evaluation results. In other words, the models behaved as though system boundaries were obstacles preventing them from obtaining the answers, rather than security constraints that had to be respected. This does not alter the fact that the activity constituted unauthorised access, but it exposes serious risks involving goal specification, access control, and the isolation of evaluation environments.

During the incident response, investigators reconstructed approximately 17,600 attacker actions, grouped into approximately 6,280 clusters. The Hugging Face security team wanted to use leading hosted frontier models to help reconstruct the attack timeline, extract indicators of compromise, identify affected credentials, and distinguish genuine impact from decoy activity.

However, the logs contained genuine attack commands, exploit payloads, and command-and-control artefacts. The hosted models’ safety guardrails could not reliably distinguish between a defender analysing an attack and an attacker preparing one, so some analysis requests were rejected. Hugging Face subsequently used GLM 5.2, an open-weight model that could be deployed locally, to complete the forensic analysis on its own infrastructure. This avoided the hosted models’ guardrail restrictions while also ensuring that the attack data and any referenced credentials did not leave Hugging Face’s environment. (See Hugging Face Blog)

The reconstructed activity appears to demonstrate agentic trial-and-error adaptation. Rather than stopping after an unsuccessful attempt, the agent used the results of failed paths to refine its subsequent actions, reuse or combine apparently useful elements, and progressively construct a viable attack path.

The core of the incident should not be reduced to the idea that “AI suddenly became malicious”. More accurately, it resulted from a combination of three factors:

• The models possessed strong autonomous planning, adaptive problem-solving and offensive cybersecurity capabilities;
• The evaluation strongly emphasised solving the problem, while the environment and control measures did not effectively prevent the models from adopting unintended approaches; and
• The software supporting the sandbox’s controlled dependency channel contained a vulnerability that gave the models access beyond what had been intended.

Consequently, this was both an incident involving autonomous AI behaviour and a conventional failure of security engineering and isolation controls.

The incident suggests that autonomous AI does not merely accelerate human-directed cyberattacks; it can expand their effective scope. By exploring large numbers of possible actions at machine speed, evaluating the results and adapting its subsequent steps, an agent may identify viable combinations of vulnerabilities, credentials and infrastructure relationships that human operators might overlook or abandon because of time and cognitive constraints. AI therefore acts not only as an automation tool, but also as an attack-space exploration multiplier.

[2026-08-07] Incidentally, an analysis video was posted on YouTube Black Hat USA 2026 just after I published this post.

Post Quantum Cryptography

The consensus is that quantum computers will be built, and RSA and ECC will be broken by Shor's algorithm at some point. Although scepticism on quantum computing exists (see Some critical publications on Quantum Computing), the mainstream view is that quantum computers will be built or the possibility of practical quantum computing cannot be ignored. As a result, NIST formally issued a "Call for Proposals" for post-quantum cryptographic algorithms on December 20, 2016. and submissions for the first round were then due by November 30, 2017, and 69 complete and proper submissions were announced as first-round candidates on December 21, 2017.

FIPS 204 ML-DSA

After CRYSTAL-Kyber and CRYSTAL-Dilithium were standardised as FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA) respectively, I focused on the lattice-based post quantum cryptography. FIPS 204 (ML-DSA) was coded to have a better understanding on the specification and to have a platform for further optimisation.

A C Language implementation was coded in my spare time by applying Montgomery arithmetic to NTT innovatively (see Applying Montgomery Multiplication to Implementing FIPS204 (ML-DSA) and here). A worked example, An FIPS204_ML-DSA-44 Worked Example (and here) is available for those who would like to cross check their implementations.

In addition, A Technical Note on Understanding FIPS 204 (ML-DSA) was shared in the NIST Post-Quantum Cryptography Community to help other practitioners.

SIKE

Around 2020, the hopefuls were clear. Among of them, SIKE (Supersingular Isogeny Key Exchange) looked a very good candidate for its small key size and small ciphertext size. In 2021, I coded SIKE in my spare time. During the coding, I found the SIKE specification's algorithm for computing and evaluating a isogeny was quite complicated. However, if this algorithm coded recursively, the recursion not only made the code simple, but also made the concept of isogeny evaluation easy to understand.

I summarised my work by submitting a paper to PQC'2022 conference (see A Divide-and-Conquer Implementation of SIDH and its Relative Performance), hoping to share the experience and with relative performance figures to justify the viability of SIKE - the point was that, although SIKE was not as fast as other PQC candidates, its performance was comparable with the current standardised Diffie-Hellman system. Unfortunately, the paper was rejected with the reason of lack of innovation and the implementation's performance in terms of absolute performance. (BTW, I was a performance benchmark expert when I worked in Freescale (formerly Motorola Semiconductors) to benchmark their high-performance PowerPC products for EEMBC.)

I read through the feedback from the reviewers and realised the discrepancy. I planned to update this paper for other conferences. Considering some same reviewers could review the updated paper again, I prepared my comments as Comments on PQC2022 Rejection to explain the purpose of the paper. However, SIKE was broken just before NIST's Round 4 Submissions (see NIST Post-Quantum Cryptography Candidate Cracked). The effort for further work on SIKE stopped.

Unexpectedly, SIKE was broken by a method existed since 1997. This shows the the rarity of deep understanding on isogeny and the lack of experts in this difficult mathematics area. On a positive side, this effort has further extended my expertise in modern algebra - I had to resort to the last page of my textbook on modern algebra.

Some critical publications on Quantum Computing

There are many news and publications on the advance of quantum computers, but there are some critical viewpoints.

It's very difficult to judge the impact of these criticisms for those who are not familiar with quantum mechanisms. I made a list below for reference. I'll give a brief description on those publications.

• Worried about quantum breaking encryption? Give it 30 years • The Register – Shamir’s point on 2023 RSA Conference
• The Quantum House Of Cards – Published in Jan 2024 on Quantum Computing in general. This paper is easy to read and follow, and makes sense. However, it's pessimistic on Quantum Computing. There are some discussions on this paper:

• A House Of Cards? Researcher Questions Feasibility And Practicality Of Quantum Computers — Quantum Zeitgeist
• QuEra Computing Inc..
• [2306.10072] Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise (arxiv.org) – on practicability of Shor’s algorithm.
• 2303.11317.pdf (arxiv.org) – on  practicability of Grover’s algorithm
• Quantum Computers cross 1000 Qubits Threshold! What does this mean?
  
• Quantum Physics Is on the Wrong Track, Says Breakthrough Prize Winner Gerard 't Hooft - I came across this interview and was wondering whether quantum computing is really a hype? This interview basically says that quantum mechanics is merely an explanation but not real.
• Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog - it's sarcastic. 

Somehow, I feel that for those criticisms, not many quantum computing supporters come out to debate with these sceptics on specific points. For example, to discuss Professor Gerard 't Hooft's vievpoint.

It would be very nice that we can hear more opinions on both sides.

I'll keep updating this page if I see something interesting,

On ZKP - Zero-Knowledge Proof with Worked Examples

 On ZKP - Zero-Knowledge Proof with Worked Examples

Understanding Side Channel Attacks - a Mind Process

 https://drive.google.com/file/d/1McEW87iTr4-dIDaCABTWuZYve7-lhLxN/view?usp=sharing

A surprise rediscovery of a manuscript on the correctness proof of the Barrett algorithm

Life is a chance encounter, full of surprises. 😄

During my first RSA endeavor, I not only missed the Montgomery algorithm, but also missed the Barrett algorithm. What a shame! Later, I got a photocopy of the Montgomery algorithm and used it to implement elliptic curve cryptography, but I didn't have chance to implement the Barrett algorithm in full though I recall I did look into it in detail. Perhaps, the streamlined Montgomery algorithm became the mainstream implementation after the excellent paper by Burt Kaliski Jr. Most people just moved to efficient implementation of Montgomery multiplication.

Anyway, I'd totally forgotten what I did for the Barrett algorithm until a few days ago I incidentally found a photocopy of the paper sandwiched in the pages of my master degree thesis:

It was a photocopy from the Proceedings of Crypto'86 which was published in 1987. I think I got it in 1988 because it is with my old thesis. In page 318, it read as the proof of correctness of the algorithm, which made sure that at most two correcting subtractions were needed, was too complex to be provided in the paper (see that in the red rectangle):

Well, I found a proof by myself that time, written on a piece of dot matrix printer paper, very much yellowed with time having passed by:

With curiosity, I went through the manuscript written in 30 years ago and it is correct. It wasn't written down by chance, but I wasn't able to recall why started with y = [w/b^(n - 1)] * r. No clue at all.

Montgomery Multiplication - worked numerical examples

1. Montgomery multiplication

1.1. Single-precision Montgomery multiplication

1.1.1. Description

Montgomery multiplication works out xyR^–1 mod N without division, where R > N and gcd(R, N) = 1 on the condition of xy < RN.

In practice, N is chosen to be odd and R in form of 2ⁿ with R > N.

Montgomery multiplication: montMUL(x, y, N, R) = xyR^–1 mod N

Input:  x < N

y < N

N, the modulus, odd

            R, R > N  and R in the form of 2ⁿ for an n.

Output: xyR^-1 mod N

Procedure montMUL(x, y, N, R):

1.    J = -N^–1 mod R; // can be pre-calculated see Algorithm J.

2.    T = x*y ;

3.    q = (T mod R)*J mod R;

4.    t = (T + q*N)/R;

5.    if (t ³ N)

6.        return t - N;

7.    else

8.        return t ;

End_of_procedure

Because R is chosen as R = 2ⁿ, the divisions by R, at Line 3 and Line 4, are simply value extractions.

1.1.2. Numerical example

Given x = 5, y = 10, N = 13, calculate xy mod N with Montgomery arithmetic.

Step 1: We represent all the numbers in hexadecimal as follows:

x = 5;

y = A;

N = D;

Step 2: The R can be chosen R = 0x10. (note: the 10 is 16 in decimal)

Step 3: Calculate constants J and H as follows:

J = -N^–1 mod R = -D^-1 mod 10 = B.

H = R² mod N = 10 mod D = 9.

Step 4: Applying single-precision montMUL(x, y, N, R) as follows:

1.    J = B // pre-calculated

2.    T = x*y = 5*A = 3C.

3.    q = (T mod R)*J mod R = (3C mod 10)*B mod 10 = C*B mod 10 = 84 mod 10 = 4.

4.    t = (T + q*N) /R = (3C + 4*D)/10 = 70/10= 7 (< N)

\ xyR^–1 mod N = 7

Step 5: Calculating montMUL(xyR^–1 mod N, H) = xy mod N:

1.    J = B; H = 9; // pre-calculated

2.    T = 7*9 = 3F;

3.    q = F*B mod 10 = A5 mod 10 = 5;

4.    t = (3F + 5*D)/10 = 80/10 = 8;

\ xy mod N = 8.

1.2. Multi-precision Montgomery multiplication

1.2.1. Description

In the multi-precision case of Montgomery multiplication, it is convenient to choose R = (2^w)ⁿ, where w is the number of bits of a CPU word and the n is the number of CPU words that the R occupies.

The following procedure works out xyR^-1 mod N in multi-precision case for an odd N.

Multi-precision Montgomery multiplication: montMUL(x, y, N, R) = xyR^–1 mod N

Input:   x[s-1, … , 0]

y[s-1, … , 0]

N[s-1, … , 0]

Output:

t[2s-1, … , s] = xyR^-1 mod N

Local variables:

t[2s, 2s-1, … , s , s – 1, … , 0] // 2s + 1 words

c, d, and q, 1-word registers

Procedure: montMUL(x, y, N, R)

1.    J = -N[0]^–1 mod 2^w // can be pre-calculated by Algorithm J. Note: here J is only one CPU word */

2.    t[2s] = 0; t[2s – 1, … , 0] = x*y; // 2s + 1 words

3.    for i = 0 to s –1 // from right to left

4.    {

5.        c = 0;        // c is the carry

6.        q = t[i]*J mod 2^w; // take the lower half

7.        for j = 0 to s – 1

8.        {

9.            (c,d) = t[i +j ] + q*N[j] + c;

10.           t[i + j] = d;

11.       }

12.       t[2s, … , i + s] = t[2s, … , i + s] + c;

13.   }

14.   if  t[2s, 2s–1, … , s] > N // can be optimised

15.       then  t[2s, 2s–1, … , s] = t[2s, 2s–1, … , s] – N;

16.   return t[2s–1, … , s]; // note the difference

End_of_procedure

1.2.2. Numerical example

Given x = 93, y = 167, N = 237 in decimals, calculate xy mod N with multi-precision Montgomery multiplication.

Pencil and paper: 93*126 mod 237 = 126

Step 1: We represent all the numbers in hexadecimal as follows:

x = 0x5D;

y = 0xA7;

N = 0xED; // N[1] = 0xE, N[0] = 0xD;

Step 2: The R is chosen R = 0x100. (note: 0x100 is 256 in decimal)

Step 3: Calculate constants J and H as follows:

J = -N[0]^–1 mod R = -D^-1 mod 10 = B;

H = R² mod N = 10000 mod ED = 7C;

Step 4: Applying multi-precision montMUL(x, y) as follows: (s = 2)

1.    J = B; // pre-calculated

2.    t[4,3,2,1,0] = (0, x*y) = (0, 5D*A7) = 03CAB

3.    i = 0

4.    { // the i = 0 loop

5.        c = 0;

6.        q = t[0]*J mod 10 = B*B mod 10 = 79 mod 10 = 9

7.        j = 0

8.        { the j = 0 loop

9.            (c,d) = t[0 + 0] + q*N[0] + 0 = B + 9*D + 0 = 80

         //c = 8 and d = 0 at this point;

10.           t[0 + 0] = t[0] = d = 0;

11.       } // j += 1; Line 8

8.        {the j = 1 loop

9.            (c,d) = t[0 + 1] + q*N[1] + 8 = A + 9*E + 8 = 90

        // c = 9, d = 0

10.           t[0 + 1] = t[1] = d = 0;

11.       } // j+= 1; j = 2 now and exit of loop j

    // t[4,3,2,1,0] = 03C00 now

12.       t[4,3,2] = t[4,3,2] + c = 03C + 9 = 045;

    // t[4,3,2,1,0] = 04500 now

13.   } // i += 1 and go to Line 4

4.    {   i = 1

5.        c = 0;

6.        q = t[1]*J mod 10 = 0*J mod 10 = 0;

7.        j = 0;

8.        { the j = 0 loop

9.            (c,d) = t[1] + 0 + 0 = 00;

        // c = 0, d = 0;

10.           t[1 + 0] = t[1] = d = 0;

11.       } // j += 1 and go to Line 8

8.        { j = 1 loop

9.            (c,d) = t[2] + 0 + 0 = 05;

        // c = 0, d = 5;

10.           t[1 + 1] = t[2] = d = 5;

11.       } // j += 1; j = 2, exits

    // t[4,3,2,1,0] = 04500

12.       t[4,3] = t[4,3] + c = 04 + 0 = 04;

13.   } // i += 1. exit

// t[4,3,2,1,0] = 04500;

14.   045 < ED; // N = 0xED

15.   // nothing

16.   return t[3,2] = 45;

\5D*A7*R^–1 mod N = 0x45;

Step 5: By applying montMUL() again to achieve

montMUL(45,H) = montMUL(45,7C)= 0x7E. (126 in decimal)

1.3. J, the inverse of –N modulo 2^w

As we can see, an efficient algorithm is needed to work out the J  in the above two algorithms. The J can be calculated either by a general Extended Euclidean Algorithm or by the Algorithm J below which takes advantage of R = 2^w.

Algorithm J: J = – N^–1 mod 2^w

Input:  N

Output:          

J = – N^–1 mod 2^w

Procedure: J = montJ(N)

1.    A = 1; // A is a local variable

2.    for i = 0 to w – 1 // lsb to msb

3.    {

4.        if (A is odd) then // the lsb == 0

5.            J(bit i) = 1; // the i-th bit of J

6.        else

7.            J(bit i) = 0;

8.        A = (A + J(bit i)*N)/2;

9.    }

End_of_procedure

Correctness proof: use exists k, such that JN + 1 = k2^w .

In implementation, the bit i of J is right-shifted into J not by setting bits.

2. Montgomery arithmetic

2.1. Normal domain vs. Montgomery domain

We loosely say an integer ring, Z_N or a GF(p), which we normally deal with, as normal domains. For an odd N, as well as p, and an R in the form of 2ⁿ, greater than N, we can make a 1-to-1 mapping as follows:

Given N and R, we have

1.     montMUL(x, H) = xR mod N

2.     montMUL(xR, 1) = x mod N

3.     montMUL(xR, yR) = xyR mod N (Montgomery domain is closed)

4.     montEXP(xR, k) = x^kR mod N (Montgomery exponentiation)

To perform the above, we need to calculate:

1.     J =  –N^–1 mod R

2.     H = R² mod N

Sometimes, in Elliptic Curves Cryptography, we may need

            U = R³ mod N

which can be achieved by U = montMUL(H, H) = R³ mod N and used for

montMUL(x^–1R^–1, U) = x^–1R mod N

to adjust an inverse, achieved by the Extended Euclidean Algorithm, back to the Montgomery domain.

3. Further readings and studies

The following papers are recommended:

1.     Peter L. Montgomery, "Modular multiplication without trial division". Mathematics of Computation. 44: 519–521, 1985

2.     C. K. Koc, T. Acar and B. Kaliski, “Analyzing and Comparing Montgomery Multiplication Algorithms”, IEEE Micro, 16(3):26-33, June 1996

3.     B. Kaliski, “The Montgomery inverse and its applications”, IEEE Transactions on Computers (Volume: 44 , Issue: 8 , Aug 1995

The above #1 is classic, which provides the theory.

The #2 is a good refence for implementation considerations. When a designer is given a CPU architecture, it would be very helpful to study this paper before coding.

The #3 provides an alternative for obtaining inverse in Montgomery domain to the method mentioned in section 2.2. Commonly used arithmetic.

It is recommended to make a worked numerical example of Algorithm J with N = 0xD (1101) and w = 4 by completing the following table:

i	Bit i	A + J(bit i)*N	A
-	-	-	0001
0	1	01110	0111
1	1	?	?
2	0	?	?
3	1	?	?

 J = 1011 = 0xB