A theoretical and practical scientific article on  the Google Colab laptop reproducible_ecdlp_challenge_ladder.ipynb

This paper documents the work of a Google Colab notebook created as a reproducible, practical companion to the paper by Dallaire-Demers, Doyle, and Foo, “Brace for Impact:  ECDLP  Challenges for Quantum Cryptanalysis” (arXiv:2508.14011).  The notebook  does not attack  Bitcoin , real wallets, public keys, or the secp256k1 work curve. Instead, it constructs and analyzes a deliberately small, public, and verifiable instance of the elliptic curve discrete logarithm problem ( ECDLP ).

Scientific significance.  Reproducible small samples allow one to verify the group arithmetic, the origin of challenge points, the correctness of discrete logarithm recovery, and asymptotic estimates without making unsubstantiated claims of breaking 256-bit ECC.

Annotation

We consider a practical implementation of the ECDLP learning ladder on the short Weierstrass curve, which has the same shape as secp256k1:  y² = x³ + 7 (mod p). The notebook implements: operations on a finite field; a group operation on points; deterministic derivation of NUMS points from strings  Quantum and  Challenge; SEC1 point compression; exhaustive finding of the discrete logarithm in a small group; a probabilistic  Pollard’s rho algorithm ; classical scalability calculation; and a classical check of an algebraic relation used in postprocessing of Shor’s algorithm. For each program block, the purpose, formulas used, execution flow, expected checks, and applicability limits are given.

1. Task setting

1.1 Elliptic Curve and  ECDLP

The notebook  uses a family of curves over a simple field  Fₚ:

E / Fₚ : y² = x³ + 7 (mod p).

The set of points on a curve, together with the point at infinity,  O forms an Abelian group. If  Q is a point of order  n, and  P belongs to the subgroup generated by it,  the ECDLP problem  is formulated as follows:

find κ ∈ {0, …, n − 1} such that P = [κ]Q.

In ECC cryptographic systems, a scalar corresponds to a secret value, and a period corresponds to a public value. In this experiment, κ is not anyone’s  private key : it exists only within the small study group and can be determined by direct verification.

1.2. Objectives of the study

• Build a testable  ECDLP instance  with parameter  TARGET_BITS = 6.
• Reproduce deterministic point generation without a pre-defined secret.
• Prove the correctness of the found κ by equality  [κ]Q = P.
• Show the collision mechanism and algebraic recovery of κ in  Pollard’s rho .
• Demonstrate why generic cryptanalysis classically grows as  Θ(√n).
• Distinguish between Shor’s post-processing mathematical model and the actual implementation of a quantum circuit.

2. Preparation and launch

2.1. Requirements

• Google account and access to  Google Colab .
• File  reproducible_ecdlp_challenge_ladder.ipynb.
• The standard Python  3  environment  is already provided by Colab . No external libraries need to be installed.

2.2. Launch procedure

1. Open  Google Colab  and select  File → Upload notebook .
2. Download the notepad file.
3. Make sure  Python  3 runtime is selected.
4. Run cells strictly from top to bottom using the run button or the  Runtime → Run all command .
5. Do not change  TARGET_BITS to large values ​​when using direct point enumeration: the tutorial implementation is intentionally not optimized for large fields.

Security Limitation:  This material is intended for educational purposes, code verification, and research on artificially small public groups. It does not provide a means of calculating discrete logarithms (secp256k1),  Bitcoin private keys   , or other production keys.

3. Step-by-step cell analysis

3.1. Introductory Markdown Cell

The first cell specifies the title, connection to the original paper, scientific purpose, and ethical restrictions. It explicitly states the objects of the demonstration:  a Bitcoin-like  curve, NUMS points, compressed SEC1, exhaustive  ECDLP ,  Pollard’s rho  , and an idealized Fourier-samples ratio for Shor.

Importantly, this cell doesn’t equate the model with quantum hacking:  Python  only performs classical computations. A real-world Shor scheme would require reversible arithmetic over a large elliptic curve, error correction, and a fault-tolerant quantum processor.

3.2. Cell 1 – Environment and Parameters

The code imports modules and sets reproducible constants:

import hashlib, math, random, time
from collections import Counter

TARGET_BITS = 6
A, B = 0, 7
RNG = random.Random(250814011)
INF = None

assert TARGET_BITS >= 5

Element	Function	Scientific meaning
TARGET_BITS = 6	Sets the training field size.	Allows you to accurately enumerate points and solve  ECDLP  without hidden heuristics.
A, B = 0, 7	Weierstrass short form coefficients.	Fix the form  y²=x³+7used in secp256k1.
RNG	Deterministic pseudorandom generator.	Makes Pollard’s rho start   and idealized samples repeatable.
INF = None	Representation of a neutral element.	The point at infinity O satisfies  P + O = P.
assert	Checks the lower bound of a size.	Prevents launching in a configuration not intended by the author.

Practical result:  after execution, all global parameters for the subsequent experiment are determined in memory. A fixed seed ensures repeatable results with unchanged Python code.

3.3. Cell 2 – Field and Group Arithmetic

This is a fundamental cell. It implements mathematical operations without cryptographic libraries, so every formula is auditable.

Primality check.  The function  is_prime(x) uses trial division up to √x. For small numbers, this is sufficient; for real-world cryptographic parameters, fast primality tests and specialized libraries are required.

Legendre symbol.  The function  legendre_symbol(a, p) calculates:

χₚ(a) = a^(p−1)/2 (mod p).

For an odd prime p, the value 1 means that a is a quadratic residue; −1 means that a is not a square root; 0 corresponds to a=0. In the code, the value remains in the modulo p representation, so the condition  in (0, 1) selects cases where the y-coordinate exists.

Square root.  The function  sqrt_mod_bruteforce sequentially checks all y in  {0,…,p−1}, until it finds  y² ≡ a (mod p). This is correct, but has complexity O(p), so it’s only valid on a toy board.

Verification of affiliation on_curve(P,p)  directly checks:

y² − (x³ + Ax + B) ≡ 0 (mod p).

For  None the function returns true because the point at infinity is an element of the group.

The negation of a point neg(P,p)  constructs:

−(x,y) = (x, −y mod p).

Addition. All necessary cases  are  add(P,Q,p) implemented: neutral element, addition of opposite points, addition of distinct points, and doubling. For P≠Q, the slope is calculated:

λ = (y₂−y₁)(x₂−x₁)⁻¹ (mod p),

and when doubling:

λ = (3x₁²+A)(2y₁)⁻¹ (mod p).

Result coordinates:

x₃ = λ²−x₁−x₂ (mod p), y₃ = λ(x₁−x₃)−y₁ (mod p).

The Pythonpow(value, -1, p)  call  computes   the inverse modulo p. It exists for a nonzero denominator, which is guaranteed by separate treatment of the vertical line and the point of order 2.

Multiplication by a scalar.  The function  mul(k,P,p) uses the double-and-add method. It reads the binary representation of k: if the bit is set, it adds the current point, doubles it at each step, and shifts k to the right. The execution time for group operations is O(log k).

Group enumeration. curve_points(p)  Iterates through all pairs (x,y), adding those that satisfy the equation. The complexity is O(p²), but for a 6-bit field this is small. The list length is exactly  #E(Fₚ).

3.4 Cell 3 – Deterministic Challenge Instance

This section combines arithmetic with the challenge ladder methodology. The function  find_toy_instance(k) scans numbers from  2ᵏ−1 down to  2ᵏ⁻¹, that is, candidates of k-bit length. For each prime p, it exactly computes the order of the group n given by  len(curve_points(p)). The instance is accepted if n is a prime and n ≠ p.

The requirement that n be prime is important: any nonzero point in a group of prime order generates the entire group. Consequently, the point Q has total order n, and the discrete logarithm P to the base Q is uniquely defined.

The function  nums_point(label,p) prints the public point from an ASCII string. Schema:

1. Calculate  SHA-256(label).
2. Interpret the hash as a big integer and convert it to modulo p.
3. Try  x=(h+δ) mod pstarting from δ=0.
4. Calculate  rhs=x³+7 mod p.
5. Check if rhs is a quadratic residue.
6. Find y and choose a canonical representation  min(y, −y mod p).

This is how the points  P = NUMS("Quantum") and  are obtained Q = NUMS("Challenge"). The choice of rows is fixed and public, so no one chooses a secret κ in advance. The variables  delta_P and  delta_Q document the number of search attempts.

The function  sec1_compressed creates a compressed SEC1 notation: a prefix  02 for even y and  03 odd y, followed by a fixed-width x. This reduces the public representation of a point, since for a given x, at most two y values ​​are possible—opposite points.

Finally,  multiplicative_order(p,n) look for the minimum r such that:

p ^r  ≡ 1 (mod n).

This is the embedding degree for a given order n. In the laptop, it is displayed as a diagnostic characteristic and is not used for attack.

Final check:

assert on_curve(P,p) and on_curve(Q,p) and mul(n,Q,p) is None

It proves, within the computation, that both points are correct and that  [n]Q = O.

3.5. Cell 4 – exact solution toy-ECDLP

The function  exhaustive_dlog starts at O ​​and sequentially evaluates:

O, Q, [2]Q, [3]Q, …, [n−1]Q.

At each step, it compares the current point with P. When equality is found, k is returned. For prime n and nonzero Q, this k is unique modulo n.

kappa = exhaustive_dlog(Q, P, n, p)
print('Recovered toy discrete logarithm kappa =', kappa)
print('Verification [kappa]Q == P:', mul(kappa, Q, p) == P)
assert kappa is not None and mul(kappa,Q,p) == P

Proof of the result.  The assertion  assert does not take the resulting number at face value, but rather iterates through scalar multiplication. Therefore, the proof is a directly computed group equality  [κ]Q=P.

Limit of applicability.  The search requires O(n) operations. For order around 2²⁵⁶, such a calculation is fundamentally impractical; this is why the 6-bit mode is for training purposes.

3.6. Cell 5 –  Pollard’s rho demonstration

Unlike linear enumeration,  Pollard’s rho  uses a pseudo-random walk and collision detection. The state is stored as:

Xᵢ = [aᵢ]Q + [bᵢ]P.

The function  rho_step divides the points into three classes  x mod 3 and selects one of the actions:

Class	Operation over X	Updating the coefficients
0	X ← X + Q	a ← a+1, b ← b
1	X ← 2X	a ← 2a, b ← 2b
2	X ← X + P	a ← a, b ← b+1

The invariant is preserved at each step. For example, after doubling:

2X = [2a]Q + [2b]P.

The algorithm  pollard_rho_dlog uses Floyd cycle detection: the “tortoise” takes one step, the “hare” two. When their points coincide, there is:

[aᵢ]Q + [bᵢ]P = [aⱼ]Q + [bⱼ]P.

After transfer:

[aᵢ−aⱼ]Q = [bⱼ−bᵢ]P.

Substitution  P=[κ]Q and a non-zero denominator yield:

κ = (aᵢ−aⱼ)(bⱼ−bᵢ) ⁻¹  (mod n).

The code calculates the candidate and always checks  mul(candidate,G,p) == H. If the collision is degenerate (the denominator is zero), the function does not falsely infer and returns  None; a correct production implementation typically restarts walk with a different starting point.

Scientific result.  If the execution terminates without exception, the equality  rho_k == kappa confirms the agreement of the probabilistic algorithm with the exact exhaustive solution.

3.7. Cell 6 – Classic Scalability

The function  rho_estimates(bits) uses an approximate order of n≈2 ^bits  and computes two theoretical estimates:

E[Tρ] ≈ √(πn/2), E[Tρ±] ≈ √(πn/4).

The second estimate takes into account symmetry  P ↔ −P (negation map), which reduces the constant but does not change the exponential nature of the complexity.

for bits in [6, 16, 32, 64, 96, 128, 160, 192, 224, 256]:
    base, symmetry = rho_estimates(bits)
    print(f'{bits:4d} | {base:14.3e} | {symmetry:14.3e}')

If you increase the bit length by 8, n grows by 2⁸=256 times, and √n by 16 times:

√(2 ^b+8 ) / √(2 ^b ) = 2 ⁴  = 16.

The last line of code checks this for the transition from 120 to 128 bits. The table output is not a time prediction on a specific computer, but an estimate of the number of group operations: the actual time depends on the point representation, parallelism, hardware, memory, and the quality of the implementation.

3.8. Cell 7 – Idealized Shor Post-Processing

The cell specifically separates the mathematics from the claim of quantum execution. A full quantum attack on  ECDLP  must implement a reversible mapping:

|x⟩|y⟩|R⟩ → |x⟩|y⟩|R + [x]G + [y]Q⟩,

After which, quantum Fourier transforms, measurements, and classical processing are performed. This scheme is not built in the notebook. Instead, the function  ideal_shor_sample generates an ideal pair:

b = rng.randrange(1, n)
a = (-secret * b) % n

According to the construction, the following is performed:

a + bκ ≡ 0 (mod n).

Since n is prime and b≠0, the inverse element b ⁻¹  exists. Therefore, each sample can be processed classically:

κ ≡ −ab ⁻¹  (mod n).

Five samples are needed not because of the mathematical necessity of a perfect model, but to demonstrate reproducibility. The test  all(x == kappa for x in recoveries) confirms that all artificially generated valid relationships return the same κ.

Correct Interpretation.  This cell does not simulate a noisy quantum processor, QFT, reversible point additions, or magic-state distillation. It only verifies the exact modular relation that would be used in the classical stage after obtaining a correct quantum sample.

3.9. Cell 8 – Reproducibility Report

The final cell forms a dictionary  report with the main artifacts of the experiment: the original article, the field size, p, n, embedding degree, compressed SEC1 points, κ from exhaustive search, κ from  Pollard’s rho , the number of rho steps, and the final Boolean test.

report = {
    'paper': 'arXiv:2508.14011 — ECDLP challenges for quantum cryptanalysis',
    'target_bits': TARGET_BITS,
    'field_prime_p': p,
    'group_order_n': n,
    'known_toy_kappa': kappa,
    'pollard_rho_kappa': rho_k,
    'verification': mul(kappa,Q,p) == P,
    'scope': 'Toy-instance demonstration only; no production-key or wallet attack.'
}

The practical role of this cell is to separate the observed results of the calculation from interpretations. The value  verification: True indicates that the equality in the small model has been verified. It does not constitute a statement about the safety or insecurity of other parameters.

4. Results, evidence and conclusions

4.1. Results achieved

• A transparent arithmetic curve model has been implemented  y²=x³+7 (mod p).
• A small field with prime group order and two deterministic public points are constructed.
• The belonging of the points to the curve and the equality are confirmed  [n]Q=O.
• The only toy-scalar κ has been found and verified.
• Pollard’s rho  recovered the same κ via the collision equation.
• A numerical illustration of the growth of generic-classical complexity as √n is obtained.
• The formula for recovering κ from an ideal pair satisfying has been verified  a+bκ≡0 (mod n).

4.2. Logic of proofs

Statement	Checking in Notepad
P and Q are points on the curve	on_curve(P,p) And  on_curve(Q,p).
Q has order dividing n	mul(n,Q,p) is None.
κ decides  ECDLP	Direct equality  mul(kappa,Q,p) == P.
Pollard’s rho  is correct in this run	rho_k == kappa plus a repeat group screening of the candidate.
Modular post-processing is coordinated with κ	All recovered values ​​in  recoveries coincide with κ.

4.3. Final conclusions

1. Deterministic NUMS construction allows challenge points to be published without having to trust the choice of a hidden private scalar.
2. Primeness of order n turns a nonzero point of Q into a generator of the entire group and guarantees the uniqueness of the discrete logarithm modulo n.
3. On a small group, direct search is a rigorous verification method, but its O(n) cost precludes application to real ECC sizes.
4. Pollard’s rho  is significantly better than brute force in terms of asymptotics, but remains exponential in bit length, on the order of: O(2 ^b/2 ).
5. Shor’s algorithm theoretically changes the complexity picture since it solves discrete logarithms in a polynomial number of quantum steps in the input size, but engineering implementation requires a fault-tolerant quantum architecture.
6. The training notebook should be treated as a properly limited artifact for training and verification, and not as a tool for practical cryptanalysis of 256-bit systems.

5. Notes and literature

5.1 Methodological notes

• Direct point enumeration replaces SEA point counting only for small p values. For large fields, this method is unacceptable due to time constraints.
• Brute-force square root extraction is also intentionally educational; for large simple fields, Tonelli–Shanks or special formulas are used.
• The group implementation does not have constant-time properties and is not intended for secret scalars.
• Pollard’s rho estimates   are probabilistic expectations; a particular trajectory may collide sooner or later.
• In the paper arXiv:2508.14011, the quantum resource estimates are scenario-based: they depend on physical errors, correction codes, distance, the performance of non-Clifford resources, and architectural assumptions.

5.2. References / recommended materials

1. P.-L. Dallaire-Demers, W. Doyle, T. Foo.  Brace for impact:  ECDLP  challenges for quantum cryptanalysis . arXiv:2508.14011, 2025. The main source of the concept of the difficulty-graded  ECDLP  challenge ladder, NUMS points, and quantum resource estimates.  arXiv record .
2. P.W. Shor.  Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer . SIAM Journal on Computing 26(5), 1484–1509, 1997. Foundational work on efficient quantum algorithms for prime factorization and discrete logarithms.  arXiv .
3. J. M. Pollard.  Monte Carlo Methods for Index Computation (mod p) . Mathematics of Computation 32(143), 918–924, 1978. Historical source of the rho method.
4. P. C. van Oorschot, M. J. Wiener.  Parallel Collision Search with Cryptanalytic Applications. Journal of Cryptology 12, 1–28, 1999.
5. E. Teske.  Speeding up  Pollard’s Rho  Method for Computing Discrete Logarithms . ANTS III, LNCS 1423, 1998. Analysis and improvement of the iterative functions of the rho method.  Springer record .
6. DJ Bernstein, T. Lange.  SafeCurves: Choosing Safe Curves for Elliptic-Curve Cryptography . A resource on the criteria and risks of choosing elliptic curves.  SafeCurves .
7. Standards for Efficient Cryptography Group (SECG).  SEC 1: Elliptic Curve Cryptography , Version 2.0, 2009. Description of point representation formats, including compressed SEC1.  SEC 1 PDF .
8. Standards for Efficient Cryptography Group (SECG).  SEC 2: Recommended Elliptic Curve Domain Parameters , Version 2.0, 2010. Parameters of secp256k1 and other standardized curves.  SEC 2 PDF .
9. A. J. Menezes, P. C. van Oorschot, S. A. Vanstone.  Handbook of Applied Cryptography . CRC Press, 1996. The classic reference on finite fields, discrete logarithms, and ECC.  Open online edition .
10. DRL Brown.  SEC 2: Recommended Elliptic Curve Domain Parameters  and related SECG materials – for mapping the curricular curve to engineering practice.