Empirical Complex Multiplication Detector for Elliptic Curves
A statistical classifier that detects whether an elliptic curve y² = x³ + ax + b has Complex Multiplication (CM) structure, based on 5 features extracted from finite-prime reductions.
- 🎯 100% accuracy on 18 production cryptographic curves (secp256k1, BN254, BLS12-381, P-256, Brainpool, etc.)
- 📊 Trained on 7,121 (curve, prime) data points
- 📈 5-fold CV AUC: 0.7937 ± 0.0057
- 🔬 Strongest signature:
gcd(#E, #E_twist)with p-value 3.78 × 10⁻¹⁷⁵ - 🚀 Runs on a laptop, no GPU/quantum required
- 📜 Open dataset (7,121 samples, 16 features) included
# Install dependencies
pip install sympy
# Run the detector
python3 cm_detector.pyExpected output:
Curve is_CM prob expected
-----------------------------------------------------------------
secp256k1 (Bitcoin) CM 0.738 CM ✓
BN254 G1 (zk-SNARKs) CM 0.672 CM ✓
BLS12-381 G1 (Ethereum 2.0) CM 0.673 CM ✓
...
Total: 12/12 (100.0%)
from cm_detector import CMDetector
det = CMDetector()
# Test secp256k1 (Bitcoin's curve, j-invariant 0)
is_cm, prob = det.detect(a=0, b=7)
print(f"secp256k1 is CM: {is_cm}, probability: {prob:.3f}")
# Output: secp256k1 is CM: True, probability: 0.738
# Test P-256 (NIST, non-CM)
is_cm, prob = det.detect(a=-3, b=41)
print(f"P-256-form is CM: {is_cm}, probability: {prob:.3f}")
# Output: P-256-form is CM: False, probability: 0.423An elliptic curve E has complex multiplication (CM) if its endomorphism ring is strictly larger than ℤ. For curves with j-invariant 0 (like secp256k1), the endomorphism ring contains ℤ[ω] where ω is a primitive cube root of unity. This structure enables the GLV endomorphism speedup but also creates measurable statistical signatures.
This classifier is informed by 9+ statistically significant signatures distinguishing CM from non-CM curves:
| Signature | p-value | Cohen's d | Family |
|---|---|---|---|
gcd(#E, #E_twist) |
3.78 × 10⁻¹⁷⁵ | +0.899 | Twist |
|#E/#E_twist - 1| |
3.82 × 10⁻¹³⁹ | -0.275 | Twist |
| Number of cubic roots | 1.01 × 10⁻¹²⁰ | +0.562 | Local |
|cos(θ)| |
1.51 × 10⁻¹⁰⁴ | -0.380 | Sato-Tate |
| Hasse interval deviation | 1.51 × 10⁻¹⁰⁴ | -0.380 | Sato-Tate |
v₂(#E) 2-adic valuation |
1.71 × 10⁻⁶⁷ | +0.346 | Local |
| Smoothness ratio | 3.84 × 10⁻⁴⁷ | -0.366 | Sato-Tate |
cos⁴(θ) |
1.51 × 10⁻¹⁰⁴ | +0.178 | Sato-Tate |
| Spectral gap of Cayley graph | < 10⁻¹⁰⁵ | +1.62 | Cayley |
These organize into 4 information-theoretic source families:
- Sato-Tate: trace distribution properties
- Cayley graph: random walk mixing properties
- Local algebraic: small-prime structure of #E
- Twist relations: properties of E vs quadratic twist E'
Detect whether a "verifiably random" curve has hidden CM structure that may indicate intentional construction:
from cm_detector import CMDetector
det = CMDetector()
is_cm, prob = det.detect(a=YOUR_CURVE_A, b=YOUR_CURVE_B)
if is_cm and prob > 0.7:
print("Warning: curve exhibits CM structure - investigate further")Reverse-engineer unknown curve parameters by checking signature patterns at small primes.
Direct empirical visualization of the Sato-Tate conjecture and CM theory.
The classifier has been tested on these production cryptographic curves:
CM curves (j=0 or j=1728):
- secp256k1 (Bitcoin) —
y² = x³ + 7 - BN254 G1 (zk-SNARKs) —
y² = x³ + 2 - BLS12-381 G1 (Ethereum 2.0) —
y² = x³ + 4 - BLS12-377 G1 (Aleo) —
y² = x³ + 1 - BN462 G1 —
y² = x³ + 2 - BLS24-509 G1 —
y² = x³ + 1
Non-CM curves:
- NIST P-256 / secp256r1 (TLS, multiple variants)
- Brainpool P256r1 (verifiably random)
- ANSSI FRP256-like
- SM2 (Chinese standard)
- Random non-CM controls
This tool is observational, not exploitative. The CM signatures detected here:
- ✅ Reveal structural properties of curves
- ✅ Are useful for curve auditing and forensic analysis
- ❌ Do NOT provide an attack on ECDLP for secp256k1 or other secure curves
- ❌ Do NOT reduce Pollard rho's
√ncomplexity bound
Pollard rho's lower bound (Shoup 1997) and Kim-Montenegro-Tetali (2010) ensure that even with full CM knowledge, ECDLP-256 still requires ~2^128 operations.
The training dataset (cm_dataset.csv) contains 7,121 (curve, prime) samples:
| Column | Description |
|---|---|
label |
"j0", "j1728", or "nonCM" |
p |
Prime field characteristic |
a, b |
Curve coefficients (y² = x³ + ax + b) |
n_E |
#E(F_p) |
n_twist |
#E_twist(F_p) |
cos_theta |
Frobenius trace cosine |
abs_cos, cos_4 |
Higher moments |
smooth_r |
Smoothness ratio |
v2 |
2-adic valuation of #E |
gcd_E_twist |
gcd(#E, #E_twist) |
abs_twist_ratio |
|#E/#E_twist - 1| |
num_zeros |
Number of cubic roots of x³+ax+b |
hasse_dev |
|t|/(2√p) |
is_cm |
Boolean: True for CM curves |
For details, see paper.tex which is being prepared for submission to:
- IACR ePrint (immediate, open access)
- SAC 2026 (Selected Areas in Cryptography Workshop)
- ANTS XVII (Algorithmic Number Theory Symposium)
Title: "Empirical Complex Multiplication Signatures of Elliptic Curves: A Multi-Feature Statistical Study with Implications for Curve Auditing"
@misc{disra2026cmsignatures,
author = {Disra Moonlit},
title = {Empirical Complex Multiplication Signatures of Elliptic Curves},
year = {2026},
howpublished = {\url{https://github.com/disra2027/pycm-detector}},
}git clone https://github.com/disra2027/pycm-detector.git
cd pycm-detector
pip install -r requirements.txt
python3 cm_detector.pyTotal compute: < 1 minute on standard laptop. No GPU required.
MIT License — see LICENSE file.
- Sato-Tate conjecture: Barnet-Lamb, Geraghty, Harris, Taylor (2011)
- Pollard rho lower bound: Shoup (1997)
- Mixing time analysis: Kim, Montenegro, Tetali (2010)
- GLV endomorphism: Gallant, Lambert, Vanstone (2001)
- Spectral isogeny graphs: Codogni, Lido (2023)
- Author: Disra Moonlit
- Email: disra.dev.indigo@gmail.com
- GitHub: @disra2027
This software is provided for research and educational purposes. The author makes no claims about the security of any specific cryptographic curve and confirms that the detected signatures do not constitute a known attack on standard ECC implementations.