## 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