3
$\begingroup$

This question is successor of Compositeness test for specific class of $N=k \cdot b^n-1$ .

Can you provide a proof or a counterexample to the following claim :

Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ . Let $N=k \cdot b^n-1$ such that $k>0$ , $3 \not\mid k$ , $k<2^n$ , $b>0$ , $b$ is even number, $3 \not\mid b$ and $n > 2$ . Let $S_i=P_b(S_{i-1})$ with $S_0=P_{kb/2}(P_{b/2}(4))$ , then if $S_{n-2} \equiv 0\pmod{N}$ then $N$ is a prime .

You can run this test here .

I have verified this claim for many random values of $k$ , $b$ and $n$ .

P.S.

A command line program that implements this test can be found here .

$\endgroup$
2
  • 1
    $\begingroup$ When $b=2$ this looks pretty close to the Riesel--Lucas--Lehmer test for primality of numbers of the form $k\cdot 2^n - 1$. See en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test. Note your $(4 \pm \sqrt{4^2-4})/2 = 2 \pm \sqrt{3}$. $\endgroup$
    – KConrad
    Aug 27, 2018 at 23:59
  • $\begingroup$ @KConrad Your observation is correct. I tried to generalize Riesel's theorem. $\endgroup$
    – Pedja
    Aug 28, 2018 at 4:38

1 Answer 1

1
+50
$\begingroup$

Not a full answer (but maybe need to fill computational details): If I am not mistaken, you are using the group law of a conic $C$ to iterate a point $p_0$ by multiplication by $b$. In fact, $S_{n-2}$ is the $x$ coordinate of the point $b^{n-2}(kp_0)$ in $C$ of order $4$, therefore, $S_{n-1}$ of a point of order $2$ and finally $S_n$ for the $x$ coordinate of the identity of $C$. These $x$ coordinates are $0,-1,1$. If you find such a sequence (which corresponds to the iteration of a fixed point $kp_0$ by multiplication by $b$) then it means that $C(\mathbb{Z}/N)\cong \mathbb{Z}/(N+1)\mathbb{Z}=\mathbb{Z}/kb^n\mathbb{Z}$. Therefore prime. Your restriction $k<2^n$ I think can be $k<b^n$. I did not have time to calculate $C$ but it should be something doable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.