The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -