Jacobi symbol

Embedding plaintext on Elliptic Curve is no simple. The problems to solve are how to represent a block of plaintext with the form of point on elliptic curve and recover it quickly. Not any block of plaintext can be embedded to elliptic curve because about half of x has no y correspondingly.

The common method to resolve this is by determining the quadratic residue using Jacobi symbol. If Jacobi(a) = 1, a is a quadratic residue, and if Jacobi(a) = -1, c is not a quadratic residue so the corresponding plaintext can’t be embeded to elliptic curve.

The following is the code for calculating Jacobi symbol [thx God I took the course taught by Prof. Edy Tri Baskoro, so I’m familiar enough with this “common” mathematical method, hi hi hi]:

/********************************************
 *  Program for calculating Jacobi symbol   *
 *                                          *
 *  CG - August 2008                        *
 ********************************************/

#include <iostream>

using namespace std;

int jacobi(int, int);

int main()
{
    int a, n;

    cout << "a? ";
    cin >> a;
    cout << "n? ";
    cin >> n;

    cout << "\nThe Jacobi symbol is " << jacobi(a,n) << endl;

    return 0;
}

/* Precondition: a, n >= 0; n is odd */
int jacobi(int a, int n) {
    int ans;

    if (a == 0)
        ans = (n == 1) ? 1 : 0;
    else if (a == 2) {
        switch ( n % 8 ) {
            case 1:
            case 7:
                    ans = 1;
                    break;
            case 3:
            case 5:
                    ans = -1;
                    break;
        }
    }
    else if ( a >= n )
        ans = jacobi(a%n, n);
    else if ( a % 2 == 0 )
        ans = jacobi(2,n)*jacobi(a/2, n);
    else
        ans = ( a % 4 == 3 && n % 4 == 3 ) ? -jacobi(n,a) : jacobi(n,a);
    return ans;
}

I test the code using example from this book, page 132. a = 6278 and n = 9975. The result is correct : -1

Advertisements