Browse Groups

• ## Re: Unified test for Sophie Germain primes

(5)
• NextPrevious
• ... It s not well known because it s quite unnecessary. The foolproof unified Sophie test that works in *all* cases is much simpler. If p is prime, then q =
Message 1 of 5 , Jan 20, 2010
View Source
"j_chrtn" <j_chrtn@...> wrote:

> Do you know if this test is something well known?

It's not well known because it's quite unnecessary.
The foolproof "unified Sophie" test that works in
*all* cases is much simpler.

If p is prime, then q = 2*p+1 is prime iff 4^p = 1 mod q.

Proof: Simply use base 2 in Pocklington's theorem and
observe that 2^2-1 is coprime to 2*p+1 for every prime p.

Note that this test detects *every* Sophie pair,
including [2,5] and [3,7]. Here is a sanity check:

Pock(p)=Mod(4,2*p+1)^p==1;
forprime(p=2,10^6,if(Pock(p)!=isprime(2*p+1),print(fail)));
\\ The rest is silence, signifying consent

Entia non sunt multiplicanda praeter necessitatem :-)
http://en.wikisource.org/wiki/The_Myth_of_Occam's_Razor

David [second attempt at a reply; apologies if it appears twice]
• ... Unnecessary but at least correct. ... This is closed to Henri Lifchitz s test 3^p = 1 (mod q) but your s also handles p=2 and p=3. ... There Is More Than
Message 1 of 5 , Jan 20, 2010
View Source
>
>
> It's not well known because it's quite unnecessary.
>
Unnecessary but at least correct.

>
> If p is prime, then q = 2*p+1 is prime iff 4^p = 1 mod q.
>
This is closed to Henri Lifchitz's test 3^p = 1 (mod q) but your's also handles p=2 and p=3.

>
> Entia non sunt multiplicanda praeter necessitatem :-)
>

"There Is More Than One Way To Do It."
http://en.wikipedia.org/wiki/There's_more_than_one_way_to_do_it

However, some ways are more efficient than others ;-)

Regards,
J-L
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.