Re: RSA and PowerMod-Function
- To: mathgroup at smc.vnet.net
- Subject: [mg5513] Re: RSA and PowerMod-Function
- From: danl (Daniel Lichtblau)
- Date: Sat, 14 Dec 1996 19:26:10 -0500
- Organization: Wolfram Research, Inc.
- Sender: owner-wri-mathgroup at wolfram.com
In article <58lq09$7jo at dragonfly.wolfram.com> Quast Christian <94104039 at fhs-hagenberg.ac.at> writes: > > (1) > Perhaps you know how the standardfunction "PowerMod[a,b,n]" is > implemented. > (2) > Does a RSA-Algorithm implementation exist.(If possible even as > as C or C++ code) > If it exists ,please mail it to me. > > Thanks > Quast Christian > (1) It works by the standard power-tree method. Set result = a. Write b as a binary number. Iterate over the bits, squaring result each time, reducing mod n, and then multiplying by a if the bit is one and reducing mod n. (2) One implementation can be found on MathSource, item 0204-130, entitled RSA public-key encryption. There may be others, I am not sure. Daniel Lichtblau Wolfram research danl at wolfram.com