Elliptic curve arithmetic: Difference between revisions

 

[[wp:Elliptic curve|Elliptic curve]]s   are sometimes used in   [[wp:cryptography|cryptography]]   as a way to perform   [[wp:digital signature|digital signature]]s.

In a nutshell, an elliptic curve is a bi-dimensional curve defined by the following relation between the '''x''' and '''y''' coordinates of any point on the curve:

 

 

'''a''' and '''b''' are arbitrary parameters that define the specific curve which is used.

<br>for any point '''P''' and integer '''n''', &nbsp; the point '''P + P + ... + P''' &nbsp; &nbsp; ('''n''' times).

<br><br>

 

=={{header|C}}==

#include <math.h>

 

 

return 0;

{{out}}

<pre>

a + b + d = Zero

a * 12345 = (10.759, 35.387)

</pre>

 

=={{header|D}}==

{{trans|Go}}

 

enum bCoeff = 7;

writeln("a + b + d = ", a + b + d);

writeln("a * 12345 = ", a * 12345);

{{out}}

<pre>a = (-1.817, 1.000)

=={{header|EchoLisp}}==

===Arithmetic===

(require 'struct)

(decimals 4)

(printf "%d additions a+(a+(a+...))) → %a" n e)

(printf "multiplication a x %d → %a" n (E-mul a n)))

{{out}}

<pre>

===Plotting===

;; Result at http://www.echolalie.org/echolisp/help.html#plot-xy

(define (E-plot (r 3))

(define (Ellie x y) (- (* y y) (* x x x) 7))

(plot-segment R.x R.y R.x (- R.y))

)

 

=={{header|Go}}==

{{trans|C}}

 

import (

show("a + b + d = ", add(a, add(b, d)))

show("a * 12345 = ", mul(a, 12345))

{{out}}

<pre>a = (-1.817, 1.000)

 

=={{header|Haskell}}==

import Control.Monad (guard)

 

 

 

data Elliptic = Elliptic Double Double | Zero

 

inv Zero = Zero

 

Points on elliptic curve form a monoid:

mempty = Zero

 

mkElliptic l = let x = l^2 - x1 - x2

y = l*(x1 - x) - y1

 

Examples given in other solutions:

 

 

<pre>λ> let a = ellipticX 7 1

 

1. direct monoidal solution:

 

2. efficient recursive solution:

| n == 0 = Zero

| n == 1 = p

| n < 0 = inv ((-n) `mult` p)

| even n = 2 `mult` ((n `div` 2) `mult` p)

 

<pre>λ> 12345 `mult` a

We use QuickCheck to test general properties of points on arbitrary elliptic curve.

 

do let y2 = x**3 + a*x + b

guard (y2 > 0)

return $ Elliptic x (sqrt y2)

 

associativity a b x1 x2 x3 =

in (p x1 <> p x2) <> p x3 == p x1 <> (p x2 <> p x3)

 

commutativity a b x1 x2 =

 

+++ OK, passed 100 tests.

λ> quickCheck commutativity

Follows the C contribution.

 

isZero=: 1e20 < |@{.@+.

)

 

)

 

 

task=: 3 :0

{{out}}

c + d = Zero

a + b + d = Zero

 

=={{header|Java}}==

{{trans|D}}

import java.util.Locale;

 

return String.format(Locale.US, "(%.3f,%.3f)", this.x, this.y);

}

<pre>a = (-1.817,1.000)

b = (-1.442,2.000)

a + b + d = Zero

a * 12345 = (10.759,35.387)</pre>

 

=={{header|PARI/GP}}==

The examples were borrowed from C, though the coding is built-in for GP and so not ported.

a=[-6^(1/3),1]

b=[-3^(1/3),2]

elladd(e,c,d)

elladd(e,elladd(e,a,b),d)

{{output}}

<pre>%1 = [-1.8171205928321396588912117563272605024, 1]

=={{header|Perl}}==

{{trans|C}}

{

package EC::Point;

sub new { my $class = shift; bless [ @_ ], $class }

 

package Test;

{{out}}

<pre>EC-point at x=-1.817121, y=1.000000

EC-point at x=-1.442250, y=2.000000

EC-point at x=10.375375, y=-33.524509

</pre>

 

=={{header|Phix}}==

{{Trans|C}}

{{out}}

<pre>

a + b + d = Zero

a * 12345 = (10.759, 35.387)

</pre>

 

=={{header|Python}}==

{{trans|C}}

 

class Point:

show("c + d =", c.add(d))

show("a + b + d =", a.add(b.add(d)))

{{out}}

<pre>

 

=={{header|Racket}}==

#lang racket

(define a 0) (define b 7)

[(even? n) (⊗ (⊗ p (/ n 2)) 2)]

[(odd? n) (⊕ p (⊗ p (- n 1)))]))

Test:

(define (root3 x) (* (sgn x) (expt (abs x) 1/3)))

(define (y->point y) (vector (root3 (- (* y y) b)) y))

(displayln (~a "p+(q+(-(p+q))) = 0 " (zero? (⊕ p (⊕ q (neg (⊕ p q)))))))

(displayln (~a "p*12345 " (⊗ p 12345)))

Output:

p = #(-1.8171205928321397 1)

q = #(-1.4422495703074083 2)

p+(q+(-(p+q))) = 0 #t

p*12345 #(10.758570529320806 35.387434774282106)

 

=={{header|REXX}}==

 

Also, some code was added to have the output better aligned &nbsp; (for instance, negative and positive numbers).

numeric digits 100 /*try to ensure a min. of accuracy loss*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

cbrt: procedure; parse arg x; return root(x,3)

root: procedure; parse arg x,y; if x=0 | y=1 then return x/1; d=5; return rootI()/1

func: procedure; parse arg y,k; if k=='' then k=7; return cbrt(y**2-k) y

inf: return '1e' || (digits()%2)

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

rootI: ox=x; oy=y; x=abs(x); y=abs(y); a=digits()+5; numeric form; g=rootG(); m=y-1

do until d==a; d=min(d+d,a); numeric digits d; o=0

do until o=g; o=g; g=format((m*g**y+x)/y/g**m,,d-2); end /*until o=g*/

<pre>

</pre>

 

=={{header|Sage}}==

Examples from C, using the built-in Elliptic curves library.

 

# a point (x,y) on Ellie, given y

return P

 

P = point(1)

Q = point(2)

S = P+Q

{{out}}

<pre>

P+Q-S (0.000000000000000 : 1.00000000000000 : 0.000000000000000) ## Zero

P*12345 (10.7585721817304 : 35.3874428812067 : 1.00000000000000)

</pre>

 

=={{header|Tcl}}==

{{trans|C}}

set zero {x inf y inf}

proc tcl::mathfunc::cuberoot n {

}

return $r

Demonstrating:

if {[iszero $p]} {

puts "${s}Zero"

show "c + d = " [add $c $d]

show "a + b + d = " [add $a [add $b $d]]

{{out}}

<pre>