(************************************************************
   scale_point.ml	Created      : Fri Jul 26 14:55:34 2002
  			Last modified: Fri Jul 26 17:46:37 2002
  Compile: ocamlopt.opt scale_point.ml -o scale_point #
************************************************************)

exception Error
type point = PZero | Point of (int * int)

let n = 11
let normalize v = 
  let nv = v mod n in
  nv + (if nv < 0 then n else 0)

let inverse_table = Array.make n (-1)

let make_inverse_table () =
  let rec sub1 i =
    let rec sub2 j =
      if ((i*j) mod n) = 1 then
      Array.set inverse_table i j
      else
	sub2 (j+1)
    in
    if i = n then ()
    else 
      begin
	sub2 1;
	sub1 (i+1)
      end
  in
  sub1 1
	
(*
 * ¼°
 *  Setting y^2 = x^3 + a*x^2 + b*x + c (Âʱ߶ÊÀþ)
 *
 *  lambda =  (y2 - y1)/(x2 - x1) (if P <> Q)
 *            (3x1^2+a)/(2*y2)    (if P = Q but y1 <> 0)
 *
 * x3 = lambda^2 - x2 -x2
 * y3 = lambda(x1 - x3) - y1
 *)

let f_lambda (x1,y1) (x2,y2) =
  if x1 = x2 then
    if y1 <> y2 || y1 = 0 then
      raise Error
    else
      let inv = Array.get inverse_table (normalize (2*y1)) in
      normalize ((3*x1*x1 + 1)*inv) 
  else
    let inv = Array.get inverse_table (normalize (x2 - x1)) in
    normalize ((y2 - y1) * inv)

let add_point p1 p2 =
  match (p1,p2) with
    (PZero,_) -> p2
  | (_,PZero) -> p1
  | ((Point((x1,y1) as p1)),(Point((x2,y2) as p2))) ->
      if x1 = x2 && y1 <> y2 then
	PZero
      else
	let lambda = f_lambda p1 p2 in
	let x3 = normalize ((lambda * lambda) - x1 - x2) in
	let y3 = normalize (lambda*(x1-x3) - y1) in
	Point(x3,y3)
let _ =
  begin
    make_inverse_table ();
    let init_point = Point(8,8) in
    let current_point = ref init_point in
    for i = 0 to 13 do
      begin
	(match !current_point with
	  PZero -> 
	    Printf.printf "Zero point\n"
	| Point(x,y) ->
	    Printf.printf "(%d,%d)\n" x y);
	current_point := add_point !current_point init_point
      end
    done
  end