[Date Index] [Thread Index] [Author Index]

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