mersenneforum.org (a+bi)^p, prime test in C
 Register FAQ Search Today's Posts Mark Forums Read

 2018-12-06, 19:26 #1 bhelmes     Mar 2016 2×33×5 Posts (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
 2018-12-06, 22:14 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,127 Posts A sad day. Imagine that - to be banned from Google, too? Maybe this will help - http://bfy.tw/LEFG
 2018-12-28, 19:19 #3 bhelmes     Mar 2016 2×33×5 Posts 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.
2018-12-28, 19:28   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by bhelmes 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.

2018-12-28, 20:29   #5
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts

Quote:
 Originally Posted by bhelmes 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?

 2018-12-29, 17:57 #6 bhelmes     Mar 2016 2·33·5 Posts 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
2018-12-29, 19:23   #7
paulunderwood

Sep 2002
Database er0rr

D5616 Posts

Quote:
 Originally Posted by bhelmes 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

2018-12-29, 20:28   #8
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts

Quote:
 Originally Posted by paulunderwood 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.

2018-12-30, 17:21   #9
bhelmes

Mar 2016

2·33·5 Posts

Quote:
 Originally Posted by paulunderwood

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

 2019-01-03, 17:44 #10 paulunderwood     Sep 2002 Database er0rr 2×3×569 Posts Serge gave you a clue with "=?=" above. You can just do 1 selfridge tests as the result of the binomial expansion over p.
 2019-01-03, 23:51 #11 bhelmes     Mar 2016 2×33×5 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Carl Fischbach Miscellaneous Math 33 2009-09-11 20:49 henryzz Software 11 2008-02-12 18:30 jocelynl Math 8 2006-10-20 19:36 Robert Grace Miscellaneous Math 15 2005-06-03 18:12 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