Faster infrastructure discrete logarithms and point counting

Definitions and mathematical statement

The source asks for a baby-step/giant-step infrastructure framework that speeds infrastructure discrete logarithms or point counting by a polynomial factor. In algebraic-number/function-field computation, an infrastructure is typically a collection of reduced objects with distance information and reduction-based baby and giant steps; it is not automatically a finite group with an associative operation.

For comparison, in a cyclic group of order $N$, ordinary baby-step/giant-step solves a discrete logarithm using on the order of $\sqrt N$ group operations and comparable stored group elements. Infrastructure analogues must account for distance corrections, reduction costs and the relevant search interval or regulator. The excerpt does not specify the number/function-field class, unit rank, infrastructure encoding, distance problem, or step-operation cost. A rank-one distance-circle model is therefore not silently imposed on every intended instance.

The target is a provable or otherwise explicitly qualified improvement over a specified baseline for one of the intended tasks. "Polynomial factor" needs a parameter: a factor polynomial in input bit length differs from a factor polynomial in the search-space size. Running time, memory, precomputation and heuristic versus worst-case guarantees also need definition. Point counting may refer to curve points, a Jacobian order or another class-number-related quantity; the source does not choose among these.

The summary reports square-root-style infrastructure algorithms and refinements by Scheidler--Williams--Zhang, Jauch--Jacobson and others, while saying no decisive general polynomial-factor speedup framework was verified. It supplies no exact complexities or theorem citations. This partial-progress report is retained without independently certifying a lower bound or current algorithmic status.

Short English statement

Improve infrastructure discrete-logarithm or point-counting algorithms through baby-step/giant-step ideas. The infrastructure class, target quantity, baseline and parameter for a polynomial-factor improvement are missing, so no exact complexity theorem is yet specified.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $8800087$, source code catalogue entry; supplied statement, background, and research summary, updated 2026-08-06. Attributed to Renate Scheidler.
• IPAM, Workshop on Number Theory and Cryptography---Open Problems (2006), attachment 6665, PDF pages 184--188, printed slide 29: https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Supplied PDF/legacy-PPT visual audit accessed 2026-07-29; it reports 19 inspected surviving attachments.
• Scheidler--Williams--Zhang and Jauch--Jacobson are named by the summary without full references or exact algorithmic bounds.