A probable prime test with high confidence (Q1273196): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Created claim: Wikidata QID (P12): Q56673772, #quickstatements; #temporary_batch_1711574657256 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56673772 / rank | |||
Normal rank |
Revision as of 00:05, 28 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A probable prime test with high confidence |
scientific article |
Statements
A probable prime test with high confidence (English)
0 references
16 February 2000
0 references
The Rabin strong probable prime test of an integer \(n\) has a probability of 1/4 for failing to detect compositeness. The author develops an improvement running about three times as long but with error of about 1/7710. This consists of a Lucas-type adaptation called the ``quadratic Frobenius tests.'' For \(n\) prime and \(\xi\) (with conjugate \(\xi')\) roots of the unfactorable \(x^2-bx-c\) it is easily seen that in \(\mathbb{F}_{n^2}\), with \(\eta=\xi^{(n+1)/2}\), then \(\eta^2(=\xi^n\cdot\xi)\equiv\xi'\xi=-c\) (hence ``Frobenius''). If additionally \((-c\mid n)=-1\), then \(\eta\notin \mathbb{F}_n\). At the same time \(\xi^{(n^2-1)}\equiv 1\), and this works on the even power in \(n^2-1\) (rather than \(n-1\) as in the probable prime test). The failure analysis is very sophisticated. For the mixed strategy, the author cites the work of \textit{C. Pomerance}, \textit{J. L. Selfridge} and \textit{S. Wagstaff} [The pseudoprimes to \(25\cdot 10^9\), Math. Comput. 35, 1003-1026 (1980; Zbl 0444.10007)].
0 references
Lucas test
0 references
quadratic Frobenius test
0 references
strong probable prime test
0 references
failure analysis
0 references