Pairing sweep

As explained in Elliptic Curve Cryptography for Developers

A pairing sweep is a systematic enumeration of parameter values for pairing-friendly curve formulas followed by tests for acceptable prime and size conditions.

A pairing sweep systematically enumerates discriminants α and odd parameters x, evaluates r(z), q(z), and t(z) with z = αx², then tests prime and size conditions for pairing-friendly curves. section 14.5.1

A practical sweep follows this execution flow:

• Choose an embedding degree k and a maximum bit size lg2r; estimate the x limit from 2^(lg2r/(2k−2)). section 14.5.1

Command-line sweep

Running pairing_sweep_alpha 260 with k = 13 processes α values from 7 onward and reports 182 r primes. A result can contain 62-bit r, 76-bit q, ρ = 1.225806, and t = −34.

Figure 14.3 Program that sweeps over \(α\) to find pairing-friendly curves

Use the flow chart to inspect the sweep’s main control path from parameter selection through candidate testing. section 14.5.1

How Elliptic Curve Cryptography for Developers covers it

How deep it goes

Descends through formulas, GMP routines, loop bounds, primality checks, size cutoffs, and algorithm selection.

Examples

Demonstrates C/GMP routines, a k = 13 command-line run, and candidate outputs with r, q, t, and ρ.

What it assumes

Assumes the formulas for r(z), q(z), and t(z), while defining z, sweep bounds, supported k values, and loop behavior.

What you can do after

Builds a parameter-search program that evaluates candidate formulas and filters results by probable primality and bit size.

How it connects

Connects embedding degree, cyclotomic polynomials, pairing-friendly curves, probable-prime testing, and ρ.

liveBookmanning.com

Read Elliptic Curve Cryptography for Developers on liveBook Get the book at manning.com

Related concepts

• Hilbert class polynomialuses · A Hilbert class polynomial is a polynomial whose roots are j-invariants associated with elliptic curves having complex multiplication by a specified imaginary quadratic order.
• GNU Multiple Precision Arithmetic Libraryuses · GNU Multiple Precision Arithmetic Library (GMP) is a software library that provides arbitrary-precision arithmetic for integers, rational numbers, and floating-point values.

This explainer was generated by Manning's knowledge graph from the text of Elliptic Curve Cryptography for Developers. The section links point to the parts of the book it draws on.