IEICE TRANSACTIONS on Fundamentals
Inefficacious Conditions of the Frobenius Primality Test and Grantham's Problem
Summary :
For determining whether an input number is prime, there are two kinds of algorithms, a primality test and a primality proving. A primality test is very efficient but probabilistic, that is, there are certain errors in determining primality. On the other hand, a primality proving always gives a correct answer but it is not so efficient. Grantham proposed a very interesting problem on the Quadratic Frobenius Test (QFT) which is a primality test. If we negatively solve the problem, then we can construct a primality proving more efficient than any other existing primality proving. To solve Grantham's problem, it is important to study when QFT fails. In this paper, as the first step to solve Grantham's problem, we show two conditions on a given odd composite number n and parameters a,b of QFT such that n passes QFT for a,b. Based on these conditions, we made a computational experiment that may suggest the problem will be negatively solved. Moreover, the two conditions give two algorithms computing a pair (a,b) for which a given odd composite number n passes QFT, where n's prime factorization is known.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.11 pp.3325-3334
- Publication Date
- 2008/11/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e91-a.11.3325
- Type of Manuscript
- PAPER
- Category
- Cryptography and Information Security
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Naoyuki SHINOHARA, "Inefficacious Conditions of the Frobenius Primality Test and Grantham's Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 11, pp. 3325-3334, November 2008, doi: 10.1093/ietfec/e91-a.11.3325.
Abstract: For determining whether an input number is prime, there are two kinds of algorithms, a primality test and a primality proving. A primality test is very efficient but probabilistic, that is, there are certain errors in determining primality. On the other hand, a primality proving always gives a correct answer but it is not so efficient. Grantham proposed a very interesting problem on the Quadratic Frobenius Test (QFT) which is a primality test. If we negatively solve the problem, then we can construct a primality proving more efficient than any other existing primality proving. To solve Grantham's problem, it is important to study when QFT fails. In this paper, as the first step to solve Grantham's problem, we show two conditions on a given odd composite number n and parameters a,b of QFT such that n passes QFT for a,b. Based on these conditions, we made a computational experiment that may suggest the problem will be negatively solved. Moreover, the two conditions give two algorithms computing a pair (a,b) for which a given odd composite number n passes QFT, where n's prime factorization is known.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.11.3325/_p
Copy
@ARTICLE{e91-a_11_3325,
author={Naoyuki SHINOHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Inefficacious Conditions of the Frobenius Primality Test and Grantham's Problem},
year={2008},
volume={E91-A},
number={11},
pages={3325-3334},
abstract={For determining whether an input number is prime, there are two kinds of algorithms, a primality test and a primality proving. A primality test is very efficient but probabilistic, that is, there are certain errors in determining primality. On the other hand, a primality proving always gives a correct answer but it is not so efficient. Grantham proposed a very interesting problem on the Quadratic Frobenius Test (QFT) which is a primality test. If we negatively solve the problem, then we can construct a primality proving more efficient than any other existing primality proving. To solve Grantham's problem, it is important to study when QFT fails. In this paper, as the first step to solve Grantham's problem, we show two conditions on a given odd composite number n and parameters a,b of QFT such that n passes QFT for a,b. Based on these conditions, we made a computational experiment that may suggest the problem will be negatively solved. Moreover, the two conditions give two algorithms computing a pair (a,b) for which a given odd composite number n passes QFT, where n's prime factorization is known.},
keywords={},
doi={10.1093/ietfec/e91-a.11.3325},
ISSN={1745-1337},
month={November},}
Copy
TY - JOUR
TI - Inefficacious Conditions of the Frobenius Primality Test and Grantham's Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3325
EP - 3334
AU - Naoyuki SHINOHARA
PY - 2008
DO - 10.1093/ietfec/e91-a.11.3325
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2008
AB - For determining whether an input number is prime, there are two kinds of algorithms, a primality test and a primality proving. A primality test is very efficient but probabilistic, that is, there are certain errors in determining primality. On the other hand, a primality proving always gives a correct answer but it is not so efficient. Grantham proposed a very interesting problem on the Quadratic Frobenius Test (QFT) which is a primality test. If we negatively solve the problem, then we can construct a primality proving more efficient than any other existing primality proving. To solve Grantham's problem, it is important to study when QFT fails. In this paper, as the first step to solve Grantham's problem, we show two conditions on a given odd composite number n and parameters a,b of QFT such that n passes QFT for a,b. Based on these conditions, we made a computational experiment that may suggest the problem will be negatively solved. Moreover, the two conditions give two algorithms computing a pair (a,b) for which a given odd composite number n passes QFT, where n's prime factorization is known.
ER -
English
