 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 39710 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 23·1,229 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 397 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

203008 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

23×1,229 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 6158 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

103216 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

231508 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

39710 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·691 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 39710 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   Thread Tools Show Printable Version Email this Page 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 09:46.

Sat May 28 09:46:23 UTC 2022 up 44 days, 7:47, 0 users, load averages: 0.62, 1.07, 1.15