Re: Modular cube root question

From: Derek Thomson (derek_at_hiredgoons.org)
Date: 04/08/04 

Date: Fri, 09 Apr 2004 02:39:08 +1000

Paul Rubin wrote:
> Derek Thomson <derek@hiredgoons.org> writes:
>
>>description of RSA key generation (section 8.2.1) says "selected a
>>random integer e, 1 < e < phi, such that gcd(e, phi) = 1", and phi is
>>given as (p-1)(q-1).
>>
>>Now, the book doesn't *say* this, but I'm guessing that this is the
>>magic that makes "x**e mod n" one-to-one, but I don't quite see
>>how. Is this actually expounded upon somewhere in the book?
>
>
> Yes, that's correct, e must have no common factors with phi(N). I
> don't know if the book explains that.

It does say that, but doesn't *explain* it anywhere, or even provide the
tiniest hint that this is what makes it one-to-one. This is irritating
for someone who just doesn't take things at face value. On the other
hand, I'm pleased that I managed to reason out the explanation correctly.

> You may want a book that goes
> more into the math, if it's unfamiliar to you. "A Course in Number
> Theory and Cryptography", by Neal Koblitz, is pretty good.

I'm okay with the basic operations (modular arithmetic, gcd et al), but
this book just doesn't seem to be particularly rigorous about the
assertions it makes or the conclusions it draws (so far). Once again, I
suppose it's just because when I read "this is a hard problem", or "you
must do X, Y and Z and it just works out" or some other unjustified
statement, I just want to know "why?" :(

Or maybe you are not supposed to think too hard about what's said in the
first chapter, and all will be explained later - although skipping
around it doesn't look like it. The RSA section appears to just be a
description without any support at all, such as the real purpose of
using gcd in determining e. I will look up your recommended reference,
it sounds like it will be helpful!

Thanks for all your help,
Derek.

Relevant Pages

  • Re: A gcd proposition
    ... A non-negative common ... and let d' be a non-negative common divisor divisible ... all common divisors divide the gcd ...
    (sci.math)
  • Re: tell me if this is right.
    ... > Now to reduce i've applied the Euclidean algorithm ... Before explicitly finding the GCD, it's worth checking if you can see ... any common factors 'by inspection' ...
    (sci.math)
  • Re: LCM and HCF
    ... teaching) HCF and LCM? ... easier to keep dividing by common factors. ... LCM for fraction addition maybe, but it's easier to cross-multiply and ... For small numbers one should know directly what the GCD is, ...
    (rec.puzzles)
  • Re: A gcd proposition
    ... A non-negative common ... divisor d is their gcd if and only if c | d for every common ... and let d' be a non-negative common divisor divisible ... all common divisors divide the gcd (which is a nongegative common ...
    (sci.math)
  • Re: inverse mod n
    ... is it a hard problem to find x*y=1 mod n ... It is quite easy unless x and n have a common factor greater than 1. ... display article in a monospaced font ...
    (sci.math)
Quantcast