Factoring Fibonacci numbers

I just wrote a C program based off this note that can decide whether the Fibonacci number F_p is prime for a prime index p. (Recall that F_n is composite when n>4 is composite.) I had written a MATLAB code some years back and since I can’t access MATLAB on my current computer I decided to rewrite it in C. The program can compute the smallest prime factor of F_p for all primes p\le 93 on a 64-bit system.

EDIT: I’ve improved my program slightly so that now it works for p\le 130. (Note: F_{130}=659,034,621,587,630,041,982,498,215.) The new code looks somewhat ugly so I won’t post it here.

#include <stdio.h>

int isprime(unsigned long long n) {
    int i, ans=1;
    for (i=2; i*i<=n; i++) {
        if(n%i==0){
            ans=0;
            break;
        }
    }
    return ans;
}

int main() {
    int p;
    printf("Enter an odd prime number: ");
    scanf("%d", &p);
    
    unsigned long long prev=1, cur=1, next, ind=2;
    while (ind<p) {
        next=prev+cur;
        prev=cur;
        cur=next;
        ind++;
    }
    
    unsigned long long Fp, P, Q;
    Fp=cur;
    P=4*p+1;
    Q=2*p-1;
    while (Q*Q<=Fp) {
        if (isprime(Q)==1 && ((Q%10)-3)*((Q%10)-7)==0 && Fp%Q==0){
            printf("The smallest prime factor of Fibonacci(%d)=%llu is %llu.", p, Fp, Q);
            return 0;
        }
        else if (isprime(P)==1 && ((P%10)-1)*((P%10)-9)==0 && Fp%P==0){
            printf("The smallest prime factor of Fibonacci(%d)=%llu is %llu.", p, Fp, P);
            return 0;
        }
        P=P+4*p;
        Q=Q+4*p;
    }
    if (Q*Q>Fp) printf("Fibonacci(%d)=%llu is prime.", p, Fp);
    return 0;
}
Advertisements

2 Comments

Filed under Number theory

2 responses to “Factoring Fibonacci numbers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s