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 개의 소수가 오르고 있다.