Alle Punkte einer elliptische Kurve bestimmen -

Alle Punkte einer elliptische Kurve bestimmen

Dienstag, den 27. Juli 2010 um 19:02 Uhr

Dieses kleine Programm hilft alle Punkte einer elliptischen Kurve zu finden.

<?php
//array mit validen Punkten
$valid_points = array ();
//Parameter: Modulus:
$mod = 13;
echo"Finding valid Points on elliptic Curve: <br>";
for($x = 0; $x < $mod; $x++)
{
 for($y = 0; $y < $mod; $y++)
 {
 if(check_pair($x,$y,$mod))
 {
 $newPoint = array($x,$y);
 if(!in_array($newPoint,$valid_points)){$valid_points[] = $newPoint;}
 }
 echo"-";
 }
}
Echo" Done.<br> Found ".count($valid_points)." vaild Points<br> E = {";

for($i = 0; $i < count($valid_points); $i++)
{
 echo" ( ".$valid_points[$i][0]." ; ".$valid_points[$i][1]." ), ";
}
$ord = 1 +count($valid_points); //Ordnung der elliptische Kurve
echo" O } <br> Die Ordnung(E) beträgt: ord(E) = $ord ";

/*
Prüft ob ein Koordianten Paar die Polynomgleichung erfüllt
*/
function check_pair($x,$y,$mod)
{
 $y = ($y * $y ) % $mod;
 //Polynom der elliptischen Kurve
 $x = ( pow($x, 3) + 3 * $x + 11) % $mod;
 if($y == $x)
 {
 return true;
 }
 return false;
}
?>

Die Funktion des Programms ist recht einfach es werden alle möglichen Koordinaten geprüft. Da es sich um kryptographische ,,elliptische Kurven" handelt sind die Koordinaten durch den Modulus begränzt.

Eine Ausgab des Programms sieht so aus:

Finding valid Points on elliptic Curve:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Done.
Found 11 vaild Points
E = { ( 2 ; 5 ), ( 2 ; 8 ), ( 4 ; 3 ), ( 4 ; 10 ), ( 8 ; 1 ), ( 8 ; 12 ), ( 9 ; 0 ), ( 10 ; 1 ), ( 10 ; 12 ), ( 11 ; 6 ), ( 11 ; 7 ), O }
Die Ordnung(E) beträgt: ord(E) = 12

Das Programm gibt alle gültigen X-Y Paare aus und fügt das neutrale Element O hinzu. die Ordnung der Kurve entspricht der Anzahl an Koordinaten plus dem neutralen Element.

serious-cool

Alle Punkte einer elliptische Kurve bestimmen