» »

[php] Razširjen evklidov algoritem

[php] Razširjen evklidov algoritem

Yacked2 ::

Za računanje privatnega kjuča pri RSAju potrebujem tale lasty:
function extended_gcd(a, b)
    x := 0    lastx := 1
    y := 1    lasty := 0
    while b ≠ 0
        quotient := a div b
        (a, b) := (b, a mod b)
        (x, lastx) := (lastx - quotient*x, x)
        (y, lasty) := (lasty - quotient*y, y)       
    return (lastx, lasty)


ker pišem program v phpju, sem sestavil takole:
$p = 17; //praštevilo 1
$q = 11; //praštevilo 2
$javni = 7; //javni kjuc

$n = $p * $q; //modul
$o = ($p-1)*($q-1); //koeficient

//razsirjen evklidov algoritem
$x=0;
$y=1;
$lastx=1;
$lasty=0;

$a=$o;
$b=$javni;

while ($b != 0)
{
	$quotient =intval($a / $b);
	$temp = $a;
	$a = $b;
	$b = $temp % $b;
	$temp = $x;
	$x = $lastx - ($quotient *$x);
	$y = $lasty - ($quotient *$y);
	$lasty = $temp;
}

echo $lasty;


Pri takih podatkih bi program moral vrniti 23, a vrne 0. Nevem kje sem ga polomil, lahko kdo pregleda ? hwala
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!
  • spremenil: Mavrik ()

amacar ::

<?php
$p = 17; //praštevilo 1
$q = 11; //praštevilo 2
$javni = 7; //javni kjuc
 
$n = $p * $q; //modul
$o = ($p-1)*($q-1); //koeficient

$x = 0;
$y = 1;
$lastx = 1;
$lasty = 0;
$a = $o;
$b = $javni;
 
while($b !=0)
{
    $quotient = intval($a / $b);
    $temp = $a;
    $a = $b;
    $b = $temp % $b;
    $temp = $x;
    $x = ($lastx - $quotient * $x);
    $lastx = $temp;
    $temp = $y;
    $y = ($lasty - $quotient * $y);
    $lasty = $temp;
}
echo $lasty;
?>

Yacked2 ::

O hvala, to sem pa spregledal
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Najvecji skupni delitelj dveh ali vec stevil

Oddelek: Programiranje
51198 (826) RatedR
»

Matematika

Oddelek: Šola
313435 (2215) Math Freak
»

VB.NET evklidov algoritem razširjen

Oddelek: Programiranje
8898 (745) Yacked2
»

Grafika

Oddelek: Programiranje
201707 (1059) aaaaa93
»

[C++] Dve malo težji nalogi

Oddelek: Programiranje
162241 (1857) roli

Več podobnih tem