Quantum Algorithms for Modular Factorials

• URL: http://arxiv.org/abs/2607.29453v1
• Date: Fri, 31 Jul 2026 14:15:12 GMT
• Title: Quantum Algorithms for Modular Factorials
• Abstract summary: We give a prime $p$, a divisor $qmid(p-1)$, and an integer $0np$, and computes $n!bmod p$ in expected time.<n>We conjecture that the condition $qmid(p-1)$ is a technical limitation of the present method rather than an inherent obstruction.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a bounded-error quantum algorithm that, given a prime $p$, a divisor $q\mid(p-1)$, and an integer $0<n<p$, computes $n!\bmod p$ in expected time $\widetilde{O}(q^c+\sqrt{p/q})$ for some absolute constant $c\ge 1$. When $p-1$ has a divisor of size $q\approx p^{1/(2c+1)}$, this gives the exponent $c/(2c+1)<1/2$. To our knowledge, this is the first algorithm to break the exponent $1/2$ barrier for modular factorials under such a divisor promise. The main technical ingredient is a quantum algorithm that reconstructs the relevant Jacobi sum exactly in compact algebraic form, with polynomial dependence on $q$ and $\log p$. We further extend the same asymptotic bound to the computation of $n!\bmod p^2$, uniformly over $0\le n<p^2$. At $n=p-1$, this determines the Wilson quotient $\frac{(p-1)!+1}{p}\pmod p$. We conjecture that the condition $q\mid(p-1)$ is a technical limitation of the present method rather than an inherent obstruction, and that a uniform quantum algorithm exists for all primes.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the $2^r p^s$-th Cyclotomic Field [0.0]
  We prove the RLWE-PLWE equivalence for the maximal real subfields of the cyclotomic fields with conductor $n = 2r ps$.<n>We also describe a fast multiplication algorithm in the ring of integers of these real subfields.
  arXiv  Detail & Related papers  (2025-04-07T15:01:48Z)
• Decomposition of RSA modulus applying even order elliptic curves [0.0]
  An efficient integer factorization algorithm would reduce the security of all variants of the RSA cryptographic scheme to zero.<n>We demonstrate how a natural extension of the generalized approach to smoothness, combined with the separation of $2$-adic point orders, leads us to propose a factoring algorithm.
  arXiv  Detail & Related papers  (2025-03-02T16:09:07Z)
• Some new infinite families of non-$p$-rational real quadratic fields [0.0]
  We give a simple methodology for constructing an infinite family of simultaneously non-$p_j$-rational real fields, unramified above any of the $p_j$. One feature of these techniques is that they may be used to yield fields $K=mathbbQ(sqrtD)$ for which a $p$-power cyclic component of the torsion group of the Galois groups of the maximal abelian pro-$p$-extension of $K$ unramified outside primes above $p$, is of size $pa
  arXiv  Detail & Related papers  (2024-06-20T18:00:51Z)
• Computing $\varphi(N)$ for an RSA module with a single quantum query [0.0]
  We give a computation time algorithm to compute $varphi(N)$ for an RSA module $N$ using as input the order modulo $N$ of a randomly chosen integer.
  arXiv  Detail & Related papers  (2024-06-06T13:30:18Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
  arXiv  Detail & Related papers  (2023-08-28T18:12:54Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.