3.237.66.86

lizhuanggarden.comsince 2017-10-07

GQQ Primality Test

I'm not good at English. Please send messages to me where the semantic meaning is unclear.

The Primality Test is named GQQ after Guixiu Zhang, my mother's name, and Qifu and Qingzhi, my two elder brothers' names.

GQQ Primality Test is a deterministic primality testing algorithm based on a special sequence. The special sequence covers Fermat sequence , Lucase sequence and more. It is called Qifu sequence, named after Qifu, my elder brother, as the Lucase sequence is called Lucase sequence. Through only a deterministic key number, which is without randomness, from calculating with the tested number, GQQ Primality Test can tell the primality of the tested number.

In Fermat Primality Test, if a ^{p − 1} ≡ 1 (mod p), then the modular number p is a probable prime number. For example, from 2^{7 − 1} ≡ 1 (mod 7) and 3^{91 − 1} ≡ 1 (mod 91), we know 7 can be prime but 91 is not. But in GQQ Primality Test, the tested value is a square root. For example, (f(k)_{n})^{2} ≡ 2 (mod 7), where f(k)_{n} means the nth value in Qifu sequence of GQQ Primality Test and n = (7 + 1) ∕ 2. Notice that in Fermat Primality Test, we get the (p − 1)th value of the sequence, a ^{p − 1} ≡ 1 (mod p),and in GQQ Primality Test, we get the (p+1)/2th value of Qifu sequence. One is " - " and the other is " + ". In GQQ Primality Test, analogous to Fermat Primality Test, if the base a is not 1, the (p+1)/2th value would not be 1 or p-1. So we will not mistake the tested number as a prime number when it is a composite number. In fact, the seqence in Fermat Primality Test is only a special case of Qifu sequence.

The Miller-Rabin Primality Test tests the value at (p-1)/2^{r}th, so it has the same promblem as Fermat Primality Test does.

In Fermat Primality Test, where n=p_{1}*p_{2}*····*p_{i} and n-1 is divided evenly by LCM(f(p_{1}-1)，f(p_{2}-1)，····,f(p_{i}-1)), it exists a strong liar a making a ^{n-1}≡ 1 (mod n) holding. The f(p_{i}-1) means any factor of p_{i}-1 and exists a base a _{i} corresponding it. The base a can be obtained by Chinese remainder theorem. In the test, no matter n being single factor (n is a prime number) or multi-factor (n is a composite number), the equation a ^{n-1}≡ 1 (mod n) always holds.

For example:n=11*23=253. Let f(11-1)=2, a _{1}=10, f(23-1)=1, a _{2}=1. LCM(2,1)=2, n-1=253-1=252, and 252≡ 0 (mod 2). The strong liar a =208 that is calculated by Chinese remainder theorem. From the example, GCD((11-1)/2,(23-1)/2)=1, we see a fact that each composite allways has its strong liar. Another example: n=11*23*29=7337. Let f(11-1)=1, a _{1}=1, f(23-1)=1, a _{2}=1 and f(29-1)=7, a _{3}=16. LCM(1,1,7)=7, n-1=7337-1=7336, and 7336≡ 0 (mod 7). The strong liar a =2278 that is calculated by Chinese remainder theorem. Note that 11*23=36*7+1 and 29=4*7+1, so (11*23)*29-1=7*k. Now we can say that Fermat Primality Test is a useless algorithm to decide the primality of a number. It is just fortunate for it deciding,but has great fortunate for most numbers.

To discuss miller-Rabin Primality Test is accorded to the way to obtain the strong liar a above. To keep with a^{d}≡1 (mod n), we take each f(p_{i}-1) being odd factor. If the least common multiple from these odd factors divide evenly n-1 we can obtain the strong liar a by Chinese remainder theorem from these a _{i} corresponding each odd factor. To keep with a ^{2rd}≡-1 (mod n), we take each f(p_{i}-1) being the same factor and the factor exactly divides n-1. Calculate the a that is the strong liar.

Of course, we ought to consider the situation in GQQ Primality Test. To discuss GQQ Primality Test is accorded to the way to obtain the strong liar a above. Due to we test the value at (n+1)/2th in Qifu sequence, there is no problm about Fermat strong liar or Miller-Rabin strong liar in GQQ Primality Test. You can prove it yourself if you are interested with it. Here is no superfluous to it and we are going to discuss about GQQ strong liar. Because GQQ Primality Test is with Qifu sequence and the base a is calculated from n and not selected randomly, and if n+1 is divided evenly by the least common multiple from f(p_{i}+1), the value at (n+1)th in Qifu sequence is not the value that we think but is calculated by Chinese remainder theorem since n is multiple factors. As the base a is less than the square root of n. It is a linear relationship between this value and n. But if n is single factor, regardless of it being big or small, the value is a square root that is fixed. So there is no problm about pseudoprime in GQQ Primality Test as long as the base a is less than the square root of n and more than 1.

Is GQQ Primality Test combined with Fermat Primality Test and AKS Primality Test? We can try it with Carmichael number and others. The time complexity of GQQ Primality Test is O(ln n)^{2}. Testing the Mersenne prime number 2^{4253} − 1 took only 0.21556 seconds excluding the time to input and output on my PC with Core i5-2400 (3.10 GHz). But the time compleity of AKS Primality Test is O(log (n))^{6} at least. Can we say the GQQ Primality Test is a fast and determinstic primality Test If it testing a large Carchael number takes a short time and says the number being composite?

Baillie-PSW combines strong Fermat probable prime test to base 2 with Lucas probable prime test. But why does it need to combines two theory? And other primality tests combine Fermat Primality Test or Miller-Rabin Primality Test with Lucase Sequence or Fibonacci Test. But why? GQQ Primality Test is a single theory. It clearly tell us the reason why a odd number is prime or composite.

I have tested GQQ Primality Test by the sieve of Eratosthenes with odd numbers from 3 to 10^10-1. All pass. Primes are primes, composites are composites. GQQ Primality Test suits to test general numbers. To Proth number, Riesel number, Sierpinski number and others on the special forms, GQQ Primality Test is not suitable for them. Because they have their respective algorithm based on their forms and are faster. GQQ Primality Test suits to test the prime numbers used on RSA's encryption and researching about primes.

Of course, you would think whether Qifu sequence could factor composite numbers as I did. It disappoints us. I started studying the factorization in 2003, and discovered Qifu sequence in November 2013. After half a year I found GQQ Primality Test. Three and half years going by, I still have not found a method to factor composite numbers with Qifu sequence.

Excuse me that I'm not going to publish the details of GQQ Primality Test currently. But I will test the primality of the number you inputed for you.

The testings are free, and as you found a composite/prime number which GQQ Primality Test tested it prime/composite I will give you who first found it a prize, US$100. One number only gets one prize.

A GQQ-based prime sieve (in the input intervals) will be avaliable soon.

Thanks to 東東's lover for her help.

Writted by Chair Zhuang 2017/10/07