kouzdra (kouzdra) wrote,
kouzdra
kouzdra

Задачко:

Питер Донован в статье The Flaw in the JN-25 Series of Ciphers, II пишет:
This paper deals with codebooks assigning to each word or phrase in a (long) list a 5-digit ‘group’ which is a multiple of three or scannable in the jargon of WW2. Here the groups are allowed to have initial 0s: thus 12345 and 00078 are groups.

Being a multiple of three (equivalently, being divisible by three) means that the corresponding number, 12345 or 78 in these examples, is a multiple by three or, equivalently, the sum of the five digits, 15 in both examples, is a multiple of three.

The characteristic χ of such a group is defined to be the reduction modulo 10 of the sum of the five digits: thus χ(12345) = 5.

One might well guess that of the 33334 scannable groups from 00000 to 99999 about 3333 have characteristic 0, about another 3333 have characteristic 1, etc. This is far from being the case. A simple electronic calculation checks that for 0 ≤ i ≤ 9 the number m(i) of scannable groups with characteristic i is as set out below:

m(0) = 3247 m(1) = 5875 m(2) = 1780 m(3) = 1780 m(4) = 5875
m(5) = 3247 m(6) = 925 m(7) = 4840 m(8) = 4840 m(9) = 925.

These Mamba numbers, were known to the American naval cryptanalysis unit Op-20-G in 1943 but the calculation must have been quite tedious. Working out that it was worth calculating at all was a major achievement in cryptanalysis.
Понятно, что для 5-значных групп прямой перебор решит задачку в момент.

Требуется написать прогу, которая будет вычислять mamba numbers для произвольного n. Ну чтобы не создавать проблем любителям С и Java пусть n ≤ 18. Этого достаточно уже, чтобы тут уже не работал брютфорс.
Subscribe

  • "Трагедия курьера"

    Что забавно - попытки партии и ментов усиливать контроль за всем на практике дают противоположный результат - паспорта у меня в данный момент нет,…

  • Из комментов

    Впрочем у истории с чёрными кораблями были две забавные концовки — одна в Порт-Артуре, другая — в Жемчужной гавани

  • Во всяком культивировании

    всяких покрытых богоматерей, дней оун-упа и прочих мининых-невских-пожарских и тп меня раздражают не поводы (на них мне действительно насрать) а…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 9 comments