Hi Cliff,
I don't understand how to go from xyz back to xy coordinates.
At any rate, here is the affine (python) implementation. (I posted invmod
earlier):
Pointadd =: 1 : 0 NB. n is curve p a b
:
p =. {. m NB.'p a b' =. n
if. y -: p,0 do. x return. end.
if. x -: p,0 do. y return. end.
if. x -: y do. m Pointdouble y return. end.
'xx xy' =. x
'yx yy' =. y
if. (xx = yy) *. 0=p|xy+yy do. p,0 return. end.
l =. p | (p invmod yx - xx ) * yy - xy
(p| (l*xx -x3 ) - xy ) ,~ x3=. p | yx -~ xx -~ l * l
)
Pointdouble =: 4 : 0
'p a'=. 2{. x
if. y -: p,0 do. y return. end.
'xx xy' =. y
l =. p | (p invmod xy * 2 ) * a + 3 * *: xx
(p| (l*xx -x3 ) - xy ) ,~ x3=. p | (+: xx) -~ l * l
)
Pointmul =: 1 : 0 NB. sum of binary mask of repeated squares
:
m Pointadd/^:(1<#) |. bin # |. m Pointdouble^:(i. # bin =. 2 #. inv x) y
)
It passes the python tests, but it worries me that addition is not commutative.
I also don't know how to code the point at infinity (I put 0,p but that is
never reached).
3 10 (23 Pointadd) 9 7
17 20
(23 1 Pointadd) each /\ 18 # <3 10
┌────┬────┬────┬────┬────┬────┬────┬─────┬───┬─────┬───┬─────┬────┬─────┬────┬─────┬────┬────┐
│3 10│7 12│19 5│17 3│9 16│12 4│11 3│13 16│0 1│20 13│6 3│22 19│16 2│12 15│12
8│16 21│22 4│6 20│
└────┴────┴────┴────┴────┴────┴────┴─────┴───┴─────┴───┴─────┴────┴─────┴────┴─────┴────┴────┘
,. (2+ i.16) (23 1 Pointmul)"0 1 ] 3 10
7 12
19 5
17 3
9 16
12 4
11 3
13 16
0 1
6 4
18 20
16 20
5 15
13 21
2 21
5 19
18 3
These lists diverge after the item 0 1 is reached, which is the origin and a
good candidate for infinity? I don't seem to understand what order is.
----- Original Message -----
From: Cliff Reiter <reit...@lafayette.edu>
To: programm...@jsoftware.com
Cc:
Sent: Wednesday, January 29, 2014 3:32:21 PM
Subject: Re: [Jprogramming] math requests
Some elliptic curve stuff; I think there is a +1 error that Roger Hui
noticed in the factorization method.
http://archive.vector.org.uk/art10007270
http://archive.vector.org.uk/art10007280
Best, Cliff
On 1/29/2014 11:35 AM, Pascal Jasmin wrote:
>
> With all of the mathematicians on this list, these functions have likely been
> implemented before in J.
>
> elyptic curve point add, multiplication and double
> a python reference implementation:
> https://github.com/warner/python-ecdsa/blob/master/ecdsa/ellipticcurve.py
>
> the functions are: __add__ __mul__ and double
>
> if I may suggest J explicit signatures for the first 2 functions as:
>
> F =: 4 : 0
> 'yx yy yo' =. y
> 'xx xy xo' =. x
> )
>
> Some other methods than the python reference could be considered here:
>
> http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
>
>
> also appreciated if you have in implementation of inverse_mod
> for reference function of same nate at:
> https://github.com/warner/python-ecdsa/blob/master/ecdsa/numbertheory.py
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
--
Clifford A. Reiter
Lafayette College, Easton, PA 18042
http://webbox.lafayette.edu/~reiterc/
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
