mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-12-12, 23:20   #1
Chair Zhuang
 
Dec 2017

2×5 Posts
Default 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.
Chair Zhuang is offline   Reply With Quote
Old 2017-12-13, 08:49   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·2,213 Posts
Default

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
LaurV is online now   Reply With Quote
Old 2017-12-13, 14:20   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·13·137 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2017-12-13, 20:03   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

72·112 Posts
Default

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

Quote:
Originally Posted by LaurV View Post
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 View Post
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
CRGreathouse is offline   Reply With Quote
Old 2018-03-16, 23:18   #5
Chair Zhuang
 
Dec 2017

128 Posts
Default

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
Chair Zhuang is offline   Reply With Quote
Old 2018-03-17, 00:04   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Chair Zhuang View Post
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 ...
science_man_88 is offline   Reply With Quote
Old 2018-03-17, 03:40   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001010012 Posts
Default

When I get a response like
Code:
The message:
You are the messager 00000005:N3000
how do I find the result?
CRGreathouse is offline   Reply With Quote
Old 2018-03-18, 17:35   #8
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

22×151 Posts
Default

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
Stargate38 is offline   Reply With Quote
Old 2018-03-18, 18:17   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

72·112 Posts
Default

It's down for me too. It was working earlier, though, and it seemed to work. I suspect it is a legitimate pseudoprimality test.
CRGreathouse is offline   Reply With Quote
Old 2018-03-19, 00:17   #10
Chair Zhuang
 
Dec 2017

1010 Posts
Default

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.
Chair Zhuang is offline   Reply With Quote
Old 2018-03-19, 00:48   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts
Default

Quote:
Originally Posted by Chair Zhuang View Post
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


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

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

Fri Oct 23 07:50:54 UTC 2020 up 43 days, 5:01, 0 users, load averages: 1.38, 1.56, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.