45 lines
1.2 KiB
HTML
45 lines
1.2 KiB
HTML
|
|
||
|
|
<html>
|
||
|
|
|
||
|
|
<body BGCOLOR="#00E0E0" link="#001fC0" vlink="#000080" text="#00000f">
|
||
|
|
|
||
|
|
|
||
|
|
<title> Algorithm used to find 'd' </title>
|
||
|
|
|
||
|
|
<h1> Algorithm used to find 'd' </h1>
|
||
|
|
|
||
|
|
The variable 'd' must obey the equation
|
||
|
|
<center> <b> d.e % phi = 1 </b> </center>
|
||
|
|
This can be re-written as :
|
||
|
|
|
||
|
|
<center> <b> d.e = 1 + k.phi </b> </center>
|
||
|
|
<p>
|
||
|
|
And further
|
||
|
|
<center> <b> d = (1+k.phi)/e </b> </center>
|
||
|
|
<p>
|
||
|
|
Iterating though with values for k, a correct value
|
||
|
|
for d is found when a whole number result for d (no fractional part)
|
||
|
|
is found.
|
||
|
|
<p>
|
||
|
|
The algorithm used is to first test the user entered value
|
||
|
|
in the form. If this satisfies the equation, it is the d value used.
|
||
|
|
If it does not, it is used as the seed value for 'k'.
|
||
|
|
If the 'd' value is left blank in the form, the algorithm
|
||
|
|
will iterate using k==1 as its start value.
|
||
|
|
<p>
|
||
|
|
Note that if the value 'e' is not co-prime to phi,
|
||
|
|
this script may never find a valid value for 'd'.
|
||
|
|
A limit of 10,000 iterations has been placed on this for the time being.
|
||
|
|
It has been left this way to show the importance of these
|
||
|
|
numbers being co-prime, for the RSA system.
|
||
|
|
<br>
|
||
|
|
<br>
|
||
|
|
<br>
|
||
|
|
<center>
|
||
|
|
<a href="javascript:history.back();">
|
||
|
|
<img src=back.png align=center border=0> </a>
|
||
|
|
|
||
|
|
|
||
|
|
</body>
|
||
|
|
</html>
|