GQQ: a "deterministic" "primality" test in O(ln n)^2

Chair Zhuang · 2017-12-12, 23:20

There is a fast and deterministic primality test at the sit: lizhuanggarden.com
Time complexity:O(ln n)2. No pseudoprime.
Try it.

LaurV · 2017-12-13, 08:49

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.

Dr Sardonicus · 2017-12-13, 14:20

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.

CRGreathouse · 2017-12-13, 20:03

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?

Chair Zhuang · 2018-03-16, 23:18

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^(n-1) =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^10-1 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^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.

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

science_man_88 · 2018-03-17, 00:04

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 ...

CRGreathouse · 2018-03-17, 03:40

When I get a response like

Code:

The message:
You are the messager 00000005:N3000

how do I find the result?

Stargate38 · 2018-03-18, 17:35

Chair Zhuang's web site isn't working for me. All I get is "This page isn't working". What happened to it?

CRGreathouse · 2018-03-18, 18:17

It's down for me too. It was working earlier, though, and it seemed to work. I suspect it is a legitimate pseudoprimality test.

Chair Zhuang · 2018-03-19, 00:17

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.

science_man_88 · 2018-03-19, 00:48

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.

2017-12-12, 23:20	#1
Chair Zhuang Dec 2017 1010₂ 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 10100000100111₂ 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

2018-03-17, 03:40	#7
CRGreathouse Aug 2006 5,987 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 2F1₁₆ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
"New" primality test/check	gophne	gophne	272	2018-04-24 13:16
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
"New primality proving test from Alex Petrov"	ewmayer	Math	11	2007-04-23 19:07
P-1 B1/B2 selection with "Test=" vs "Pfactor="	James Heinrich	Software	2	2005-03-19 21:58
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

2018-03-16, 23:18	#5
Chair Zhuang Dec 2017 A₁₆ 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^(n-1) =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^10-1 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^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=pq, 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. 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

2018-03-18, 18:17	#9
CRGreathouse Aug 2006 13543₈ 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 2×5 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=pq=40751122251=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=pq=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 5956859568-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.