Forum de mathématiques - Bibm@th.net

from math import log10, exp
import random

logf4g ={}      # dic des log des fréquences des 4-grammes
f = open('brut4g_space_fr.txt')
total = 0       # effectif total
for line in f:
    (w, c) = line.split(sep= ' ')
    logf4g[w] = int(c)
    total += int(c)
for w in logf4g:
    logf4g[w] = -log10(logf4g[w]/total)
f.close()

def logscore(s):  # fonction de score
    logsum = 0
    default = 10          # quadrigramme inconnu
    for i in range(len(s)-3):
        logsum += logf4g.get(s[i:i+4], default)
    return logsum
   
alpha0 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def sub_polyalpha(crypto, liste_alpha):
    """ Substitution polyalphabétique sur 'crypto'.
        Les lettres de 'crypto' sont chiffrées séquentielement par les
        alphabets de 'liste_alpha'
    """
    idx = 0
    clair = ''
    for c in crypto:
        if c in alpha0:
            clair += liste_alpha[idx][alpha0.index(c)]
            idx = (idx+1)%len(liste_alpha)
        else:
            clair += c
            # idx = (idx+1)%len(liste_alpha)
    return clair

def nouvel_état(alpha):
    c = list(alpha)
    i, j, k, m = random.sample(range(len(alpha)), 4)
    choix = random.random()
    if choix < 0.7:
        c[i], c[j] = c[j], c[i] # permutation deux éléments
    elif choix < 0.8:
        c[i], c[j], c[k] = c[j], c[k], c[i]  # permutation circulaire 3 éléments
    elif choix < 0.9:
        c[i], c[j], c[k], c[m] = c[j], c[k], c[m], c[i]  # idem 4 éléments
    else:
        if i > j:
            i, j = j, i            # on veut i < j
        m = c[i:j]
        m.append(m.pop(0))      # rotation du segment c[i:j]
        c[i:j] = m
    return ''.join(c)
   
def critère_Metropolis(delta, T):
    if delta <= 0: return True
    if random.random() < exp(-delta/T) and delta/T < 0.05:
        return True
    return False
   
def RS_PolyAlpha(crypto, periode, max_iter = 0, CoolRatio = 0.5, trace=True):  # recuit simulé
    if max_iter == 0:  # valeur par défaut
        max_iter = periode*10000
    myalphas = []    # liste des alphabets courants
    a = list(alpha0)
    for i in range(periode):
        random.shuffle(a)
        myalphas.append(''.join(a))
    clair = sub_polyalpha(crypto, myalphas)    
    old_score = logscore(clair)
    T = 200          # température initiale
    print('T0 =', T)
    best_clair = clair
    best_alphas = myalphas.copy()
    best_score = old_score
    freeze = 0
    idx_alpha = 0
    while True:
        nb_iter = 0
        while nb_iter < max_iter:
            nalphas = myalphas.copy()
            nalphas[idx_alpha] = nouvel_état(nalphas[idx_alpha])
            clair = sub_polyalpha(crypto, nalphas)
            new_score = logscore(clair)
            delta = new_score - old_score
            if critère_Metropolis(delta, T): # transition acceptée
                myalphas = nalphas.copy()
                old_score = new_score
                if old_score < best_score:
                    best_score = old_score
                    best_alphas = myalphas.copy()
                    best_clair = clair
                    if trace:
                        print(best_score)     # trace
                        print(best_clair[:80])
                        print()
            nb_iter += 1
            idx_alpha = (idx_alpha+1)%periode
        T *= CoolRatio
        print('T =', T)
        if T < 10:  # condition d'arrêt
            break
    print("*** Meilleure solution ***")
    print('score = ', best_score)
    print('alphabets :', best_alphas)
    print(best_clair)
 
# Le cryptogramme
 
k = 'FF_IBWITOL_VUMY_VL_XMVWDADW_FCV_NKHWMDAI_RW_GFSHLNZT_ITFJ_RW_TPOIQBI_\
HIA_BWHEIKQ_HD_JJW_OJZVFTW_JRI_DT_XUALWXWTJY_ASC_VI_VDIMI_HIB_DUVXKMTMVQIVMWQ_\
MZOSCHVJFJAKXF_QJZ_T_FF_KTAI_EM_BNRVC_YIKVJZXLM_TPOIQAHCTXHI_KMBQQ_XTIWAOAWZT_\
QLLLJC_PSX_EIV_JUQBF_YI_PKH_HF_EV_MH_ICTNLXP_XUABVWUTG_TK_WCYHWWCQI_NOFFKVXWHZEJ_\
ALTI_DFDVC_WZA_NYERUAHF_RM_KKTVM_UV_JKTLYMI_FKHW_WLEHX_YL_VQMZNTHAA_PSH_\
JLDNHCYI_RMP_UAUILV_OF_J_T_OJMVPSH_ORNCI_MDH_XMPCI_AACPMIYPHOYJ_B_MUFGF_\
OMZJFRTZVMKM_STQ_FG_SITIJV_FF_NXTC_EEKRUAUV_IW_YC_LSSY_UIRTBBVH_AL_LQSZ_\
PLAINZ_HR_NLTD_IZYI_KDIAXAMWQ_YI_DT_EXMPVMKM_HF_ASCVOJM_BYZNM_STQ_JTI_INNYWV_\
TM_AFRV_RTJ_KDHTCHAHDQ_X_CPV_RW_BV_JHABRGIQA_OJT_BEMNFFQRI_DJ_WHQNCLOYL_\
FSIOJMW_QJQHPTLTT_NC_II_KQKWJ_IWT_FK_SQ_UHHE_SVCNDWYQF_CA_NH_AJ_Q_LA_HCBUHY_\
IHH_WD_UZTFGXOCC_EI_R_WN_VKIQFBQ_XDTHXMHVMW_IF_JRIDXSH_OMEJH_MW_BLH_RJSW_\
MAZI_ZECKORXJ_PH_QJQHPTLTT_X_CPV_R_WURHXWBRLM_YTMN_KKZMHI_ANRC_DT_JWQDUVJQL_\
AR_TTIPH_WDCLTF_STQ_MTACH_IBWITOL_LQSZ_VL_XMLVFHQ_DF_CIQAHVMIC_INF_XX_CZWYXH_\
JJ_Q_LXF_LQ_YI_DT_JKTJFXH_WMQZIQAHZEJ_U_INF_DF_ASX_IZJI_SESNIL_X_MACYXLMY_B_\
XULADQMFYI_VMHV_JA_AJTC_JGLZTI_XHI_TDMV_KI_IKTIQJFPXDWV_XLOTHN_FKCLRMYFKV_DJ_\
TQIAVCH_JL_KU_WXJ_IW_JJ_Q_STTQFNJ'

RS_PolyAlpha(k, 14, CoolRatio=0.8)