Re: Shifting alphabets

From: Milan VXdgsvt (milan_vxdgsvt_at_seznam.cz)
Date: 09/30/05 

Date: Thu, 29 Sep 2005 22:42:13 +0000 (UTC)

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

Relevant Pages

  • Re: reading text files
    ... > countPunct(infile, outfile, punctuation); ... It is not necessary for 'alphabet' to be a parameter passed from the ... is still true every subsequent time and this is an infinite loop. ... characters at the beginning of the input. ...
    (comp.lang.c)
  • Re: cracking the vigenere cipher when the key is non-alphabetic
    ... the characters in it will be from a single alphabet. ... If the plaintext uses full ASCII, ...
    (sci.crypt)
  • Re: National Language - question on alphabet/sort order
    ... This has little to do with the alphabet, ... I also doubt that accented characters are used for this even when the ... really used in the language. ... The initial market study might show you than you need more flexibility, ...
    (microsoft.public.vc.mfc)
  • Re: WANTED MORE JEWS PART 2
    ... legal blog - volokh.com) where they typically introduce characters with ... of the old phonetic alphabet. ... used in yeshivos to name characters in discussion is the names of the ... web-based forum, we can set up a separate section for off-topic ...
    (soc.culture.jewish.moderated)
  • Re: Etymology of the name KRAVITZ
    ... it could neve have evolved but for the fact that the sounds "B" and "V" are rendered by the same alphabet character in Cyrillic. ... The two characters look similar enough to anyone who does not know the alphabet or the language, ... The analogy Stan makes with the similarity between various Hebrew letters is a good one. ... My point was that the same thing can happen with the Cyrillic "B" characters, among people who were literate in Yiddish, but had some visual familiarity with Cyrillic alphabet letters. ...
    (soc.genealogy.jewish)