20171212, 23:20  #1 
Dec 2017
2·5 Posts 
GQQ: a "deterministic" "primality" test in O(ln n)^2
There is a fast and deterministic primality test at the sit: lizhuanggarden.com
Time complexity:O(ln n)2. No pseudoprime. Try it. 
20171213, 08:49  #2 
Romulan Interpreter
Jun 2011
Thailand
2·4,679 Posts 
First, you have to tell us what is a "Carchael" number, so we know. . And generally, check the terminology you use.
Second, for Carmichael numbers, the only witnesses are those that contain a factor. Because they will ring "prp" for all other bases. Therefore, if you have such algorithm that finds "liars" (??) for Carmichael numbers in polylog time, you just have an algorithm to factor numbers in polylog time. Any numbers. This is not only about proving primality (which we know is polynomial anyhow), but it is about a lot more, you just add some calculus to it, and a GCD, and you have proper factors of the numbers. What you claim may be true, but it is unbelievable. Think about it! (beside of the fact that you would need "witnesses" and not "liars", to eliminate any pseudoprimes). Nobody will take you seriously here around, with such a claim, and "input serial numbers" in that page, after which one has to wait for the next day to see if 561 is prime or not. Last fiddled with by LaurV on 20171213 at 09:03 
20171213, 14:20  #3  
Feb 2017
Nowhere
3·1,481 Posts 
Quote:
For example, using the base 2 with 561, we have ? Mod(2,561)^560 %1 = Mod(1, 561) ? Mod(2,561)^(560/2) %2 = Mod(1, 561) ? Mod(2,561)^(560/4) %3 = Mod(67, 561) ? gcd(66,561) %4 = 33 ? gcd(68,561) %5 = 17 There are a couple of links in my post to a thread on Carmichael numbers which may be pertinent. Bottom line  if the sequence you're using is a linear recurrence with constant coefficients, it's not a deterministic primality test. Last fiddled with by Dr Sardonicus on 20171213 at 14:54 

20171213, 20:03  #4  
Aug 2006
3^{2}·5·7·19 Posts 
I'd find the page much more interesting if it actually presented an algorithm.
Quote:
Edit: Dr Sardonicus beat me to it. I'm not even sure how the form is supposed to work. We request a serial number, send between 1 and 10,000 queries, wait a day... then what? Where do the results appear? Last fiddled with by CRGreathouse on 20171213 at 20:04 

20180316, 23:18  #5 
Dec 2017
2×5 Posts 
Sorry! I have be banned for serval month. I should read the rules about this forum again. Now I am here again and reply for you.
During the banned period, I have changed the way to input the tested number with +  * / ^ ( and ) and the showed way for its resualt, online. And the site adds two function, searching continuous primes and searching strong primes. Thank you for your words, LaurV. Mathematics is a rigorous science and I'm glad your critical to my post. Thank you again. Carmichael number is a integer number "n" that any integer base "a" that coprime with "n" make a^(n1) =1 (mod n) holding, e.g. 561. They have many forms. Reference: en.wikipedia.org/wiki/Carmichael_number I'm not good at English. If I mistake your means or the words I wrote are unclear, please reply me again. Thank you. Thank for your words and the example, 561,and you offered a example to explain for Laur. Thank you again, Dr Sardonicus. I have been researching the primality test and the factorization for general numbers and not the numbers that are on the special forms. The sequence GQQ Primality Test is not linar. It covers the Lucas sequence and the Fermat sequence as the page on my site says. I have tested the odd numbers from 3 to 10^101 with it. I sieved the number from 2 to 10^10 with the sieve of Eratosthenes for prime numbers first, then tested the primality of the odd numbers from 3 to 10^101 with GQQ Primality Test to contrast the primality that the sieve of Eratosthenes did above. After 4 days, my computer stopped at 10^10+1. To the same base "a", each prime number makes its sequence in GQQ Primality Test. Let a composite number n=p*q, and select a base "a" that calculated out from n. If n+1 isn't divided evenly by p+1 or q1, n is composite. And if n+1 is divided evenly by p+1 and q1, the value at (n+1)/2th is another number that can be calculated out by Chinese Remainder Theorem, and n is composite. So it's a deterministic primality test. Thank you for you being interested in GQQ algorithm and telling about Carmichael number, CRGreathouse. I'm sorry that I ignored the input on the page on my site. Now, I have made 7 operators, +  * / ( ) and ^. I have been making lists of primes that are the first 10,000 primes starting from 2^n. Because there is a list of primes from 2 up to 10^12 on the web, I list the first 10,000 primes from 2^39 , 2^40 and 2^41 that can be tested by the software,Excel. Afterward I will make the lists that n>=256 that used on encryption. Thanks. Chair Zhuang 2018/3/17 
20180317, 00:04  #6  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20180317, 03:40  #7 
Aug 2006
1761_{16} Posts 
When I get a response like
Code:
The message: You are the messager 00000005:N3000 
20180318, 17:35  #8 
"Daniel Jackson"
May 2011
14285714285714285714
287_{16} Posts 
Chair Zhuang's web site isn't working for me. All I get is "This page isn't working". What happened to it?
Last fiddled with by Stargate38 on 20180318 at 17:37 
20180318, 18:17  #9 
Aug 2006
3^{2}×5×7×19 Posts 
It's down for me too. It was working earlier, though, and it seemed to work. I suspect it is a legitimate pseudoprimality test.

20180319, 00:17  #10 
Dec 2017
10_{10} Posts 
To science_man_88
Thanks! 1. In empirically I found out all prime numbers from 2 to 10^10 with the Sieve of Eratosthenes first, and marked their primality 1 and the composite numbers 1. Then GQQ Primality Test tests each odd number. If GQQ tests a number be prime it marks the number primality 1, if not 1. Then get the primality (1 or 1) of the number from the Sieveof Eratosthenes timeing the primality (1 or 1) of the number from GQQ. If the value is 1 GQQ passes detection, if not my computer will stop at the number and GQQ doesn't pass detection. So In empirically, the GQQ algorithm is effective to test the primality of each odd from 3 to 10^101. 2. In theoretically Let's see the Fermat sequence first. To the same base "a" each prime makes its sequence. For example prime p=40751 and prime q=122251, base "a"=16644. They are their sequences below: p=40751 base 16644: 16644,38189,24369,2933,..... The value number is 1 at item (407511). q=122251 base 16644: 16644,1970,25412,91119,........... The value number is 1 at item (1222511). Now a number is n=p*q=40751*122251=4981850501,........ Let base is also 16644. Its sequence is below. n=4981850501 base 16644:16644,277022736,2554704559,408653961,............ The value number is also 1 at item (49818505011). so 4981850501 is a pseudoprime to base 16644. To the number 4981850501, the congruences mod(r^3,4981850501), r is any integer and GCD(r,n)=1, are all its liar witness. In GQQ, to the same base "a" each prime also makes its sequence. Let's take the same example p=40751 and q=122251, and calculate the base, it just is 16644. Their sequences are below: .p=40751 base 16644: 1,17409,10638,36705,3788,..... The value numbers are 59568 and 59568 at item (40751+1)/2 and next. q=122251 base 16644: 1,83349,83494,74553,56287,...... The value numbers are 1 and 83349 at item (122251+1)/2 and next. Now a number is also n=p*q=4981850501 and calculate the base a. It is also 16644. Its squence is below. 1,541037891,301348201,469365156,195624731,....... The value numbers are 4400941 and 559793876 at item (4981850501+1)/2 and next. In the case get the values at item (40751+1)/2 and next of p sequence. They are 59568 and 59568. If the two numbers are the same calculate the congruence 59568*5956840751*k. As the value is equal a special number, 40751 is prime. In the other, q sequence, because base 16644 is not its right base the values at the item (122251+1)/2 and next are 1 and 83349 and we can't decide its primality. In the n sequence base 16644 is its right base, but the value at the item (4981850501+1)/2 and next are 4400941 and 559793876. They are deffrent, so 4981850501 is not prime. In fact Fermat sequence is Level 1 sequence and its cycle numbers are p1 and the factors of p1. Quifu sequence used by GQQ is Level 2 sequence and its cycle numbers are p^21 and the factors of p^21. There are many sequence in the sequence system that I call it Chair sequence system. In Level 3 sequence its cycle numbers are p^31, p^21 and their factors. Level 4 sequence's are p^41, p^3 1,p^21 and their factors. To CRGreathouse Thanks I'm not good at English and the program. There must be errors in my program. Can you tell me the input you did so that I can check my program quickly. By the way GQQ Primality Test is a deterministic primality test and it would make errors because of my program. My web is usually break. I will take care of it. 
20180319, 00:48  #11  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
"New" primality test/check  gophne  gophne  272  20180424 13:16 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"New primality proving test from Alex Petrov"  ewmayer  Math  11  20070423 19:07 
P1 B1/B2 selection with "Test=" vs "Pfactor="  James Heinrich  Software  2  20050319 21:58 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 