Hello I am working on implementing a message to elliptic curve point mapping hardware circuit I have done some research and found out the koblitz mapping method: I will be using a field of binary polynomials F(2^163) the equation will be of the form of : $$ y^2 + xy = x^3 + x^2 + 1 $$
The given algorithm consists of checking the Tr "Trace of polynomial" at first and then solving the quadratic equation based on the chosen coordinate "x" that satisfied the needed trace conditions and obtain "y" the second coordinate I have given to understand that finding the trace of any polynomial C in field 163 is XORing(bit0,bit157) of the given polynomial
But after calculating the Trace and finding the x coordinates I do not understand how to solve the quadratic equation in hardware and how to implement it I have found some reading material suggesting of calculating the H(C) which is the half trace of the polynomial C but my questions are:
1.What is trace of a polynomial and how it is calculated? is it by xoring all bit together from 0 to m-1 ?
what is half trace ? and how does it relate to trace? and why is it used to solving quadratic equation isn't it a 1 -bit answer
how can I solve the given equation to obtain the y coordinate and if there are 2 Y answers which one will be chosen?
Thank you I really appreciate the help. I could not find clear reading material on this matter with a simplified and easy to read algorithm/pseudo-code
Added: I found the following algorithm but I do not know what it's name? and how are the parameters a2n and a2n+1 computed and how they vary for different fields lets say (163)
algorithm for solving the equation taken from: A Low-Power Design for an Elliptic Curve Digital Signature Chip (Rich Schroeppel, Tim Draelos, Russell Miller, Rita Gonzales, Cheryl Beaver)