Algorithm optimization in the enigma app

log in

Advanced search

Message boards : Number crunching : Algorithm optimization in the enigma app

Author Message
Alex VE3NEA
Send message
Joined: 22 Oct 16
Posts: 7
Credit: 8,570
RAC: 0

Message 4143 - Posted: 23 Oct 2016, 1:09:45 UTC

Hello,

Here is my attempt to improve the hill climbing algorithm used in the enigma app.

Hill climbing finds the plugboard connections by trying every possible way of re-connecting the letters, scoring the decrypted text, and retaining the modifications that improve the score. Some modifications that the program tries have a very small probability of improving the solution, and some others are tried twice during the same pass. Elimination of the inefficient and redundant modifications dramatically improves the speed: the modified program makes three quick passes in the time of a single slow one, and the chances of finding the solution significantly increase.

The new algorithm was tested on 1000 messages, randomly selected from a text in German and encrypted with random M3 Enigma settings. The n-gram dictionaries were generated from the same text.

Here is a plot of the success rate of solving the plugboard vs. the time spent on each plugboard. The new algorithm performs better than the original hill climbing at all message lengths.





The plotted data in the tabluar form are here (sorry, I am not allowed to post url's here):

http://www.dxatlas.com/DxMath/Enigma/EnigmaSpeed.txt


The new executable for Windows is here for you to try:

http://www.dxatlas.com/DxMath/Enigma/EnigmaProject.exe.zip

Note that this program requires a unigram dictionary (included).


The source code of the modified enigma, (compiles in Visual Studio 2015), the testing application, and the test data are here:

http://www.dxatlas.com/DxMath/Enigma/EnigmaSolution.src.zip


Cheers,

Alex

jj666
Send message
Joined: 10 Mar 14
Posts: 8
Credit: 68,796,111
RAC: 3

Message 4158 - Posted: 6 Nov 2016, 0:26:07 UTC - in response to Message 4143.

Hello there,

Currently using Agbar's optimised binary. I notice with this release, there are no app_info.xml or wrapper.exe.

What's the correct procedure for installation/testing?

Cheers,

-jj-

oh2hyt
Send message
Joined: 14 Jul 09
Posts: 25
Credit: 22,813,964
RAC: 2,977

Message 4162 - Posted: 6 Nov 2016, 17:44:24 UTC
Last modified: 6 Nov 2016, 17:46:17 UTC

I think we should get TJM's approve before using this for Enigma@Home as this version gives different results than other so far optimized executables. This is logical, because this use different algorithm.

I tried already contact TJM, but no repply.

Speedwise this would be -60% computation time compared optima avx2, BUT this one doesn't achieve as high scores always.

Alex VE3NEA
Send message
Joined: 22 Oct 16
Posts: 7
Credit: 8,570
RAC: 0

Message 4171 - Posted: 10 Nov 2016, 22:48:14 UTC - in response to Message 4158.

This program is only for testing and for stand-alone execution, not for the enigma@home work yet. It will likely need a different work unit type since it works with unigrams instead of bigrams, and requires a different number of passes.

Alex


Post to thread

Message boards : Number crunching : Algorithm optimization in the enigma app


Return to Enigma@Home main page


Copyright © 2017 TJM