On the Number of Witnesses in the Miller–Rabin Primality Test
In this paper, we investigate the popular Miller–Rabin primality test and study its effectiveness. The ability of the test to determine prime integers is based on the difference of the number of primality witnesses for composite and prime integers. Let <inline-formula> <math display="i...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-06-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/12/6/890 |
| _version_ | 1797566444156747776 |
|---|---|
| author | Shamil Talgatovich Ishmukhametov Bulat Gazinurovich Mubarakov Ramilya Gakilevna Rubtsova |
| author_facet | Shamil Talgatovich Ishmukhametov Bulat Gazinurovich Mubarakov Ramilya Gakilevna Rubtsova |
| author_sort | Shamil Talgatovich Ishmukhametov |
| collection | DOAJ |
| description | In this paper, we investigate the popular Miller–Rabin primality test and study its effectiveness. The ability of the test to determine prime integers is based on the difference of the number of primality witnesses for composite and prime integers. Let <inline-formula> <math display="inline"> <semantics> <mrow> <mi>W</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> denote the set of all primality witnesses for odd <i>n</i>. By Rabin’s theorem, if <i>n</i> is prime, then each positive integer <inline-formula> <math display="inline"> <semantics> <mrow> <mi>a</mi> <mo><</mo> <mi>n</mi> </mrow> </semantics> </math> </inline-formula> is a primality witness for <i>n</i>. For composite <i>n</i>, the power of <inline-formula> <math display="inline"> <semantics> <mrow> <mi>W</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> is less than or equal to <inline-formula> <math display="inline"> <semantics> <mrow> <mi>φ</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> <mo>/</mo> <mn>4</mn> </mrow> </semantics> </math> </inline-formula> where <inline-formula> <math display="inline"> <semantics> <mrow> <mi>φ</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> is Euler’s Totient function. We derive new exact formulas for the power of <inline-formula> <math display="inline"> <semantics> <mrow> <mi>W</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> depending on the number of factors of tested integers. In addition, we study the average probability of errors in the Miller–Rabin test and show that it decreases when the length of tested integers increases. This allows us to reduce estimations for the probability of the Miller–Rabin test errors and increase its efficiency. |
| first_indexed | 2024-03-10T19:27:52Z |
| format | Article |
| id | doaj.art-8f6e2e2085a74425a75ecdcf680b7872 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T19:27:52Z |
| publishDate | 2020-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-8f6e2e2085a74425a75ecdcf680b78722023-11-20T02:24:55ZengMDPI AGSymmetry2073-89942020-06-0112689010.3390/sym12060890On the Number of Witnesses in the Miller–Rabin Primality TestShamil Talgatovich Ishmukhametov0Bulat Gazinurovich Mubarakov1Ramilya Gakilevna Rubtsova2Institute of Computational Mathematics and Information Technology, Kazan Federal University, Kremlevskya St. 35, Kazan 420008, RussiaInstitute of Computational Mathematics and Information Technology, Kazan Federal University, Kremlevskya St. 35, Kazan 420008, RussiaInstitute of Computational Mathematics and Information Technology, Kazan Federal University, Kremlevskya St. 35, Kazan 420008, RussiaIn this paper, we investigate the popular Miller–Rabin primality test and study its effectiveness. The ability of the test to determine prime integers is based on the difference of the number of primality witnesses for composite and prime integers. Let <inline-formula> <math display="inline"> <semantics> <mrow> <mi>W</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> denote the set of all primality witnesses for odd <i>n</i>. By Rabin’s theorem, if <i>n</i> is prime, then each positive integer <inline-formula> <math display="inline"> <semantics> <mrow> <mi>a</mi> <mo><</mo> <mi>n</mi> </mrow> </semantics> </math> </inline-formula> is a primality witness for <i>n</i>. For composite <i>n</i>, the power of <inline-formula> <math display="inline"> <semantics> <mrow> <mi>W</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> is less than or equal to <inline-formula> <math display="inline"> <semantics> <mrow> <mi>φ</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> <mo>/</mo> <mn>4</mn> </mrow> </semantics> </math> </inline-formula> where <inline-formula> <math display="inline"> <semantics> <mrow> <mi>φ</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> is Euler’s Totient function. We derive new exact formulas for the power of <inline-formula> <math display="inline"> <semantics> <mrow> <mi>W</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> depending on the number of factors of tested integers. In addition, we study the average probability of errors in the Miller–Rabin test and show that it decreases when the length of tested integers increases. This allows us to reduce estimations for the probability of the Miller–Rabin test errors and increase its efficiency.https://www.mdpi.com/2073-8994/12/6/890prime numbersprimality testMiller–Rabin primality teststrong pseudoprimesprimality witnesses |
| spellingShingle | Shamil Talgatovich Ishmukhametov Bulat Gazinurovich Mubarakov Ramilya Gakilevna Rubtsova On the Number of Witnesses in the Miller–Rabin Primality Test Symmetry prime numbers primality test Miller–Rabin primality test strong pseudoprimes primality witnesses |
| title | On the Number of Witnesses in the Miller–Rabin Primality Test |
| title_full | On the Number of Witnesses in the Miller–Rabin Primality Test |
| title_fullStr | On the Number of Witnesses in the Miller–Rabin Primality Test |
| title_full_unstemmed | On the Number of Witnesses in the Miller–Rabin Primality Test |
| title_short | On the Number of Witnesses in the Miller–Rabin Primality Test |
| title_sort | on the number of witnesses in the miller rabin primality test |
| topic | prime numbers primality test Miller–Rabin primality test strong pseudoprimes primality witnesses |
| url | https://www.mdpi.com/2073-8994/12/6/890 |
| work_keys_str_mv | AT shamiltalgatovichishmukhametov onthenumberofwitnessesinthemillerrabinprimalitytest AT bulatgazinurovichmubarakov onthenumberofwitnessesinthemillerrabinprimalitytest AT ramilyagakilevnarubtsova onthenumberofwitnessesinthemillerrabinprimalitytest |