🚀 go-pugleaf

In article <r09LrAXKBh107h@nadir.uucp> you write:
>In <PHR.92Dec16022546@napa.telebit.com> phr@telebit.com (Paul Rubin) writes:
>>    Please excuse my ignorance, but, how can "your wife" decode the message
>>    knowing 34, 91, 7, and 13?
>
>>    i.e. I have a number
>>      (X^3) moulo 77 (product of two primes) = 48
>>    what is my number? and how did you get the answer?
>
>[Stuff Deleted]
>
>>In the case of N=77 and N=91, phi(N) is a multiple of 3 so no
>>suitable t exists.  You have to have picked your original primes
>>p and q to make this not happen.
>
>O.K., now that you've excused my ignorance, I beg you excuse my stupidity.
>
>Same number  X^3(mod, 391) = 133
>(phi(N) is not divisible by 3) What is my number?
>
27.

>I tried to figure out t, but got stumped.

t is 235.  Other larger numbers like 587 will also work.
The method is explained in Rivest et al, "A Method for Obtaining Digital
Signatures and Public-Key Cryptosystems," Communications of the ACM,
vol 21, no 2, Feb 1978, pp120ff.
Section VII d and VIII are the most relevant.

Now, that we have gcd(PHI(n), d) = 1, e must be calculated.  This is
done by calculating a series x0, x1, .... with x0 = PHI(n), and x1 = d
(ie 3), and x(i+1) = x(i-1) (mod xi).  For each xi, a pair of numbers ai and
bi must be found that satisfy:
ai*x0 + bi*x1 = xi.
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.
My numbers:
    x   a   b
0  352  1   0
1    3  0   1
2    1 -2  235

>Thanks again,

I hope this helps.

>Rudy Crespin
>
>--
>                                                      _           _
>   ---   O       | Rudy Crespin                    | / \ |\ | __ / \ |\ |
>   --   <^-      | crespin@nadir.uucp              | \_/ | \|    \_/ | \|
>  --  -\/\       | crash!nadir!crespin             |
>  ---     \      |                                 |- No-No, it is On-On.

--
;---------------------------------------------------------------------
; Mark Johnson             ; msdos has 6 types of RAM - dos ram,
; My views are my own and  ; upper memory, high memory, extended memory,
; nobody else's.           ; expanded memory, and video ram.
;                          ; YUCKKK!!!!!!!!!!!
;---------------------------------------------------------------------