(a+bi)^p, prime test in C

[bhelmes]

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

[Batalov]

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

Maybe this will help - http://bfy.tw/LEFG

[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.

[science_man_88]

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.

https://www.mersenneforum.org/showthread.php?t=21799

[Batalov]

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?

[bhelmes]

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

[paulunderwood]

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.

[Batalov]

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.

[bhelmes]

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

[paulunderwood]

Serge gave you a clue with "=?=" above. You can just do 1 selfridge tests as the result of the binomial expansion over p.

[bhelmes]

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