7
$\begingroup$

Inspired by Theorem 5 in this paper I have created the following algorithm:

Let us define polynomials $P_n^{(b)}(x)$ as follows :

$$P_n^{(b)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+b}\right)^n+\left(x+\sqrt{x^2+b}\right)^n\right)$$

Test in pseudocode :

Inputs: $n$ : a value to test for primality , $n>3$ ; $k$: a parameter that determines the number of times to test for primality

Output: composite if $n$ is composite, otherwise probably prime

Repeat $k$ times :

$\phantom{5}$ Pick $b$ randomly in the range $[-100,100]$

$\phantom{5}$ Pick $a$ randomly in the range $[2 , n − 2]$

$\phantom{5}$ If $P_n^{(b)}(a) \not\equiv a \pmod n$ , then return composite

If composite is never returned: return probably prime

You can run this test here.

Unlike in Fermat primality test Carmichael numbers do not always pass this test. As a matter a fact, I don't know if any of them passes this test.

Question:

What is the probability of an arbitrary composite number passing this test? Is it possible to estimate its value?

EDIT

The Android app that implements this test with $k=3$ can be found on Google Play.

Python script that implements this test can be found here.

$\endgroup$
4
  • $\begingroup$ can you be more precise about your question? are you choosing a composite number randomly? are you asking about the probability of a specific composite number passing the test? $\endgroup$ Commented Nov 17, 2019 at 11:06
  • $\begingroup$ @mathworker21 I am asking about the probability of arbitrary composite number passing the test. I wish to know if it is possible to estimate that probability. $\endgroup$
    – Pedja
    Commented Nov 17, 2019 at 11:24
  • $\begingroup$ The paper only covered the case $b=-1$. Is there any reason to pick a random $b$? $\endgroup$
    – Szeto
    Commented Nov 19, 2019 at 12:21
  • $\begingroup$ @Szeto Yes there is.In my opinion it enlarge chances of getting correct result. $\endgroup$
    – Pedja
    Commented Nov 19, 2019 at 12:50

1 Answer 1

3
+100
$\begingroup$

This isn't a full solution, but I attempted to analyze the problem by brute force by estimating the number of values of $a$ and $b$ which verify $n$ is composite. One lesson I can find from this: increasing the span of $b$ seems to do little to change this proportion, at least for low values of $n$. Graph of proportion of false positives for primes between 10 and 300 Graph of proportion of false positives for primes between ~200 and 300 This graph seems to vary quite dramatically. For any $n=2^p$, there are no false positives; on the other extreme, for $n=105$ and $n=231$ I would note that there are an abnormally high proportion of false positives (approximately 17% and 15% respectively for $b\in\{-100,\ldots,100\}$). These numbers specifically tell me little (perhaps another will recognize some importance in them), but the existence of such variance in false positives suggests to me that the probability you wish to estimate varies in more than just the magnitude of $n$.

One very crude way of estimating the likelihood of falsely identifying a composite as prime would be to consider the average of this proportion; under this, we find that this average runs about 0.013 for $n$ up to 300; and shrinks slowly from there to about 0.009 for $n$ between 800 and 1000; if we may safely assume this trend continues, then I would expect the probability of a false positive to be less than $0.009^k$ for large values of $n$, as a very generous upper bound.

My apologies for the crude approach to this problem; I hope that despite this, it proves to yield some insight towards a more complete solution.

$\endgroup$
2
  • 1
    $\begingroup$ Could you please tell me which plotting tool did you use? $\endgroup$
    – Pedja
    Commented Nov 24, 2019 at 7:38
  • $\begingroup$ These plots were rendered using GNU/Octave; I copy-and-pasted the output from the modified Sage code over into Octave and plotted it with the standard "plot" command; I think that uses gnuplot for its graphing capabilities. $\endgroup$
    – Kite
    Commented Nov 25, 2019 at 14:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .