Re: RSA Question (was Re: PKP/RSA comments on PGP legality)

Article View: sci.crypt

Article #2366

#2366

From: Paul Rubin
Date: Thu, 17 Dec 1992 22:10

10 lines
1094 bytes

    As far as I know the most efficient way to solve this is to try different
    values for a until you get a positive integer for b.

Nah.  Modulo N, all integers are positive.  -2 is the same as 350,
mod 352. 

See any algorithms book under "Extended Euclidean Algorithm" for
more description.  Just think of it as the ordinary Euclidean
GCD algorithm, except you keep track of how much of each number
you throw away (sorry if that makes no sense).

Technical Details

Message-ID: <PHR.92Dec17221030@napa.telebit.com>

Path: arc1-ca.pugleaf.net!sparky!uunet!telebit!phr

References:

<1992Dec14.190615.13954@macc.wisc.edu> <PHR.92Dec16022546@napa.telebit.com> <r09LrAXKBh107h@nadir.uucp> <1992Dec18.001213.8000@newton.ccs.tuns.ca>

Show Full Headers

Complete Article Headers

Newsgroups: sci.crypt,alt.security.pgp
Path: arc1-ca.pugleaf.net!sparky!uunet!telebit!phr
From: phr@telebit.com (Paul Rubin)
Subject: Re: RSA Question (was Re: PKP/RSA comments on PGP legality)
In-Reply-To: johnsomr@newton.ccs.tuns.ca's message of Fri, 18 Dec 1992 00:12:13 GMT
Message-ID: <PHR.92Dec17221030@napa.telebit.com>
Sender: news@telebit.com
Nntp-Posting-Host: napa.telebit.com
Organization: Telebit Corporation; Sunnyvale, CA, USA
References: <1992Dec14.190615.13954@macc.wisc.edu> <PHR.92Dec16022546@napa.telebit.com>
 <r09LrAXKBh107h@nadir.uucp> <1992Dec18.001213.8000@newton.ccs.tuns.ca>
Date: 17 Dec 92 22:10:30
Lines: 10

Reply to Parent Message