Print Page - The shortest elliptic curve library!

Title: The shortest elliptic curve library!
Post by: grondilu on June 08, 2012, 12:35:25 PM

I wrote this dc library for elliptic curve arithmetics on secp256k1:

Code:

I16iFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2Fsp
7sb0sa483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798lp*+sG
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141soilpsm
[[_1*lm1-*lm%q]Std0>tlm%Lts#]s%[_1*l%x]s_[+l%x]s+[*l%x]s*[-l%x]s-[Smdd
l%x-lm/rl%xLms#]s~[l%xsclmsd1su0sv0sr1st[q]SQ[lc0=Qldlcl~xlcsdscsqlrlq
lu*-ltlqlv*-lulvstsrsvsulXx]dSXxLXs#LQs#lrl%x]sI[lpSm[+q]S0d0=0lpl~xsy
dsxd*3*lal+x2ly*lIx*l%xdsld*2lx*l-xdlxrl-xlll*xlyl-xrlp*+Lms#L0s#]sD[lp
Sm[+q]S0[2;AlDxq]Sdd0=0rd0=0d2:Alp~1:A0:Ad2:Blp~1:B0:B2;A2;B=d[0q]Sx2;A
0;B1;Bl_xrlm*+=x0;A0;Bl-xlIxdsi1;A1;Bl-xl*xdsld*0;Al-x0;Bl-xd0;Arl-xll
l*x1;Al-xrlp*+L0s#Lds#Lxs#Lms#]sA[rs.0r[rl.lAxr]SP[q]sQ[d0!<Qd2%1=P2/l.
lDxs.lLx]dSLxs#LPs#LQs#]sM

It does addition and multiplication of any point.

Examples:

Doubling the subgroup generator (G):

Code:

$ dc "$THE_ABOVE_CODE  lG lDx lm~f"

Multiplying G by a large number stored in shell variable n:

Code:

$ dc "$THE_ABOVE_CODE $n lG lMx lm~f"

An so on (the macro for addition is in register 'A').

Title: Re: The shortest elliptic curve library!
Post by: grondilu on June 12, 2012, 12:00:20 PM

A bit shorter, and with better alignment (64 characters):

Code:

I16i7sb0sa[[_1*lm1-*lm%q]Std0>tlm%Lts#]s%[Smddl%x-lm/rl%xLms#]s~
483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
2 100^d14551231950B75FC4402DA1732FC9BEBF-so1000003D1-ddspsm*+sGi
[_1*l%x]s_[+l%x]s+[*l%x]s*[-l%x]s-[l%xsclmsd1su0sv0sr1st[q]SQ[lc
0=Qldlcl~xlcsdscsqlrlqlu*-ltlqlv*-lulvstsrsvsulXx]dSXxLXs#LQs#lr
l%x]sI[lpSm[+q]S0d0=0lpl~xsydsxd*3*lal+x2ly*lIx*l%xdsld*2lx*l-xd
lxrl-xlll*xlyl-xrlp*+Lms#L0s#]sD[lpSm[+q]S0[2;AlDxq]Sdd0=0rd0=0d
2:Alp~1:A0:Ad2:Blp~1:B0:B2;A2;B=d[0q]Sx2;A0;B1;Bl_xrlm*+=x0;A0;B
l-xlIxdsi1;A1;Bl-xl*xdsld*0;Al-x0;Bl-xd0;Arl-xlll*x1;Al-xrlp*+L0
s#Lds#Lxs#Lms#]sA[rs.0r[rl.lAxr]SP[q]sQ[d0!<Qd2%1=P2/l.lDxs.lLx]
dSLxs#LPs#LQs#]sM

Title: Re: The shortest elliptic curve library!
Post by: Gavin Andresen on June 12, 2012, 12:48:43 PM

You're a crazy-man. Crazy in a good way... ever do any APL programming?

Title: Re: The shortest elliptic curve library!
Post by: grondilu on June 12, 2012, 01:00:24 PM

Quote from: Gavin Andresen on June 12, 2012, 12:48:43 PM

You're a crazy-man. Crazy in a good way...ever do any APL programming?

:D
No, but I'll check it out :)

Title: Re: The shortest elliptic curve library!
Post by: ribuck on June 12, 2012, 01:54:37 PM

Here's my attempt:

elliptic-curve-in-dc-0.2.8 (http://www.midnitetease.com/serendipity/uploads/AlizeeASCIIAnimated.gif)

*original source is here (http://www.midnitetease.com/serendipity/index.php?/archives/329-I-dont-like-Mondays....html)

Title: Re: The shortest elliptic curve library!
Post by: piotr_n on June 15, 2012, 05:26:35 PM

it's amazing! :)

Title: Re: The shortest elliptic curve library!
Post by: deepceleron on June 16, 2012, 04:00:43 AM

Next up: offline Bitcoin transaction generator written in AWK...

Title: Re: The shortest elliptic curve library!
Post by: Boussac on June 18, 2012, 05:13:06 PM

Quote from: ribuck on June 12, 2012, 01:54:37 PM

I like those curves too :D but Grondilu is the grand master

Title: Re: The shortest elliptic curve library!
Post by: 2112 on June 18, 2012, 10:43:40 PM

Quote from: znort987 on June 18, 2012, 05:42:02 PM

Quote from: Gavin Andresen on June 12, 2012, 12:48:43 PM

You're a crazy-man. Crazy in a good way... ever do any APL programming?

Aaah, APL. The write-only programming language.

Speaking of APL: someone had alredy posted an EC math library in the J programming language, the descendant of APL.

Here's the link:

https://bitcointalk.org/index.php?topic=35518.msg439736#msg439736

It may not be shorter, but it is clearly on par with dc.

Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: grondilu on June 08, 2012, 12:35:25 PM