The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
입력 숫자가 소수인지 여부를 결정하는 데에는 두 가지 종류의 알고리즘이 있습니다. 소수성 테스트 및 소수 증명. 에이 소수성 테스트 매우 효율적이지만 확률적입니다. 즉, 소수를 결정하는 데 특정 오류가 있습니다. 반면에, 소수 증명 항상 정답을 제시하지만 그다지 효율적이지는 않습니다. Grantham은 Quadratic Frobenius Test에서 매우 흥미로운 문제를 제안했습니다.QFT) 이는 소수성 테스트. 문제를 부정적으로 해결하면 다음과 같은 결과를 얻을 수 있습니다. 소수 증명 기존의 어떤 것보다 효율적이다. 소수 증명. Grantham의 문제를 해결하려면 언제 연구해야 하는지가 중요합니다. QFT 실패합니다. 본 논문에서는 Grantham 문제를 해결하기 위한 첫 번째 단계로 주어진 홀수 합성수에 대한 두 가지 조건을 제시합니다. n 및 매개 변수 a,b of QFT 그렇게 n 패스 QFT for a,b. 이러한 조건을 바탕으로 우리는 문제가 부정적으로 해결될 것이라고 제안할 수 있는 계산 실험을 수행했습니다. 더욱이, 두 조건은 쌍을 계산하는 두 가지 알고리즘을 제공합니다(a,b) 주어진 홀수 합성수에 대해 n 패스 QFT어디로 n의 소인수분해가 알려져 있습니다.
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.
부
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
부
@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},}
부
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 -