Inefficacious Conditions of the Frobenius Primality Test and Grantham's Problem

概要

論文の詳細を見る
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 Granthams problem, it is important to study when QFT fails. In this paper, as the first step to solve Granthams 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 ns prime factorization is known.
（社）電子情報通信学会の論文
2008-11-01