On Sun, Aug 07, 2005 at 03:25:54PM -0700, Anirban Banerjee wrote:
> Thanx everyone for your replies :) , I'm trying to implement the RST algo.,
> Asiacrypt 2001 in OpenSSL.
> This details a trapdoor algorithm, where after a combining function I need
> to employ some strategy to raise a BN to 1/RSA_3 or 1/65535 :)) the popular
> RSA constants for 'e' .
That's better. So you really want to compute 1/RSA_3, this is not difficult
gcd(x,n) = 1 iff there exit a, b s.t. x*a + n*b = 1
Then x*a = 1 mod n, or a = 1/x mod n. Given x and n, Euclid's algorithm
finds "a" and gcd(x,n) (presumably 1).