Return to Answer

Decided to make a cw answer with an illustration of time growth.

I've tried on Mathematica this:

isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, False, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0
  ]
 ]

where

smallestr[n_] := Module[{r},
  If[EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]
  ];
  r
 ]

I've run it on $n$ up to about 31000 (all answers are correct); here is the graph of time needed as a function of $n$.

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

On the other hand a rough upper bound on growth can be deduced from the fact that $\log(\text{time}(n))/(n\log(n))$ seems to go down:

Some additional remarks.

(0)

Datapoints are only for those $n$ which have positive value of smallestr, i. e. such that the corresponding $r$ is smaller than any nontrivial divisor of $n$. Understandably, for other $n$ calculation is qualitatively quicker.

(1)

Finding $r$ is very efficient: $$ \begin{array}{c|c} r&\text{smallest $n$ that requires this $r$}\\ \hline 11&29\\ 13&419\\ 19&1429\\ 23&315589\\ 29&734161\\ 31&1456729 \end{array} $$

(2)

Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.

(2')

Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To also prove that it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Seemingly if $a_j$ is not divisible by $n$ then $j$ is not coprime to $n$; maybe this can help.

Decided to make a cw answer with an illustration of time growth.

I've tried on Mathematica this:

isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, n == 2, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0
  ]
 ]

where

smallestr[n_] := Module[{r},
  If[n==1 \[Or] EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]
  ];
  r
 ]

I've run it on $n$ up to about 31000 (all answers are correct); here is the graph of time needed as a function of $n$.

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

On the other hand a rough upper bound on growth can be deduced from the fact that $\log(\text{time}(n))/(n\log(n))$ seems to go down:

Some additional remarks.

(0)

Datapoints are only for those $n$ which have positive value of smallestr, i. e. such that the corresponding $r$ is smaller than any nontrivial divisor of $n$. Understandably, for other $n$ calculation is qualitatively quicker.

(1)

Finding $r$ is very efficient: $$ \begin{array}{c|c} r&\text{smallest $n$ that requires this $r$}\\ \hline 11&29\\ 13&419\\ 19&1429\\ 23&315589\\ 29&734161\\ 31&1456729 \end{array} $$

(2)

Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.

(2')

Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To also prove that it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Seemingly if $a_j$ is not divisible by $n$ then $j$ is not coprime to $n$; maybe this can help.

Decided to make a cw answer with an illustration of time growth.

I've tried on Mathematica this:

isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, False, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0
  ]
 ]

where

smallestr[n_] := Module[{r},
  If[EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]
  ];
  r
 ]

I've run it on $n$ up to about 31000 (all answers are correct); here is the graph of time needed as a function of $n$.

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

On the other hand a rough upper bound on growth can be deduced from the fact that $\log(\text{time}(n))/(n\log(n))$ seems to go down:

Some additional remarks.

(0)

Datapoints are only for those $n$ which have positive value of smallestr, i. e. such that the corresponding $r$ is smaller than any nontrivial divisor of $n$. Understandably, for other $n$ calculation is qualitatively quicker.

(1)

Finding $r$ is very efficient: $$ \begin{array}{c|c} r&\text{smallest $n$ that requires this $r$}\\ \hline 11&29\\ 13&419\\ 19&1429\\ 23&315589\\ 29&734161\\ 31&1456729 \end{array} $$

(2)

Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.

(2')

Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To also prove that it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Experiments show that for composite $n$, while only few of $a_j$ are not divisible by $n$ (seemingly it is necessary for this that $j$ is not coprime to $n$), actually none of the $s_j$ are divisible by $n$.

Decided to make a cw answer with an illustration of time growth.

I've tried on Mathematica this:

isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, False, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0
  ]
 ]

where

smallestr[n_] := Module[{r},
  If[EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]
  ];
  r
 ]

I've run it on $n$ up to about 31000 (all answers are correct); here is the graph of time needed as a function of $n$.

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

On the other hand a rough upper bound on growth can be deduced from the fact that $\log(\text{time}(n))/(n\log(n))$ seems to go down:

Some additional remarks.

(0)

Datapoints are only for those $n$ which have positive value of smallestr, i. e. such that the corresponding $r$ is smaller than any nontrivial divisor of $n$. Understandably, for other $n$ calculation is qualitatively quicker.

(1)

Finding $r$ is very efficient: $$ \begin{array}{c|c} r&\text{smallest $n$ that requires this $r$}\\ \hline 11&29\\ 13&419\\ 19&1429\\ 23&315589\\ 29&734161\\ 31&1456729 \end{array} $$

(2)

Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.

(2')

Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To also prove that it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Seemingly if $a_j$ is not divisible by $n$ then $j$ is not coprime to $n$; maybe this can help.

Decided to make a cw answer with an illustration of time growth.

I've tried on Mathematica this:

isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, False, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0
  ]
 ]

where

smallestr[n_] := Module[{r},
  If[EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]
  ];
  r
 ]

I've run it on $n$ up to 15000 (all answers are correct); here is the graph of time needed as a function of $n$.

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

Some additional remarks.

(1) Finding $r$ is very efficient: $$ \begin{array}{c|c} r&\text{smallest $n$ that requires this $r$}\\ \hline 11&29\\ 13&419\\ 19&1429\\ 23&315589\\ 29&734161\\ 31&1456729 \end{array} $$

(2)

Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.

(2')

Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To prove it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Experiments show that for composite $n$, while only few of $a_j$ are not divisible by $n$ (seemingly it is necessary for this that $j$ is not coprime to $n$), actually none of the $s_j$ are divisible by $n$.

Decided to make a cw answer with an illustration of time growth.

I've tried on Mathematica this:

isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, False, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0
  ]
 ]

where

smallestr[n_] := Module[{r},
  If[EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]
  ];
  r
 ]

I've run it on $n$ up to about 31000 (all answers are correct); here is the graph of time needed as a function of $n$.

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

On the other hand a rough upper bound on growth can be deduced from the fact that $\log(\text{time}(n))/(n\log(n))$ seems to go down:

Some additional remarks.

(0)

Datapoints are only for those $n$ which have positive value of smallestr, i. e. such that the corresponding $r$ is smaller than any nontrivial divisor of $n$. Understandably, for other $n$ calculation is qualitatively quicker.

(1)

Finding $r$ is very efficient: $$ \begin{array}{c|c} r&\text{smallest $n$ that requires this $r$}\\ \hline 11&29\\ 13&419\\ 19&1429\\ 23&315589\\ 29&734161\\ 31&1456729 \end{array} $$

(2)

Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.

(2')

Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To also prove that it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Experiments show that for composite $n$, while only few of $a_j$ are not divisible by $n$ (seemingly it is necessary for this that $j$ is not coprime to $n$), actually none of the $s_j$ are divisible by $n$.