Re: Shifting alphabets

ht9j35r02@sneakemail.com wrote:

> For any given plaintext alphabet of length N, is it possible to find a
> crypt alphabet arrangement that can NOT be shifted into a position
> where it has zero collisions with the plain text alphabet.
>
> From trial and error, it seems that for any plaintext alphabet with
> an EVEN number of letters, you can ALWAYS find at least one
>
> So, I started trying to PROVE this rule.
>

You could try the following proof by construction:

we have
   abcdefgh
   12345678
and want to find an offset of the bottom row.
1. So, either
  a) there's no match and we're done, or
  b) at least one column has a match. So, rotate the lower line by one
char to the right. For example, suppose the match was in column a:
   abcdefgh
   8A234567
2. if there are more than 2 undiscovered letters, go back to 1
3. now we have something like
   abcdefgh
   EG5BD8AC
  a) If we started with odd number of characters and got something like:
   abcdefg
   CEGBD7A
  now the last character must match itself and this is not a solution.
If we shifted one more time, we would arrive back at the first offset
which had a match, and thus this has no solution. Thus, for odd
lengths, solution does not always exist.
  b) if we started with even number of characters, then either it's
   abcdefgh
ba)EGFBDHAC which is solution, or it's
bb)EGHBDFAC which can be solved by one more shift:
   CEGHBDFA (before, we tried N-2 shifts and identified all N-2
characters, so one more shift cannot match anything in the solved
letters; the shift breaks the matching pair and cannot create a new
pair)

This is in no way a *mathematical* proof, but I find it quite
convincing. It may need some polishing, especially the 3bb) part, but
I'm pretty sure it's all true.

  Milan
Received on Sat Oct 15 04:37:52 2005