mersenneforum.org GQQ: a "deterministic" "primality" test in O(ln n)^2
 Register FAQ Search Today's Posts Mark Forums Read

 2017-12-12, 23:20 #1 Chair Zhuang   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.
 2017-12-13, 08:49 #2 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 233658 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 poly-log time, you just have an algorithm to factor numbers in poly-log 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 2017-12-13 at 09:03
2017-12-13, 14:20   #3
Dr Sardonicus

Feb 2017
Nowhere

22·1,459 Posts

Quote:
 Originally Posted by LaurV Second, for Carmichael numbers, the only witnesses are those that contain a factor. Because they will ring "prp" for all other bases.
Actually, this isn't necessarily so, particularly if you use a Rabin-Miller test. It's reasonably likely that, as you keep dividing more factors of 2 out of n-1, you'll get a residue that isn't 1 -- and the first residue you hit that isn't 1, also is not -1 -- in which case, you have found a proper factorization.

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 2017-12-13 at 14:54

2017-12-13, 20:03   #4
CRGreathouse

Aug 2006

3·1,993 Posts

I'd find the page much more interesting if it actually presented an algorithm.

Quote:
 Originally Posted by LaurV 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 poly-log time, you just have an algorithm to factor numbers in poly-log time. Any numbers.
Carmichael numbers can already be factored in random polynomial time using Miller-Rabin (and in polynomial time under GRH).

Edit: Dr Sardonicus beat me to it.

Quote:
 Originally Posted by LaurV 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.
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 2017-12-13 at 20:04

2018-03-17, 00:04   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by Chair Zhuang 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^10-1 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 q-1, n is composite. And if n+1 is divided evenly by p+1 and q-1, 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. ... Thanks. Chair Zhuang 2018/3/17
Maybe explain what it's doing ...

 2018-03-17, 03:40 #7 CRGreathouse     Aug 2006 3·1,993 Posts When I get a response like Code: The message: You are the messager 00000005:N3000 how do I find the result?
 2018-03-18, 17:35 #8 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 22·3·59 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 2018-03-18 at 17:37
 2018-03-18, 18:17 #9 CRGreathouse     Aug 2006 3×1,993 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.
 2018-03-19, 00:17 #10 Chair Zhuang   Dec 2017 128 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^10-1. 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 (40751-1). q=122251 base 16644: 16644,1970,25412,91119,........... The value number is 1 at item (122251-1). 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 (4981850501-1). 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*59568-40751*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 p-1 and the factors of p-1. Quifu sequence used by GQQ is Level 2 sequence and its cycle numbers are p^2-1 and the factors of p^2-1. There are many sequence in the sequence system that I call it Chair sequence system. In Level 3 sequence its cycle numbers are p^3-1, p^2-1 and their factors. Level 4 sequence's are p^4-1, p^3- 1,p^2-1 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.
2018-03-19, 00:48   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Chair Zhuang 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^10-1. 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 (40751-1). q=122251 base 16644: 16644,1970,25412,91119,........... The value number is 1 at item (122251-1). 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 (4981850501-1). 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*59568-40751*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 p-1 and the factors of p-1. Quifu sequence used by GQQ is Level 2 sequence and its cycle numbers are p^2-1 and the factors of p^2-1. There are many sequence in the sequence system that I call it Chair sequence system. In Level 3 sequence its cycle numbers are p^3-1, p^2-1 and their factors. Level 4 sequence's are p^4-1, p^3- 1,p^2-1 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.
So basically a suped up fermat test. p-1 factors into them all last I checked.

 Similar Threads Thread Thread Starter Forum Replies Last Post gophne gophne 272 2018-04-24 13:16 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 ewmayer Math 11 2007-04-23 19:07 James Heinrich Software 2 2005-03-19 21:58 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 07:42.

Tue Jul 5 07:42:57 UTC 2022 up 82 days, 5:44, 0 users, load averages: 1.57, 1.75, 1.70