10
$\begingroup$

Can you provide a proof or a counterexample for the claim given below?

Inspired by an alternative definition of the Frobenius primality test which is given in this paper I have formulated the following claim:

Let $n$ be an odd natural number that is not a perfect square and let $c$ be the smallest odd prime number such that $\left(\frac{c}{n}\right)=-1$ , where $\left(\frac{}{}\right)$ denotes a Jacobi symbol . Let $T_m(x)$ be the mth Chebyshev polynomial of the first kind , then $n$ is prime iff $T_n\left(1+\sqrt{c}\right) \equiv 1- \sqrt{c} \pmod{n}$ .

The test runs in polynomial time , you can try it here. I have verified this claim for $n$ up to $10^{10}$ .

The Android app that implements this test can be found on Google Play.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ But $\left(\frac cn\right)$ is $-1$ means that $c$ is not a square $\mod n$, then what does $1-\sqrt c\ (\mathrm{mod}\ n)$ mean? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 28, 2020 at 5:01
  • $\begingroup$ @მამუკაჯიბლაძე Please see Definition 1.1. in the linked paper. $\endgroup$
    – Pedja
    Commented Aug 28, 2020 at 5:26
  • $\begingroup$ I see, thanks. Still I am not sure how to make this rigorous. Is it equality in $\mathbb Z/n\mathbb Z[t]/(t^2-c)$ or something? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 28, 2020 at 5:30
  • 1
    $\begingroup$ @მამუკაჯიბლაძე You are right. $\endgroup$
    – Pedja
    Commented Aug 28, 2020 at 5:55
  • 2
    $\begingroup$ "only if" is certainly true, following from the congruence $T_p(x) \equiv x^p \mod p$ for $p$ an odd prime. For "if" I have no clue, but in the most naive possible random model ( $T_n(1+\sqrt{c} )$ is a random element in $\mathbb Z[\sqrt{c}]/n$ for $n$ composite) it has a probability $1/n^2$ of failure for each $n$, hence based on your data we expect it is true for all $n$. $\endgroup$
    – Will Sawin
    Commented Apr 2, 2021 at 22:14

0

Reset to default

You must log in to answer this question.