Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!noao!arizona!kwalker
From: kwalker@arizona.edu (Kenneth Walker)
Newsgroups: comp.lang.pascal,sci.crypt
Subject: Re: Implimenting this system...
Message-ID: <2980@megaron.arizona.edu>
Date: Tue, 24-Nov-87 10:45:57 EST
Article-I.D.: megaron.2980
Posted: Tue Nov 24 10:45:57 1987
Date-Received: Fri, 27-Nov-87 22:03:43 EST
References: <291@caus-dp.UUCP>
Organization: U of Arizona CS Dept, Tucson
Lines: 15
Keywords: Public Key systems
Summary: exponentiation modulo K
Xref: mnetor comp.lang.pascal:537 sci.crypt:731

In article <291@caus-dp.UUCP>, marcos@caus-dp.UUCP (Marcos R. Della) writes:
> My problem lies in
> the section that says T = (C ^ D) MOD K. The problem I face is that D is
> a large number and anything taken to a large number is rediculous in size.
> 

Just as multiplication can be implemented by shifting and adding,
exponentiation can be implemented by squaring and multiplying (see
Knuth, "The Art of Computer Programing" vol 2). The fact that

   (a * b) mod K = ((a mod K) * (b mod K)) mod K

lets you reduce your result modulo K after every squaring and every
multiplication without affecting the end result. If you do this,
the intermediate results will always be less than K ^ 2.