mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2012-12-05, 13:21   #1
wsc812
 
Dec 2012
China

138 Posts
Arrow a new Deterministic primality testing

we know that if $q=4k+3$ ($q$ is a prime), then $(a+bI)^q=a^q+b^q(I)^{4k+3}(mod q) =a -bI$ for every gaussian integer $(a+bi)$ ,Now consider a composite $N=4k+3$ satisfies this condistion for $a+bi=3+2i$, I use Mathematica8 and find no solutison$ less than $5\cdot 10^7, can someone find a lager number for the condition . I guess it's impossible for a composite N.So this can be use for Primality test .
__________

We know that if q=4k+3 (q is a prime), then (a+bi)^q=a^q+b^q(i)^{4k+3}(mod\ q) =a -bi for every gaussian integer (a+bi) ,
Now consider a composite N=4k+3 satisfies this condistion for a+bi=3+2i,
I use Mathematica8 and find no solution less than 5 \cdot 10^7, can someone find a larger number for the condition?
I guess it's impossible for a composite N.
So this can be use for Primality test.

Last fiddled with by Batalov on 2012-12-06 at 02:30 Reason: (original message kept, tex'ed version added)
wsc812 is offline   Reply With Quote
Old 2012-12-05, 15:07   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

I haven't found counterexamples up to 10^7, except powers of 3 with odd exponent.

However, I suspect that this might be a kind of combined p-1 and p+1 test in disguise, and for those there are pairs of parameters known for which there is no known counterexample, but no proof of deterministicness (is that a word?), either. See for example http://mathworld.wolfram.com/Baillie...alityTest.html

Last fiddled with by akruppa on 2013-01-18 at 10:36 Reason: now->no
akruppa is offline   Reply With Quote
Old 2012-12-05, 15:32   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,699 Posts
Default

Earlier this year, I tested 2+i for n==3 (mod 4) up to 10^13 without finding a counterexample

Last fiddled with by paulunderwood on 2012-12-05 at 15:37
paulunderwood is offline   Reply With Quote
Old 2012-12-05, 18:46   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

139710 Posts
Default

This would be an AKS type test: n=4k+3 is prime iff (2*x+3)^n==3-2*x mod (x^2+1,n)

To see this notice that the minimal polynom of I is x^2+1 (and not x^4-1). This subject is an old topic not to use that many polynom tests for AKS, only a few. Here it would mean only one polynom.
R. Gerbicz is offline   Reply With Quote
Old 2012-12-05, 21:24   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

1151810 Posts
Default

Quote:
Originally Posted by akruppa View Post
but no proof of deterministicness (is that a word?)
My guess would be that the appropriate "suffixing to imply the property of being ___" here is analogous to the one for e.g. "domestic". I love words that, even when spelled correctly, just sound plain wrong: coolth ... gruntled ... "deterministicity" seems a fine addition to this distinguished pantheon.

------------------------------

Edit: Of course using the alternative analogy with e.g. optimistic/pessimistic one arrives at the accepted suffixing here, "determinism" - but where's the fun in that?

Last fiddled with by ewmayer on 2012-12-05 at 22:09
ewmayer is offline   Reply With Quote
Old 2012-12-06, 03:58   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25×3×7×13 Posts
Default

[offtopic]
related to that I really have a problem with "primality" because is always underlined red by the spellchecker and that "piss me off" for such a simple word. I tried different forms, even using "r" or "double l" in all variations, but all ended up in being underlined, and I concluded that either there is no word like that, either I am dumb, or the speller is not so clever, therefore I continued to use "primality". So, what is the correct form?
[/offtopic]

Last fiddled with by LaurV on 2012-12-06 at 04:00 Reason: [ot] tags
LaurV is offline   Reply With Quote
Old 2012-12-06, 04:26   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·13·443 Posts
Default

Quote:
Originally Posted by LaurV View Post
[offtopic]
related to that I really have a problem with "primality" because is always underlined red by the spellchecker and that "piss me off" for such a simple word. I tried different forms, even using "r" or "double l" in all variations, but all ended up in being underlined, and I concluded that either there is no word like that, either I am dumb, or the speller is not so clever, therefore I continued to use "primality". So, what is the correct form?
[/offtopic]
I like to alternate between "primerificity" and "primistitude", with an occasional US-pledge-of-allegiance-recalling "indivisibility" (with "by anything other than 1 and n" implied) to keep the spellcheckers from rioting.
ewmayer is offline   Reply With Quote
Old 2012-12-06, 04:38   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

912610 Posts
Default

Quote:
Originally Posted by LaurV View Post
[offtopic]
related to that I really have a problem with "primality" because is always underlined red by the spellchecker and that "piss me off" for such a simple word. I tried different forms, even using "r" or "double l" in all variations, but all ended up in being underlined, and I concluded that either there is no word like that, either I am dumb, or the speller is not so clever, therefore I continued to use "primality". So, what is the correct form?
[/offtopic]
That was a primal scream.

Have you tried: right-click on the word primality, and "add to dictionary"?

Same with heteroscedacity, pseudomarkers, telomeric ...and an endless score of biological and statistical terms. Add them once and never be bothered again. Maybe.

Last fiddled with by Batalov on 2012-12-06 at 04:39 Reason: (I need a spellchecker, too)
Batalov is offline   Reply With Quote
Old 2012-12-06, 07:36   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25·3·7·13 Posts
Default

Quote:
Originally Posted by Batalov View Post
"add to dictionary"
Did that for colleagues' names (never remember Thai names!) and other common words which I know they are not English, and even some technical words (same as your biology stuff, but for me is microcontroller, photodiode, etc) which I don't give a darn if they are English or not, as long as I need to use them and everybody understand them. Including my family name, which the auto-substitute was always replacing it with a bad English word, hehe. Those are all complex** words! But primality? grrr.

** That to stay on topic with complex numbers

Now to really stay on topic, for every odd prime is easy to show that according with its modularity to 4, the expression (3+2i)^n is either 3+2i, either 3-2i. Putting this in a pari line:

Code:
gp > n=3; a=3+2*I; while((n+=2)<10^6, if(n%4==3, c=3-2*I; b=real(d=a^n)%n-(n-imag(d))%n*I, c=3+2*I; b=real(d=a^n)%n+imag(d)%n*I); if(b==c&&!isprime(n), print(n)))
1105
2465
10585
29341
41041
46657
115921
etc
(interrupted, took longer then 5 minutes, a function complex_power_mod would be need to make the mod after each iterations, otherwise working with so big numbers is very slow)

Now, all that appear in the list are 1 (mod 4), but there is no reason why 3 (mod 4) numbers won't appear if we go higher. We also can change the complex base, to get some other numbers which "pass". We can see this works right, by removing the "&&!isprime()" call then it prints all primes. For example, with 2+i, there are the same as above, plus few additional: 15841 is one of them.

Last fiddled with by LaurV on 2012-12-06 at 07:41
LaurV is offline   Reply With Quote
Old 2012-12-06, 07:56   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

210408 Posts
Default

Quote:
Originally Posted by LaurV View Post
a function complex_power_mod would be need
It turned out there is no big deal to implement this. No idea if pari has one already. I made it recursive, if power is even, call the function with power>>1, square, if power is odd multiply, take mod at the end. I put that in a "cIsPrime(b,n)" function, which will return 1 if n is probable prime base b, with b being a complex number.

The nicer part is that now, a complex number can be one with the imaginary part being zero . Do you recognize these numbers? (please scroll down into the code section)

Code:
gp> forstep(n=3,10^6,2, if(cIsPrime(2,n)&&!isprime(n),print(n)))
341
561
645
1105
1387
1729
1905
2047
2465
2701
2821
3277
4033
4369
4371
*** <break, snip, this is very fast anyhow>  ***

gp > forstep(n=3,10^6,2, if(cIsPrime(3+2*I,n)&&!isprime(n),print(n)))
1105
2465
10585
29341
41041
46657
*** <break, snip, this is very fast anyhow>  ***

// <This is a beautiful one!> :
gp > forstep(n=3,10^6,2, if(cIsPrime(1+I,n)&&!isprime(n),print(n)))
561
1105
1729
1905
2047
2465
3277
4033
4681
6601
8321
8481
10585
12801
15841
16705
<etc>

Last fiddled with by LaurV on 2012-12-06 at 08:01 Reason: cut the lists, too long code section, bolded, red color
LaurV is offline   Reply With Quote
Old 2012-12-06, 08:48   #11
wsc812
 
Dec 2012
China

B16 Posts
Question

is algorithm complexity O(log(N)) For N=4k+3? we may not select base a+bi, a= b for effectively testing, and calculate (a+bi)^{N+1}=a^2+b^2 (mod N)
instead of (a+bi)^N=a-bi(mod N)

Last fiddled with by wsc812 on 2012-12-06 at 09:07
wsc812 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Theoretical (vs. Proficient/Practical) Deterministic Primality Test a1call Miscellaneous Math 194 2018-03-19 05:54
Primality testing non-Mersennes lukerichards Software 8 2018-01-24 22:30
Testing an expression for primality 1260 Software 17 2015-08-28 01:35
Testing Mersenne cofactors for primality? CRGreathouse Computer Science & Computational Number Theory 18 2013-06-08 19:12
a new primality testing method jasong Math 1 2007-11-06 21:46

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

Tue Sep 22 21:42:41 UTC 2020 up 12 days, 18:53, 0 users, load averages: 1.46, 1.57, 1.61

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.