View Single Post
Old 2021-06-30, 14:01   #15
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

2·2,503 Posts

After my tour de force proving that (2^p + 1)/3 automatically "passes" the Rabin-Miller test to the base 2 when p > 3 is prime (and stupidly failing to point out that I had actually proven that), it occurred to me that a simple Fermat PRP test for (2^p + 1)/3 to any base is easily refined to a Rabin-Miller test in this case since (N-1)/2 is odd, and for small bases the results are predictable using pencil-and-paper calculations. We have

N = (2^15135397+1)/3

Clearly N == -1 (mod 4). For base b = 3, 5, 7, and 11, reducing the exponent mod 6, 4, 6, and 10 respectively, we find that

3*N == 3 (mod 9) so that N == 1 (mod 3), N == 1 (mod 5), N == 1 (mod 7), and N == -1 (mod 11).

Assuming N is prime, applying the law of quadratic reciprocity tells us that

(3/N) = (-1/N)(-3/N) = (-1)(N/3) = -1

(5/N) = (N/5) = +1

(7/N) = (-1/N)(-7/N) = (-1)(N/7) = -1

(11/N) = (-1/N)(-11/N) = (-1)(N/11) = (-1)(-1) = +1, so if N is prime,

3^((N-1)/2) == -1 (mod N)

5^((N-1)/2) == +1 (mod N)

7^((N-1)/2) == -1 (mod N), and

11^((N-1)/2) == +1 (mod N).

If any of these congruences fail to hold, that would prove that N is composite. Further, if any of these residues were anything other than 1 or -1 (mod N), it would give a proper factorization of N.

I am confident that ryanp et al know all this, and checked all this.

Someone who natters that "you should run a Rabin-Miller test" without even bothering to do the above paper-and-pencil calculations (and perhaps doesn't even know how), or considering that they might be addressing their quibbling to people who know all this and have almost certainly already done the calculations, should IMO thank God for His infinite mercy in not issuing a permanent ban.
Dr Sardonicus is offline   Reply With Quote