Fast square-free decomposition of integers using class groups - Erik Mulder - 17 July 2024

Oct 4, 2026

Square-free decomposition seeks integers a and b such that n = a^2 b with b square-free. The talk motivates the computational role of such decompositions in cryptographic settings where the difficulty of factoring underlies security. It presents a fastest method under heuristic assumptions, together with background on binary quadratic forms, class groups, and Schnorr–Lenstra factorization. A new algorithm is derived via derived forms and lifting to related discriminants.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages16

Reading Time40 min

AccessFree to download

Introduction

Definition

Main result

Binary quadratic forms

Schnorr-Lenstra factorization

Derived forms I

Derived forms II

The new square-free decomposition algorithm I

The new square-free decomposition algorithm II

Fast square-free decomposition of integers using class groups Erik Mulder 17 July 2024 Erik Mulder Fast square-free decomposition of integers using class groups 1 / 16 Thanks to the organizers Figure: Cool guy Erik Mulder Fast square-free decomposition of integers using class groups 2 / 16 Introduction Definition Square-free decomposition problem: Let n = a2 b with a, b ∈ N and b square-free. Find a and b. Who doesn’t like integer factorization? Cryptographic systems that use n = p2 q or n = pk q rely on the hardness of factoring of n. Computing ring of integers of number field Computing endomorphism ring of an elliptic curve over a finite field Erik Mulder Fast square-free decomposition of integers using class groups 3 / 16 Main result |
Theorem | | --- | |
Assume some heuristic assumptions. Fix 0 ≤ α ≤ 1. Then for all integers n = a2 b with b = nα, there is an algorithm that finds the square-free decomposition of n in expected time:
O (Lb[1/2, 1]) = O (Ln[1/2, √α]) ,
where
Lb [α, c] = e (c+o(1)) ln(b)α (ln ln(b))1 − α . | If a, b are distinct primes of roughly the same cryptographic size, then this is the current fastest method. Erik Mulder Fast square-free decomposition of integers using class groups 4 / 16 Binary quadratic forms f (x, y) = ax2 + bxy + cy2 = (a, b, c), where a, b, c ∈ Z. D = Df = b2 − 4ac is the discriminant of f. We always have D < 0. f is primitive if gcd(a, b, c) = 1. f , g are equivalent if there exists A = ( p qr s ) ∈ Γ such that f (x, y) = g(A · (x, y)T ) = g(px + qy , rx + sy) . Then Df = Dg . If |b| < a < c, then f is reduced. Every form is equivalent to a unique reduced form. C (D) is the class group of forms of discriminant D . With composition as its group operation. If D = 0 mod 4, then eD = (1, 0 , −~~4~~D ) . The class number h (D) ≈ √ D is the order of C (D) . Why not use ideals instead of forms? Erik Mulder Fast square-free decomposition of integers using class groups 5 / 16 Schnorr-Lenstra factorization Let n ∈ N , possibly square-free Take a random f ∈ C (−4n) Construct k, consisting of powers of all primes up to some B Pray that fk = e−4n, i.e. h (−4n) is smooth If so, try to construct g of order 2 Then g is of the form (d , 0 , ~~n~~d ) The complete factorization of n can be found this way If h (−4n) is not smooth, try C (−4ns) instead for some small square-free s Quite similar to the ECM Erik Mulder Fast square-free decomposition of integers using class groups 6 / 16 Derived forms I Definition Let p be a prime and D a discriminant. We say f ∈ C (Dp2 ) is derived from g ∈ C (D) if there exists a 2 × 2 integer matrix A with det(A) = p such that f (x, y) = g(A · (x, y)T ) . Proposition For every form f ∈ C (Dp2 ) there exists a unique g ∈ C (D) up to equivalence such that f is derived from g. For each g = (a, b, c) ∈ C (D) there are exactly p −􀀀Dp􀀁 inequivalent primitive forms in C (Dp2 ) that are derived from g. These forms are: (ap2 , p (b + 2ah), ah2 + bh + c) for 0 ≤ h ≤ p − 1 and (a, bp , cp2 ) Erik Mulder Fast square-free decomposition of integers using class groups 7 / 16 Derived forms II Corollary h (Dp2 ) = h (D) · (p − 􀀒Dp􀀓 ) . |
Proposition | | --- | |
If f1 , f2 ∈ C (Dp2 ) are derived from g1 , g2 ∈ C (D) respectively, then f1 · f2 is derived from g1 · g2 . | Erik Mulder Fast square-free decomposition of integers using class groups 8 / 16 The new square-free decomposition algorithm I From now on, n = p2 b, with p prime. Proposition Suppose g ∈ C (−4n) is derived from e−4b = (1, 0 , b) ∈ C (−4b) and g ≁ e−4n = (1, 0 , n) . Furthermore, suppose that g is reduced and b > p2. Then g = (p2 , 2pk , k2 + b) for some −p/2 ≤ k ≤ p/2 . Lemma | | | --- | |
Suppose g ∈ C (−4n) is derived from e−4b . Let r be a prime with r p. Lift g to some h ∈ C (−4nr2 ) . Then l = hr−(−4n | r ) is n

FAQs

What does square-free decomposition mean for an integer n?

It writes n = a^2 b with a,b ∈ N and b square-free, then asks for a and b.

What is the main algorithmic contribution under heuristic assumptions?

For n = a^2 b with b = n^α, it provides an expected-time bound O(Lb[1/2,1]) with an equivalent expression O(Ln[1/2,√α]).

How do derived forms and lifting help in the new decomposition algorithm?

Derived forms relate class groups of discriminants D and Dp^2, and the method lifts elements to a larger discriminant to force smoothness conditions, enabling recovery of a factor p^2 of n.

Oct 4, 2026

Upload by Lucas Martin