When Elliptic-Curve Semiprimality Certificates Reveal Factors

What it is

Giuseppe Vitto's preprint (ePrint 2026/2620, received 24 October 2026) formalizes elliptic-curve semiprimality certificates and shows that those built with complex multiplication (CM) leak the factorization. The motivating examples are Reble's 1084-digit and Broadhurst's 5061-digit moduli, both of which the paper factors. The intended use was modulus generation: proving N has exactly two prime factors without revealing them.

How it works

The certificate is public data (N, S, E, P):

• N is a composite nonsquare integer.
• E is an elliptic curve over Z/NZ.
• S is a certified prime with S > (N^(1/6)+1)^2.
• P is a point of order S modulo every prime divisor of N.

Hasse's bound then forces every prime divisor of N above N^(1/3), so N has exactly two prime factors.

The break applies when the certificate was built with CM. If the Frobenius at every prime divisor lies in a known imaginary quadratic field of fundamental discriminant D, or has trace zero, a norm-lattice reconstruction recovers the factors of N from (N, S, D) alone. The expected running time is polynomial. This also requires gcd(S, 2DN) = 1. The paper also uses public-point and quadratic-twist attacks, which are complementary to the reconstruction, but the abstract does not describe them.

Preconditions / Affected

• Certificates of the Goldwasser-Kilian type with a prime point order, built through CM.
• The Frobenius condition and the gcd condition above must hold.
• The page names Reble's and Broadhurst's moduli as broken. It names no software or deployed system.

What to do

Do not use a CM-constructed elliptic-curve semiprimality certificate to publish a modulus whose factors must stay secret. The paper reports that three proposed repairs fail under its stated hypotheses:

• hidden cofactors
• withheld CM maps
• private isogeny descent within a known field

Caveats

Only the abstract was available, so the algorithm details, parameter sizes, running times and attack code are not covered here. The author leaves open whether a public Goldwasser-Kilian-based certificate can be produced for a fixed modulus, using its privately known factors, while keeping factoring as hard as the General Number Field Sieve. The attacks are shown under stated hypotheses, so certificates outside them are not ruled out. The paper is a preprint.