|
Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2008, Number 12, Pages 43–48
(Mi ivm1469)
|
|
|
|
Prime witnesses in the Shor algorithm and the Miller–Rabin algorithm
É. Yu. Lerner Kazan State University, Kazan
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 100000000 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.
Received: 31.08.2006
Citation:
É. Yu. Lerner, “Prime witnesses in the Shor algorithm and the Miller–Rabin algorithm”, Izv. Vyssh. Uchebn. Zaved. Mat., 2008, no. 12, 43–48; Russian Math. (Iz. VUZ), 52:12 (2008), 36–40
Linking options:
https://www.mathnet.ru/eng/ivm1469 https://www.mathnet.ru/eng/ivm/y2008/i12/p43
|
Statistics & downloads: |
Abstract page: | 530 | Full-text PDF : | 204 | References: | 51 | First page: | 1 |
|