Prime witnesses in the Shor algorithm and the Miller-Rabin algorithm

DOI10.3103/S1066369X08120062MaRDI QIDQ1006997zbMATH OpenOpenAlexFDO

Authors Eh. Yu. Lerner

Publication date 26 March 2009

Published in Russian Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/s1066369x08120062

zbMATH Keywords

Carmichael numbersFermat's little theoremMiller-Rabin algorithmShor's algorithmstrong pseudoprime witnesses

Mathematics Subject Classification ID

Cryptography (94A60)

Recommendations

• Shor's r-algorithms: theory and practice
• An implementation of Shor's \(r\)-algorithm
• Theory and software implementations of Shor's r-algorithms
• A note on Shor's quantum algorithm
• Primality Test Via Quantum Factorization
• A precise estimation of the computational complexity in Shor's factoring algorithm
• Probability estimates for Shor's algorithm
• A quantum version of Pollard's Rho of which Shor's algorithm is a particular case
• The Speed of Shor's R-algorithm
• scientific article

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3756556 (Why is no real title available?)
• scientific article; zbMATH DE number 1532364 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• Evaluation and comparison of two efficient probabilistic primality testing algorithms
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• There are infinitely many Carmichael numbers

Cited in

(1)

• On the number of witnesses \((a\bmod n)\) providing a proper divisor of \(n\)

This page was built for publication: Prime witnesses in the Shor algorithm and the Miller-Rabin algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1006997)