FactorLibrary: From Polynomials to Circuits via Recursive Subgoals

Researchers introduce FactorLibrary, a reinforcement learning framework that discovers minimal arithmetic circuits for polynomials over finite fields by storing reusable subexpressions as subgoals. Using PPO+MCTS agents, the system achieves 91.8% success rate in finding certified optimal circuits, addressing a combinatorially hard problem in algebraic complexity theory.

This research tackles a fundamental challenge in algebraic complexity theory: constructing minimal arithmetic circuits for polynomials over finite fields. The problem has direct implications for cryptography, zero-knowledge proofs, and secure computation systems that rely on efficient polynomial representations. FactorLibrary's innovation lies in its hierarchical approach, using a library of factorizable subexpressions as reusable building blocks that reduce the exponential search space across training episodes.

The computational efficiency gains are significant because arithmetic circuit minimization directly affects the performance of cryptographic protocols and verification systems. Smaller circuits mean faster computation, lower memory requirements, and reduced resource costs for applications like zk-SNARKs and algebraic proofs. The research compares multiple reinforcement learning architectures—bottom-up with Gumbel-PPO-MCTS and top-down with PPO+MCTS and SAC—demonstrating that top-down approaches with PPO+MCTS provide the most reliable results.

For the broader cryptography and zero-knowledge community, this work potentially accelerates the practical deployment of proof systems by automating circuit optimization. Developers building privacy-preserving applications could leverage similar techniques to reduce computational overhead. The 91.8% success rate on complexity-8 circuits suggests the method scales reasonably, though the scalability to higher complexity levels remains to be demonstrated. This research bridges academic algebraic complexity theory with practical machine learning methods, offering a template for solving other combinatorial optimization problems in cryptographic systems.

• →FactorLibrary uses stored subexpressions as reusable subgoals to overcome combinatorial explosion in circuit search space
• →PPO+MCTS top-down agent achieved 91.8% success rate finding certified optimal arithmetic circuits up to complexity 8
• →Minimal arithmetic circuits directly improve performance of cryptographic protocols and zero-knowledge proof systems
• →The framework demonstrates that reinforcement learning can effectively solve algebraic complexity theory problems previously requiring manual optimization
• →Results could accelerate practical deployment of proof systems by automating circuit optimization for developers