{"id":543,"date":"2013-10-09T02:14:30","date_gmt":"2013-10-09T06:14:30","guid":{"rendered":"http:\/\/www.curtisbright.com\/bln\/?p=543"},"modified":"2013-10-09T02:14:30","modified_gmt":"2013-10-09T06:14:30","slug":"the-n-1-and-n1-primality-tests","status":"publish","type":"post","link":"http:\/\/localhost\/blog\/index.php\/2013\/10\/09\/the-n-1-and-n1-primality-tests\/","title":{"rendered":"The $n-1$ and $n+1$ primality tests"},"content":{"rendered":"

Determining if a number $n$ is a prime number<\/a> or not is an important problem in computational number theory. Two simple ways of proving primality rely on the prime factorizations of $n-1$ and $n+1$. In general\u00a0finding these factorizations is probably a harder problem than testing the primality of $n$, so the methods are only applicable in special cases, but are they are interesting nonetheless.<\/p>\n

At a high level, the $n-1$ method works by showing that a subgroup of $\\newcommand{\\Z}{\\mathbb{Z}}\\Z^*_n$ is so large that $n$ must be prime. Specifically, a subgroup of order $n-1$ is demonstrated, which implies that $\\Z_n^*$ is as large as possible, namely the full set of nonzero residues $\\{1,2,\\dotsc,n-1\\}$; if even one element was missing then there would be less than $n-1$ elements in $\\Z_n^*$. But $\\Z_n^*=\\{1,2,\\dotsc,n-1\\}$ means that every positive integer strictly less than $n$ is coprime to $n$, and so $n$ is prime.<\/p>\n

To show that $\\Z_n^*$ contains a subgroup of size $n-1$, we find an element $a\\in\\Z_n^*$ whose order is $n-1$ (such an element is called a primitive root<\/a>). To do this, we show that<\/p>\n

\\[ a^{n-1} \\equiv 1 \\pmod{n} \\tag{1} \\]<\/p>\n

and<\/p>\n

\\[ a^{(n-1)\/p} \\not\\equiv 1 \\pmod{n} \\tag{2} \\]<\/p>\n

for all primes $p$ which divide $n-1$. This is enough to show that the order of $a$ is $n-1$; if the true order was $r<n-1$ then using B\u00e9zout’s identity<\/a>\u00a0one would be able to derive $a^{\\gcd(r,n-1)}\\equiv1\\pmod{n}$ and this would contradict (2) for some $p$.<\/p>\n

When $n$ is prime, there isn’t any known efficient algorithm which is guaranteed to find a primitive root $a$ satisfying (1) and (2), but in practice this isn’t a concern. In fact, there are $\\varphi(n-1)=\\Theta(n\/\\ln\\ln n)$ primitive roots (where $\\varphi$ denotes Euler’s totient function<\/a>), so if one simply tests if random $a$ satisfies (1) and (2) then one should quickly find one which works, and thereby prove that $n$ is prime. As mentioned, the real problem with applying this method in practice is finding the primes $p$ which divide $n-1$.<\/p>\n

Incidentally, when $n$ isn’t prime, this is usually easy to show since condition (1) will often fail to hold, and all primes satisfy (1)<\/a>\u00a0for all $a\\in\\Z_n^*$. However, some composite numbers<\/a>\u00a0still satisfy (1) for all $a\\in\\Z_n^*$. In such a case a more stringent form<\/a> of (1) can be used to prove compositeness, and this method can be employed in practice since it only requires the “evenness factorization” $n-1=2^r\\cdot m$ with $m$ odd, which is simple to compute.<\/p>\n

The $n+1$ method is similar to the $n-1$ method, except it works in the group $(\\Z_n[\\sqrt{d}])^*$, where $d$ satisfies $(\\frac{d}{n})=-1$, i.e., $d$ is not a quadratic residue<\/a> mod $n$. We assume that $n$ is odd (otherwise the problem is trivial), so that in practice $d$ can be found by computing the\u00a0Jacobi symbol<\/a> $(\\frac{d}{n})$ for multiple values of $d$ until one works. Note that when $n$ is prime we have $\\newcommand{\\F}{\\mathbb{F}}\\Z_n[\\sqrt{d}]\\cong\\F_{n^2}$, the finite field of size $n^2$, so there still exist primitive roots $a$ which generate $(\\Z_n[\\sqrt{d}])^*$. We’ll denote the\u00a0conjugate<\/a>\u00a0of $a$ by $\\bar{a}$, so if\u00a0$a:=b+c\\sqrt{d}$ with $b$, $c\\in\\Z_n$ then\u00a0$\\bar{a}=b-c\\sqrt{d}$.<\/p>\n

As you might expect in relation to the above, the $n+1$ method finds a subgroup of\u00a0$(\\Z_n[\\sqrt{d}])^*$ of size $n+1$ by finding an $a\\in(\\Z_n[\\sqrt{d}])^*$ which has order $n+1$. Actually, we need something a bit stronger than this; we need to show<\/p>\n

\\[ a^{n+1} \\equiv 1 \\pmod{n} \\tag{3} \\]<\/p>\n

and<\/p>\n

\\[ \\gcd((a^{(n+1)\/p}-1)(\\bar{a}^{(n+1)\/p}-1),n)=1 \\tag{4} \\]<\/p>\n

for all primes $p$ which divide $n+1$. Condition (4) not only implies that $a^{(n+1)\/p} \\not\\equiv 1 \\pmod{n}$, but also that\u00a0$a^{(n+1)\/p} \\not\\equiv 1 \\pmod{q}$ where $q$ is any prime divisor of $n$. To see that this, we show the contrapositive. Suppose that $q$ is a prime divisor of $n$ and that $q\\mid a^{(n+1)\/p}-1$.1<\/a><\/sup> It follows that $q$ also divides $(a^{(n+1)\/p}-1)(\\bar{a}^{(n+1)\/p}-1)\\in\\Z$, and thus divides the gcd in (4), so (4) fails to hold.<\/p>\n

Since condition (3) implies that\u00a0$a^{n+1}\\equiv1\\pmod{q}$ and condition (4) implies that $a^{(n+1)\/p}\\not\\equiv1\\pmod{q}$, just like before one knows that $a\\pmod{q}$ has order $n+1$. In particular, there must be at least $n+1$ elements in $(\\Z_q[\\sqrt{d}])^*$.<\/p>\n

Toward a contradiction, suppose that (3) and (4) hold and that $n$ is not prime. Let $q$ be the smallest prime divisor of $n$, so that $q^2\\leq n$. As we just saw, $a\\pmod{q}$ has order $n+1$, so we get the lower bound<\/p>\n

\\[ n+1 \\leq \\lvert(\\Z_q[\\sqrt{d}])^*\\rvert . \\]<\/p>\n

However, $\\Z_q[\\sqrt{d}]$ has $q^2$ elements, and so<\/p>\n

\\[ \\lvert(\\Z_q[\\sqrt{d}])^*\\rvert \\leq q^2-1 \\leq n-1 ,\u00a0\\]<\/p>\n

which contradicts the lower bound. Thus $n$ must in fact be prime.<\/p>\n

When $n$ is prime, an $a$ which satisfies (3) and (4) can be found by taking a primitive root of $\\F_{n^2}$ and raising it to the power $n-1$, since in this case $(a^{n-1})^{n+1}\\equiv1\\pmod{n}$ and $n$ will not divide $(a^{n-1})^{(n+1)\/p}-1$ or its conjugate. As mentioned, there isn’t a guaranteed procedure to find a primitive root, but since there are $\\varphi(n^2-1)=\\Theta(n^2\/\\ln\\ln n)$ of them, in practice it shouldn’t be too hard to find one; the sticking point is finding the factorization of $n+1$.<\/p>\n

Incidentally, the $n+1$ test is often presented using Lucas sequences<\/a> rather than $\\F_{n^2}$. But that’s a topic for another post.<\/p>\n

\n
<\/div>\n
    \n
  1. This notation\u00a0means that there is some algebraic integer $k$ such that $qk=a^{(n+1)\/p}-1$. However, it is actually only necessary to consider $k\\in\\Z\\lbrack\\sqrt{d}\\rbrack$, since we can take\u00a0$a\\in\\Z\\lbrack\\sqrt{d}\\rbrack$ and $q$ is odd. ↩<\/a><\/span><\/li>\n<\/ol>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

    Determining if a number $n$ is a prime number or not is an important problem in computational number theory. Two simple ways of proving primality rely on the prime factorizations of $n-1$ and $n+1$. In general\u00a0finding these factorizations is probably … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"_links":{"self":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/543"}],"collection":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=543"}],"version-history":[{"count":0,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/543\/revisions"}],"wp:attachment":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=543"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=543"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=543"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}