[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1932.0. "Find lowest d or k for (e*d)-(k*n)=1" by RANGER::TBAKER (DOS With Honor) Wed Feb 01 1995 00:55

    Please point me to the right note if this is already entered:
    
    Given some known numbers N and E, I need to find D and/or
    K where:
    
    		(D * E) - (K * N) = 1
    
    Another way of writing this is:
    
    		(D*E) mod N = 1
    
    E may be restricted to having it's most significant bit be less than
    half the most significant bit in N.  eg N = 0x100000 E<0x1000
    
    I need to do this for *very* large N and E so a brut force method is
    impractical.
    
    Thank you,
    Tom
T.RTitleUserPersonal
Name
DateLines
1932.1AUSSIE::GARSONachtentachtig kacheltjesWed Feb 01 1995 03:053
    re .0
    
    Topics 170 and 637 seem to be related but they are for N a power of 2.
1932.2RUSURE::EDPAlways mount a scratch monkey.Wed Feb 01 1995 11:4142
    Re .0:
    
    Gee, do you suppose "e" and "d" stand for "encode" and "decode"?
    
    Modular multiplicative inverses are easily found with an extension of
    Euclid's algorithm for finding the greatest common divisor.
    
    Let a = (n, 0) and let b = (e, 1).  These are vectors of two elements,
    and the arithmetic we do with them will be element-by-element.  Thus,
    multiplying the vector (j, k) by (m, n) results in (j*m, k*n).  Also, I
    will use a[0] and a[1] to indicate the individual elements in a.
    
    Do
    	Let q = a[0] / b[0].	(Take the integer part of the quotient;
    				discard any fraction.) 
    	Let c = a - q*b.	(Multiply each element in b by q and
    				subtract them from a's elements.)
    	Let a = b.
    	Let b = c.
    while b[0] != 0.
    
    When this loop is done, a[0] will contain the greatest common divisor
    of n and e, and a[1] will contain the multiplicative inverse of e
    modulo n.  To see this, observe that for the initial vectors put into a
    and b, the following property is true:
    
    	a[0] is congruent to a[1]*e, modulo n.
    
    With some algebra, you can show that whenever this property is true for
    a and b, it is true for the c calculated in the loop, so it is true for
    all vectors the loop calculates.  So at the end, where a[0] is 1 if n
    and e are relatively prime, a[1]*e is congruent to 1.  Note that a[1]
    may be negative.
    
    You can find source code for this algorithm in the PGP kit.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.
1932.3IOSG::TEFNUT::carlinDick Carlin IOSG ReadingWed Feb 01 1995 12:3611
Like edp, my first reaction was to suggest using Euclid to simultaneously 
find the gcd and solve the problem if the gcd is 1.

But then I wondered if this was the "brute force" approach that you already 
discounted; all those divides and multiplies. If so, then have you looked at 
Knuth(Motto: there's always a quicker way)'s "Seminumerical Methods", half of 
which seems to be devoted to the performance etc of Euclid?

Dick

With apologies to Dave Barry
1932.4Euclid and Associates?THOLIN::TBAKERThe Spirit of ApathyWed Feb 01 1995 15:3120
>    Gee, do you suppose "e" and "d" stand for "encode" and "decode"?

    A lucky guess :-)

    Well, I typed in the algorithm and it worked for one set of numbers
    but for the next 3 sets, a1 came out negative.... until I added it to
    the orginal a0 and everyone was happy again.

    Thank you, edp.  May your monkey sleep peacefully forevermore.

    BTW: Does Euclid charge royalties?				:-)

    And, Dick, when I referred to brute force I meant raising n
    by one and finding some number d such that d*e > n and then
    check the remainder to see if it was 1.  If not, raise n again
    and repeat.  For large numbers that would be a *lot* of calculations.
    The algorithm edp typed in was exactly what I was looking for.

    Thank you,
    Tom