One question is how the triple (*N*, *p*, *s*) is chosen. Clearly, if *M* is
the order of the group of units in
/*N*, then one way to
recover *s* given *p* is by the relation
*ps* = 1(mod *M*). Thus, one
consideration is that given only *N* and *p* it should not be easy to
determine *M* (or else *s* is not secret at all!). Clearly, if a
complete factorisation of *N* is known then this *M* can be easily
determined. However, note that if *k* is the *exponent* of the
group of units in
/*N* (i. e. the least common multiple of
the order of all elements) then it is enough to know *k* rather than
*M*, since solving
*ps* = 1(mod *k*) is adequate.

A related consideration is that there should not be too many elements
in
/*N* which are *not* units. The encrypter/decrypter
should not have to worry about checking for this while constructing
messages.

Both these considerations lead us to take for *N* = *ab* a product of two
large primes *a* and *b* (we will see some additional constraints on
the pair (*a*, *b*) as we go along). It is generally expected (and in the
next section we will see some evidence of this) that factoring a
number which has *all* factors of size (in terms of ``log'') *r*
or more is much harder than checking that a number of size *r* is
prime. Thus, it should be easier to construct key triples than it is
to ``break'' keys (by determining *s* given *N* and *p*). Note that
*M* = (*p* - 1)(*q* - 1) in this case and in general there does not seem to be a
way to determine *M* (or the exponent *k* for that matter) without
determining a factoring of *N*. The only elements *m* in
/*N*
that are not units are *p* and *q*, thus this choice is also good from
this point of view.