A GENERALIZATION OF THE KNAPSACK ALGORITHM USING GALOIS FIELDS

We prove a generalization of a theorem of Rejewski. This theorem shows how one can solve an equation of the form XY=α in a symmetric group, where α is a given permutation and X and Y are each of order two with a specified number of disjoint transpositions. The number of solutions is also part of the theorem. Using this theorem we outline what we believe was the Polish solution (or very close to it) to the Enigma assuming that one had no data from daily keys. With some assumptions on independence of events, we show that the Polish Cipher Bureau would probably have broken the Enigma in just over four years.