mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-12-06, 19:26   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2×33×5 Posts
Default (a+bi)^p, prime test in C

A peaceful evening,


i think prime test similear to the little Fermat may be possible in the complex plane,


Are there some literature of pdfs to this topic availible ?


Greetings

Bernhard
bhelmes is offline   Reply With Quote
Old 2018-12-06, 22:14   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

A sad day. Imagine that - to be banned from Google, too?

Maybe this will help - http://bfy.tw/LEFG
Batalov is offline   Reply With Quote
Old 2018-12-28, 19:19   #3
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2×33×5 Posts
Default

I am too stupid to find some prime tests with complex numbers,
or prime tests with adjoined square roots from google or wikipidia.


But as this mathematical subject seems to be interesting for other
mathematicians, i would repush this thread.


As (a+bI)^p = (a-bI) mod p; for p=3 mod 4 otherwise
(a+bI)^p = a+bI mod p for p=1 mod 4
is right for p element P; a, b element N


Or A=sqrt(2)
As (a+bA)^p = (a^p+(b^p)A^p) mod p

is right for p element P


These tests with two variable seem to me stronger than the fermat test with one variable.


I thought there must be some mathematicians who have treated this

subject already.



Greetings from the primetests

Bernhard


@Batalov, if the day is really bad and sad, try to throw a look of

the perspective of a small and blue smurf,

some times the change of the perspective

can help to get another feeling toward the subject.
bhelmes is offline   Reply With Quote
Old 2018-12-28, 19:28   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by bhelmes View Post
I am too stupid to find some prime tests with complex numbers,
or prime tests with adjoined square roots from google or wikipidia.


But as this mathematical subject seems to be interesting for other
mathematicians, i would repush this thread.


As (a+bI)^p = (a-bI) mod p; for p=3 mod 4 otherwise
(a+bI)^p = a+bI mod p for p=1 mod 4
is right for p element P; a, b element N


Or A=sqrt(2)
As (a+bA)^p = (a^p+(b^p)A^p) mod p

is right for p element P


These tests with two variable seem to me stronger than the fermat test with one variable.


I thought there must be some mathematicians who have treated this

subject already.



Greetings from the primetests

Bernhard


@Batalov, if the day is really bad and sad, try to throw a look of

the perspective of a small and blue smurf,

some times the change of the perspective

can help to get another feeling toward the subject.
https://www.mersenneforum.org/showthread.php?t=21799
science_man_88 is offline   Reply With Quote
Old 2018-12-28, 20:29   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

Quote:
Originally Posted by bhelmes View Post
These tests with two variable seem to me stronger than the fermat test with one variable.
These tests are simply two Fermat tests run together at the same time - at the expense of >2 times more time (than the two separate tests) and ~2 times more space.
It is obvious - to anyone with a pencil, a sheet of paper and a few minutes to spare.
Just write down (a+b*I)^p = a^p + b^p * I^p =?= a + b * I^p (mod p)... <==> a^p==a (mod p) and b^p==b (mod p)

So, "These tests with two variable seem to me stronger than..." are worse than running two tests. Separately.

Would you please think for just a minute before you write?
Batalov is offline   Reply With Quote
Old 2018-12-29, 17:57   #6
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2·33·5 Posts
Default

Let us see, where the misunderstanding comes from:


1. You assume that p is a prime
2. You simplify the equation
(The missings binomialcoefficients are equal 0, if p is prime
3. You conclude that two singles fermat tests are the same.


For a prime test i assume
1. that p is either prime or not
2. if p is not a prime, the complex test could not be simplify


From the mathematical point there is a difference between our assuming conditions.


The statement that the complex test is stronger than the fermat test
bases on the number of pseudoprimes which pass the test.


And you are right that the complex test is more expensive than two Fermat test, by the way i think it belong to three Selfridges.


Normally i think about the topics i deal and sleep a night about it.


Greetings from the complex plane

Bernhard

Last fiddled with by bhelmes on 2018-12-29 at 18:04
bhelmes is offline   Reply With Quote
Old 2018-12-29, 19:23   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D5616 Posts
Default

Quote:
Originally Posted by bhelmes View Post
And you are right that the complex test is more expensive than two Fermat test, by the way i think it belong to three Selfridges.
... "<==> a^p==a (mod p) and b^p==b (mod p)"

It is 2 Selfridges. For a list of candidates it is way more efficient to do an a-PRP test, then a b-PRP test.

Last fiddled with by paulunderwood on 2018-12-29 at 19:24
paulunderwood is online now   Reply With Quote
Old 2018-12-29, 20:28   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
For a list of candidates it is way more efficient to do an a-PRP test, then a b-PRP test.
Right. This will be (1+ε) Selfridges. You will still miss Carmichaels, but you will need the second b-PRP test very rarely.
Batalov is offline   Reply With Quote
Old 2018-12-30, 17:21   #9
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2·33·5 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

Nice to see you again in this conversation, i think that you could solve some problems about this topic.


1. Let p=3 mod 4: (a+bI)^(p²-1)=1 mod p; if p element P

(a+bI)^p = (a-bI) mod p


Is the second test a p-1 or a p+1 test ?


2. Let A=sqrt(2):



(a+bA)^p = a+b(A^p) mod p; if p element P



Is this test stronger than the equivalent in the complex plane ?

(I think the binominalcoefficients are symmetric and therefore

it migth be better to weight one variable)


3. Let c^[(p-1)/2]=p-1 mod p (a non quadratic residue)
Then (a+b(sqrt(c))^p=a+b[sqrt(c)] mod p; if p element P


I think this strengthen the test of 2.


Greetings from the primitive roots

Bernhard
bhelmes is offline   Reply With Quote
Old 2019-01-03, 17:44   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×569 Posts
Default

Serge gave you a clue with "=?=" above. You can just do 1 selfridge tests as the result of the binomial expansion over p.
paulunderwood is online now   Reply With Quote
Old 2019-01-03, 23:51   #11
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2×33×5 Posts
Default

A peaceful night for you,


I think (a+bI)^p=a-bI mod p for p=3 mod 4 is a p+1 test:


For example (2+11I)^16=1 mod 31


Greetings from the complex plane

Bernhard
bhelmes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The ultimate prime test ? Carl Fischbach Miscellaneous Math 33 2009-09-11 20:49
Prime test 3^n-2 henryzz Software 11 2008-02-12 18:30
another mersenne prime test jocelynl Math 8 2006-10-20 19:36
Easy Prime Test Robert Grace Miscellaneous Math 15 2005-06-03 18:12
prime test teotic_hk Hardware 10 2004-01-01 19:06

All times are UTC. The time now is 20:26.

Wed Sep 30 20:26:29 UTC 2020 up 20 days, 17:37, 0 users, load averages: 1.97, 2.05, 2.05

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.