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