A linear-time algorithm for the orbit problem over cyclic groups

DOI10.1007/s00236-015-0251-0zbMath1347.68186arXiv1411.3164OpenAlexW2099783652MaRDI QIDQ303693

Sanming Zhou, Anthony Widjaja Lin

Publication date: 22 August 2016

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.3164

zbMATH Keywords

bit complexity modellinear algorithmsorbit problemsystem of linear congruence equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite abelian groups (20K01) Congruences; primitive roots; residue systems (11A07)

Uses Software

• OEIS

Cites Work

• On the constructive orbit problem
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Faster deterministic integer factorization
• Polynomial-time algorithm for the orbit problem
• The Birth of Model Checking
• A Stirling Encounter with Harmonic Numbers
• Validation of Stochastic Systems
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item