lucas  メルセンヌ(Mersenne)数が素数であるかどうかを判定する

int lucas(int p);

p  メルセンヌ数における素数

素数なら1、非素数（つまり、合成数）なら0、内部エラーが起きた
ときは -1。

int lucas(int p)
{
    char *l, *m;
    char *lp, *mp1, *mp2;
    int  i, j, k;
    int  ca, x;
    int  ret = 1;

    if (p <= 0) return 0;
    if (p <= 2) return 1;

    if ((l = (char *)malloc(p)) == NULL) return -1;
    if ((m = (char *)malloc(p)) == NULL) {
        free(l);
        return -1;
    }

    for (lp = l + p; lp != l; ) *--lp = 0;
    *(l+2) = 1;                                     /* L(1) = 4 */

    for (i = 2; i < p; i++) {
        for (lp = l + p, mp1 = m + p; lp != l; ) {
            *--mp1 = *--lp;
            *lp = 1;                        /* 2^p -1 mod 2^p -1 = 0 */
        }

        *(l+1) = 0;                                 /* L(i) = L(i) - 2 */
        for (mp1 = m, j = 0; j < p; j++) {
            if (*mp1++) {                           /* this bit is 1 */
                ca = 0;
                k = j;
                for (mp2 = m; mp2 != m + p; ) {     /* L(i) * L(i) */
                    x = *mp2++ + *(l+k) + ca;
                    *(l+k) = x & 1;
                    ca = x >> 1;
                    if (++k == p) k = 0;
                }
                if (ca) {
                    while (*(l+k)) {
                        *(l+k) = 0;
                        if (++k == p) k = 0;
                    }
                    *(l+k) = 1;
                }
            }
        }
    }

    x = *l;
    for (lp = l + p; lp != l; )               /* L(p-1) == all 0 or 1 ? */
        if (*--lp != x) {
            ret = 0;
            break;
        }

    free(m);
    free(l);
    return ret;
}

Lucasテストとは、ルーカス (Lucas) が1876年に発見したもので、 メルセンヌ数が素数かどうかを簡単に判定できる。

　　　$L$₀ = 4、L_i+i = (L_i² - 2) mod (2^p - 1)

で、$L$_p-1 が 0 なら $M$_p は素数、0 以外なら非素数である。

Lucas テストのおかげで、コンピュータの力による素数の発見競争は、 これからも続けられ、記録は塗り替えられていくであろう。

しかし、πの近似値は20億桁まで計算されているから、たかだか26万桁の 素数は大したことでないともいえる。

ちなみに、現在使われている最大の素数表は
　　　　Lehmer, D. H. Guide to Tables in the Theory of Numbers, 1941
で、10006721 までの、665000 個の素数がのっている。