Prime witnesses in the Shor algorithm and the Miller-Rabin algorithm |
| |
Authors: | E. Yu. Lerner |
| |
Affiliation: | (1) Kazan State University, ul. Kremlyovskaya 18, Kazan, 420008, Russia |
| |
Abstract: | We prove that prime witnesses in the Miller-Rabin algorithm coincide with those in the Shor algorithm which satisfy the condition of Fermat’s little theorem. We describe the set of natural numbers, whose prime witnesses in the Miller-Rabin algorithm coincide with those in the Shor algorithm. We find all such numbers less than 100,000,000 and experimentally study the rate of increase of the ratio of the quantity of such numbers to the quantity of Carmichael numbers. |
| |
Keywords: | Shor’ s algorithm Fermat’ s little theorem strong pseudoprime witnesses Miller-Rabin algorithm Carmichael numbers |
本文献已被 SpringerLink 等数据库收录! |
|