/* -------------------------------------------------------------------- */
/*  Modulos Criptologicos desenvolvidos no ambito da accao de formacao  */
/*                                                                      */
/*            ELEMENTOS DE CRIPTOGRAFIA CONTEMPORANEA -- 2008           */
/* -------------------------------------------------------------------- */

/* CRIPTOGRAFIA CLASSICA */

/* Alguns textos... */

sonhoAG="eles nao sabem nem sonham que o sonho e uma constante da vida tao concreta e definida como outra coisa qualquer como esta pedra cinzenta em que me sento e descanso como este ribeiro manso em serenos sobressaltos como estes pinheiros altos que em verde e oiro se agitam como estas aves que gritam em bebedeiras de azul eles nao sabem que o sonho e vinho e espuma e fermento bichinho alacre e sedento de focinho pontiagudo que fossa atraves de tudo num perpetuo movimento eles nao sabem que o sonho e tela e cor e pincel base fuste capitel arco em ogiva vitral pinaculo de catedral contraponto sinfonia mascara grega magia que e retorta de alquimista mapa do mundo distante rosa dos ventos infante caravela quinhentista que e cabo da boa esperanca ouro canela marfim florete de espadachim bastidor passo de danca colombina e arlequim passarola voadora para raios locomotiva barco de proa festiva alto forno geradora cisao do atomo radar ultra som televisao desembarque em foguetao na superficie lunar eles nao sabem nem sonham que o sonho comanda a vida que sempre que um homem sonha o mundo pula e avanca como bola colorida entre as maos de uma crianca";

textoM="Monólogo por Chico Anísio -- Mundo moderno, marco malévolo, mesclando mentiras, modificando maneiras, mascarando maracutaias, majestoso manicômio. Meu monólogo mostra mentiras, mazelas, misérias, massacres, miscigenação, morticínio - maior maldade mundial. Madrugada, matuto magro, macrocéfalo, mastiga média morna. Monta matungo malhado munindo machado, martelo, mochila murcha, margeia mata maior. Manhãzinha, move moinho, moendo macaxeira, mandioca. Meio-dia mata marreco, manjar melhorzinho. Meia-noite, mima mulherzinha mimosa, Maria morena, momento maravilha, motivação mútua, mas monocórdia mesmice. Muitos migram, macilentos, maltrapilhos. Morarão modestamente, malocas metropolitanas, mocambos miseráveis. Menos moral, menos mantimentos, mais menosprezo. Metade morre. Mundo maligno, misturando mendigos maltratados, menores metralhados, militares mandões, meretrizes, marafonas, mocinhas, meras meninas, mariposas mortificando-se moralmente, modestas moças maculadas, mercenárias mulheres marcadas. Mundo medíocre. Milionários montam mansões magníficas: melhor mármore, mobília mirabolante, máxima megalomania, mordomo, Mercedes, motorista, mãos... Magnatas manobrando milhões, mas maioria morre minguando. Moradia meia-água, menos, marquise. Mundo maluco, máquina mortífera. Mundo moderno, melhore. Melhore mais, melhore muito, melhore mesmo. Merecemos. Maldito mundo moderno, mundinho merda.";

ArteE="É melhor ser alegre que ser triste A alegria é a melhor coisa que existe É assim como a luz no coração... Mas p'ra fazer um samba com beleza É preciso um bocado de tristeza Senão não se faz um samba não... Senão é como amar uma pessoa só linda... E daí ?... Uma pessoa tem de ter qualquer coisa além da beleza... Qualquer coisa de triste... Qualquer coisa que chora... Qualquer coisa que sente saudade... Um molejo de amor machucado... Uma beleza que vem da tristeza de se saber humano, Feito apenas para amar Para sofrer pelo seu amor E para ser só perdão Fazer samba não é contar piada Quem faz samba assim não é de nada O bom samba é uma forma de oração Porque o samba é a tristeza que balança E a tristeza tem sempre uma esperança... Uma esperança de um dia não ser mais triste não Feito essa gente que anda por aí brincando com a vida... Cuidado, companheiro! A vida é p'ra valer! E não se engane não, tem uma só! Duas mesmo que é bom ninguém vai me dizer que tem Sem provar muito bem provado Com certidão passada em cartório do céu E assinado embaixo: DEUS! E com assinatura reconhecida! A vida não é de brincadeira, amigo! A vida é a arte do encontro Embora haja tanto desencontro pela vida Há sempre alguém à sua espera Com os olhos cheios de carinho E as mãos cheias de perdão Ponha um pouco de amor na sua vida Como no seu samba Ponha um pouco de amor numa cadência E vai ver que ninguém no mundo vence A beleza que tem um samba não";

/* -------------------------------------------------------------------- */

/* EXEMPLOS de algumas instrucoes */

/* Um vector com os codigos ASCII das letras ABCZabc: */

/* Vecsmall("ABCZabcz") */

/* A "string" com as letras com os codigos ASCII 65, 66, 122 pode ser
produzida com a instrucao: */

/* Strchr([65, 66, 122])*/

/*--------------------------------------------------------------------*/
/* A funcao seguinte remove acentos, pontuacao e espacos de um texto,
transformando todas as letras em maiusculas */

LimpaT(txt)={
  local(len,ntxt,vtxt,k);
  vtxt=Vecsmall(txt);len=#txt;
  ntxt=listcreate(len); 
    k=1;
  while(k<=len,
    if(vtxt[k]>96 && vtxt[k]<123,listput(ntxt,vtxt[k]-32));
    if(vtxt[k]>64 && vtxt[k]<91,listput(ntxt,vtxt[k]));
    if(vtxt[k]==-61 && ((vtxt[k+1]+32<-92 && vtxt[k+1]+32>-97)
        ||(vtxt[k+1]<-92 && vtxt[k+1]>-97)),
           listput(ntxt,65);k=k+1);  /* ãâáàÃÂÁÀ ---> A */
    if(vtxt[k]==-61 && ((vtxt[k+1]+32>-89 && vtxt[k+1]+32<-85)
        ||(vtxt[k+1]>-89 && vtxt[k+1]<-85)),
            listput(ntxt,69);k=k+1);  /* êéèÊÉÈ ---> E */
    if(vtxt[k]==-61 && ((vtxt[k+1]+32>-85 && vtxt[k+1]+32<-81)
        ||(vtxt[k+1]>-85 && vtxt[k+1]<-81)),
             listput(ntxt,73);k=k+1); /* îíìÎÍÌ ---> I */
    if(vtxt[k]==-61 && ((vtxt[k+1]+32>-79 && vtxt[k+1]+32<-74)
        ||(vtxt[k+1]>-79 && vtxt[k+1]<-74)),
             listput(ntxt,79);k=k+1); /* õôóòÕÔÓÒ ---> O */
    if(vtxt[k]==-61 && ((vtxt[k+1]+32>-72 && vtxt[k+1]+32<-68)
        ||(vtxt[k+1]>-72 && vtxt[k+1]<-68)),
             listput(ntxt,85);k=k+1); /* ûúùÛÚÙ ---> U */
    if(vtxt[k]==-61 && (vtxt[k+1]==-89 || vtxt[k+1]==-121),
             listput(ntxt,67);k=k+1); /* çÇ ---> C */
    k=k+1);
  return(Strchr(Vec(ntxt)))
  }

/*--------------------------------------------------------------------*/
/* A funcao seguinte arranja um texto "limpo" em grupos de 5 letras */

arranjaT(txt)={
  local(len,ntxt,vtxt,k);
  vtxt=Vecsmall(txt);len=#txt;
  ntxt=listcreate(len+ceil(len/5)); 
    k=1;
  while(k<=len,
        if(k%5==1 && k>1,listput(ntxt,32);listput(ntxt,vtxt[k]),
                         listput(ntxt,vtxt[k]));
        k=k+1
       );
  return(Strchr(Vec(ntxt)))
  }

/* -------------------------------------------------------------------- */
/* Funcao para gerar uma chave aleatoria com 26 caracteres, para a
cifra de substituicao mono-alfabetica simples, e uma outra para
calcular a inversa de uma chave desse tipo */

chave()={
  return(numtoperm(26,random(26!)))
  }

invchave(chv)={  
  return(vecsort(chv,,1))
  }

/* A chave numa forma alfabetica... */ 

chaveA(chv)={
  return(Strchr(chv+vector(26,i,64)))
  }

/* -------------------------------------------------------------------- */
/* Cifra (ou decifra) a mensagem "txt" com a cifra de substituicao
mono-alfabetica simples, usando a chave "chv" (ou o seu inverso,
respectivamente) */

CifraSubst(txt,chv)={
  local(len,vtxt,criptgr);
  txt=LimpaT(txt);
  len=#txt;
  criptgr=listcreate(len);
  vtxt=Vecsmall(txt);
  for(k=1,len,listput(criptgr,chv[vtxt[k]-64]));
  criptgr=Vec(criptgr); len=#criptgr;
  criptgr=criptgr+vector(len,i,64);
  return(Strchr(criptgr))
  }

/* -------------------------------------------------------------------- */
/* Exemplos * / 

/*
chv=chave();

ichv=invchave(chv);

cpt=CifraSubst("esta frase nao e muito secreta",chv)

CifraSubst(cpt,ichv)
*/

/* -------------------------------------------------------------------- */
/* Conta o numero de ocorrencias da letra L, que deve entrar como
string e ser maiuscula, no texto txt...*/ 

CountL(txt,L)={
  local(ct,len,v);
  ct=0;len=#txt;
  v=Vecsmall(txt);
  for(k=1,len,if(v[k]==Vecsmall(L)[1] || v[k]==Vecsmall(L)[1]+32,ct=ct+1));
  return(ct)
  }

/* Exemplo */

/* 
txt="Esta e uma frase que serve apenas para experimentar a funcao
que conta o numero de ocorrencias de uma certa letra em textos";

CountL(txt,"O")
*/

/* -------------------------------------------------------------------- */
/* A funcao seguinte fornece a lista das frequencias de cada uma das
letras num texto */

EstatCritog(txt)={
  local(len,ct);
  len=#txt;
  for(k=1,26,ct=CountL(txt,Strchr(64+k));
      print(Strchr(64+k),": ",ct/len*100.0))
  }

/* -------------------------------------------------------------------- */
/* Dois criptogramas: um cifrado com uma cifra de substituicao e o
outro com a cifra de Vigenere */

Criptgr1="HKVAP HQHSH LQZAQ PHQZK ZZSMV QPZSS LYBLY DLVHT LKVKQ ZKJHQ VLAQV HULQP HTHTL KHBLS HSZAP ZSLHG VNZSZ PZBWZ LZSKD BZSSZ HBLVH LHDSL AQVHK VAPHQ HSHSZ DLDLZ SKLDS QHJBV QPZSZ ZBYDG PZQHB BLYHT ZTLVA ZQLAQ VHSLH SFLRL STHDK HFHBH ATHFL AQLHZ SHGID LZSSH AWZSL SMZBZ ZDAZS AVQPZ SLWLG PHTZS HTLFV TBZLL SQHTH BVHSU BHYLV SQZML BWHST LPLBH ZPMBZ ARLUH GSZGH BLVBH HMLBW HJLGZ FLAWZ HSSHG HSUBV HSHKV APHQH SHKHS LZDWB HHPVS WZBVH SZDLD HZFLA WZLHQ PDFHH IDVTL SQHGQ ZSLAW HTZAD KHJLT BHTLK LKZBV HFVWZ BVAZA LKLSV ZWDID LTZBK LSLSJ VBVWZ SLBLA ZJZSW ZHSZK MBHTZ SQLTB ZSSLQ DGHBL SQZKZ DKGLF VWHHS ZKMBH TZSHG WHBLS GZAYL THGDW HLTZU BHYZB WLBBL AZHQZ BTHLW LKJZZ SZGEH HGWZL JGLAZ HUDYD LAWZD HSGHB FHSWD KDGHB LSJHB HSDBY VBTZS LVZTL SSLSK HBLSD KKDAT ZAZFZ LSJLB HSZDK HQLAZ LSQDW HLHYB HATLF ZRTHS KDGWV TZLSS HZWLD SVBKH ZSIDL SLLBY DLKSH ZQHAQ ZLSKH STLYD LBBHL SHZFZ RLSTL BLMHW LLBYD LWLJZ VSSZG THTZT ZUDWD BZLTZ SBHVZ STLGD RTZSZ APZJD BZSZA PHTZB UHRLL SJHTH TLQZK MHWLH AWLBZ TLIDL AWHGZ GPHAT ZZKHB SZAPZ SLKWL BTLID LAHTH AZKHB SHGFZ ZSLBK HBSLF LKHST LSLAH THFLB IDHAW ZHHGK HSZAP HTLID LKLSL BFLKH FLBTH TLLHU LFLBQ GHBZI DHAWZ SIDLU HWHVS LBBHK ZSLKB DHSZD LKLSW BHTHS ZDSZM BHKZS WLKZS LSWHQ LBWLR HLSLK JBLLL KWDTZ SZAPH KZSLS ZAPHK ZSLSZ APHKZ SHSHB FZBLS GZAYV AIDHS THUGZ BLSWH JHBLQ LKJZB GZAYV AIDHS SWHBL KULSW HIDHA WZHQZ AWLQL JZBID LSLAH ZFLKH STZID LPHJZ DQZZD AHZPH ZKLSK ZBLSW HSLWV FLHKZ BLSEH AHZSL VSLZS WVFLI DLKZA WLKUD VEHPZ ELLKK VKAHZ FVFLM LMLID LWDTZ LGVID VTZLL KMBVH YHLHF VTHKZ BBLLA IDHAW ZZSLB BLFVF LQZGP LSBZS HSIDL QZGPL SSLPH ZTLSL BKZWV FZSQZ GZBVT ZSTLK ZBBLB KHSQZ GPLBZ SHSJZ BIDLA HZQZG PLGHS SLWLH YBHTH LWDTZ LTLVN HBTLZ PHFLB ULBAH ATZJL SSZHU VRQZK HSUHT HSDKH HGVHA QHHTL SWLQZ AWZAD AQHQZ AWHBK HSQZK ZHVAT HSZDQ BVHAQ HIDLB ZHKVK JBZJB VHLKM HGHBL SWHFH KAHJB HVHWB LSTZA RLGHS QZKZW BLSGH BHAEH SADKJ ZKHBA LAPDK HSHMV HJHBH IDHGT LGHSQ HAWHF HZJBV AQVJL TZKHB BZSHS UHWHV SHSWB LSTZA RLGHS HKHZT LLSJD KHHST LSUZG PZDAL APDKS ZDMLJ HBHID HGTLG HSZJB VAQVJ LTZKH BQHAW ZDTZS LAWVK LAWZW BHYVQ ZTHFV THAHZ PHBLF ZGWHA ZPZKL KIDLS LBLFZ GWHQH GQHTZ ZIDLA LGLSL BLFZG WHLHJ LAHSD KMZQH TZIDL TLAWB ZUVQH HYHBB HTZHW HMDHT HWLZB VHHID VGZID LALGL KLAWL LJHBW LLKUV GZSZU VHLJZ BFLAW DBHHS LKLAW LTZUB DWZID LALGL AHSQL LHSLT LAHZG PLHGV FVHBL FZGWH LWLBS LAHSQ VTZSL KTLSQ ZMBVB ZSLAW VTZTZ IDLAZ SPHTL KHWHB BLMLG TVHLZ IDLJZ LAHAZ SSHKH ZDKJD APHGJ HBHFV MBHBA HIDLG HKZBW LIDLA ZSKHW HTLFH YHBLS ZTLJZ VSTLV AUZBK HTZSZ TLJZV STLLS QGHBL QVTZB LMLGT LADLT LVWHT ZVBZA VHTLS HMLBZ IDLSZ LAWHZ SLSHM LLAHZ SLJZT LQZAW HBAHW HGVHQ ZBBLV HHKHT ZBSLK QZVSH HKHTH BLSZG FVHAT HBAHB DHQZK ZSZGP ZSJZS WZSAZ QPHZI DLKKL IDVSL BIDLK LQPHK LZDID LKLWZ IDLQZ KHKHZ IDHAT ZHHAY DSWVH LKMHQ VHBTL WLTVZ ZSZGP ZSFVT BHTZS ZGPHB LVJHB HZSJB LTVZS HGWZS JHBHH SWLGP HSTZS WLGPH TZSHK HTZBS LKQZV SHHKH THHJB LATVR QZGLY VHGSZ DHKHT ZBTHL NVSWL AQVHA HZQPL YZHJB ZUVSS VZAHG HAWZA VZYLT LHZ";


Criptgr2="QGXDE SOWHD DWQSF HLSBS PDOUG ZEUDS VORHL SRCGR OKQAI QDSDI EXMXA FQLGM QWVRS WMUMW AKQSW JUWUF EIRWY SGUEH UHECI YGSDD GMQWE HFDGH YDFJQ AIFOE AOWHD WNSFH NMYOE YIVQN HHGSD UEQTS OCQRU EOOZD LGESI VPSZH ERUUA ASXMN QBXUE UABGH BWFFI PEWRF IPEXD SQHEL DSQHF JUCVH NLAJS RDWXW FHLMX OWRBJ QCGKA JOCMP UFPCI HSLDS QHBSD QSGEA ZQSJN AFCPH MWOOH DHGYS QFAVM QIOUD MSGRM GGAXH CAPCS UGSZW GRQMQ BERSW OORHM UAOKX LSCII DSAYS WPOKQ SWWIE GZEHV SUBYP MWPWH RPSZW GRAHQ FJHIU ACEIO UMUIP ODTCM PAYQA TRRAY OKHMF GAEFO EAQER CJQGG HNLQS RFHWY GIPEG ECPKO KPSEJ USFOR WOKAB LRTSZ HEPAY AOXDN LMQSL SSFOR WAYQB XHSSA OYWOE AJILS DMAFU ELMGQ RTGEJ IVPSE PMFIU XSXDS UMFVR SUMFV LNZAG GDRJQ HEVEY QBXHS WYDVH MSUGK HNLQU IQTWS SRWEY QBXHG WZHIQ UEFIQ XLLAD IUMSZ SRWEI GSRDO UMBWD NWYRI VCSZQ EXMJU CUXEF AAEUS WXORF AWYQE XDSXC WDCGD FIQTW FORWO KABLR TSZHE HSHQF EQCSF ORWAE MUSDT SZHEJ EFFSE QTGZW SJEVQ OSTUW MASUN SAAIH NYMBE FOEMG YDBJM BHXRS ESHHA FFWKD CZMAE PADHW ZHASY OVJUJ MRYPA EMBGK AFQUV DDMYO THDJM TVLAI GSEPO JZOSV EWZHV HGSZO RRILQ JECIS QOWYO RQGIP BSDQE PNMYG MOEFO WSDFD UHSTU SZHSP AAEGI DPSDH EPMSU GWHOM HSSVE MSFMW OEGWX RAXXC VGAKM UYDSF AWXHM SDWRK EADOZ HMVQJ EJAJU BLRPS DOEPI FTOFH IJMSQ QONMG GRULM REVJM ZHSGE MYOLH RSZOW FEERZ SUEKH SVPED TOWSE DMDVL MSHSV DAKEW QWUKA IFHRS EWVPA UAHSY ISPWD HREQG IHSHQ FEVOF MGGHR VARMD JGESE IOFEC SVAEM BXHSK QAHLN ZQWVR TAZVE POJAG XRATQ FXRAI GSQSA KEOZD TAZVE PLWZR EVEEU HSVEX DWSQO UAFEF AGFWR KAEVO VGIFE CRGES XIESA KESEY AVQAE RSVMR EVCGY OEJUS QIQDN BARIS EVDOT RRADA ERTAZ VEPCG YCXRD SMUIQ TWAAM OAYDS HHCSP OHLAW EQSUR WZRSS EDAGX HLZMR SVEGX VSVDW AWVRO FPSEU DAMAS VSGZV SVMSU GXUEK YOPKA VAGXL NZMAJ RMWQG IGEUA ASRST UQLRS WEWPH NUUCE UOVMR SVSWG GTDSK AGQDS SOOHD GWEHS TUWRO DLAEG ATDSK MFSQA KOWEG OKESY VDWPC WHDWE ZYPBJ MRSSE FQHVD VSZCW HSHMQ SVEMS SRLOV QORGR SPSEP IFTOZ LDSQC QDRGM PVLLS DIERM WGWRW EJUCV HUEMO XHNUM CZRLL MRESA JMTSU AGYSY YINQF IVCMF OEIRS ESUXE VQQSL SSQAG RIKMG MOATM REJRS HORRE KBOGR EFAHI PPGMG YDEKO FMWAF MCXUA YARIX SWYAM PMSEB SPUFP CSSRG OIVRS SNSRG OIGSS UESXC QRSLD OVDNS AHIQH GQLTO IUMQS HSGXV SHCGZ TVRNL ASTRR EQHSG OWZIQ HUHQB WDMWZ HSDTW DFERS GXCZH NLACQ DRKMC EPIFT OFLOY DOJLA WEOSP EMDCW WOHAF MVSGZ OSPEH QQEPC SDHER DWURI QTAPO HHPGU GRHNZ GASXT JAGIQ AGAAY QDGFS RKOFM CQHPW OOQRP AZWSH SFQAI QTJQJ MVTSE BERMW BSVJU FFSQG ALMGR HMEAF EGAKP SXXDG CIEQT GHSNR MWMQV HSUQB XREST CVDDS YWRKA EAFXH AXXCV DLWZH EPEFF SGDDS PWESR WBOVD DSECT KISPS QHLDA PVHYF QFEQD JQGIQ ALMFH HEVQC MUOJG HMOOW EPVDS WUOSK OJUNS QTWGA GDCLA DYUPM DWRRE SHOKD EKNSP WAIGS TDLHU HEHOF PSMDC GYIQD FJMUM OGJMQ EGEEQ BMQOH AIWDO EMBXR DWMFQ LNZAB EDRWU OIOAN MWIOA KQUYH OKQIH HSLUB SHOKA ZRDSU MGEVB JMBGD SIGSM QCWZR ILAVQ GIQHS YOSVS SZUVH NLMGH HAKEO WVIFA EYHLA ZREWA JPSEE EJFOW RBJQC QDRNM WHHIL MBHRD GOSYP ODTCW GEJAG EVQMQ OTRLG ESIQT JQHIP AVQGJ RLZMF IVOTD SQLMW YUIVT GEDEO PAFOR WEKMG XXAKY OSVMG DSRDS EUZEJ RGEOW VAGMG EVAKP CWRLS SCRLZ SZHIV FDAFF HLSQG TDNUM";

/* -------------------------------------------------------------------- */
/* Substitui no texto txt as letras na string h1 pelas correspondentes
letras de string h2 */

DecifParcialL(txt,h1,h2)={
  local(len,lenh,txth,vt,vh1,vh2,ct);
  txt=LimpaT(txt);
  len=#txt;
  lenh=#h1;
  txth=listcreate(len);
  vt=Vecsmall(txt);vh1=Vecsmall(h1);vh2=Vecsmall(h2);
  for(k=1,len,
      ct=1;
      for(j=1,lenh,if(vt[k]==vh1[j],listput(txth,vh2[j]);ct=0));
      if(ct,listput(txth,45))
      );
  txth=Strchr(Vec(txth));
  return(txth)
  }

/* -------------------------------------------------------------------- */
/* Calculo do indice de coincidencia de um texto */

IndCoinc(txt)={
  local(ct,ctl,len);
  txt=LimpaT(txt);
  len=#txt;
  ct=0;
  for(k=1,26,ctl=CountL(txt,Strchr(64+k));ct=ct+(ctl/len)^2);
  return(ct*1.0)
  }

/* -------------------------------------------------------------------- */
/* Uma implementacao da cifra de Vigenere (txt e chv em maiusculas,
para ja...): a primeira cifra, a segunda decifra... */

VigenereC(txt,chv)={
  local(len,b,vtxt,vchv,criptgr);
  txt=LimpaT(txt);
  len=#txt;
  b=#chv;
  vtxt=Vec(Vecsmall(txt))+vector(len,i,-65);
  vchv=Vec(Vecsmall(chv))+vector(b,i,-65);
  criptgr=listcreate(len);
  for(k=1,len,listput(criptgr,(vtxt[k]+vchv[(k-1)%b+1])%26));
  criptgr=Vec(criptgr); len=#criptgr;
  criptgr=criptgr+vector(len,i,65);
  return(Strchr(criptgr));
  }

VigenereD(txt,chv)={
  local(len,b,vtxt,vchv,criptgr);
  txt=LimpaT(txt);
  len=#txt;
  b=#chv;
  vtxt=Vec(Vecsmall(txt))+vector(len,i,-65);
  vchv=Vec(Vecsmall(chv))+vector(b,i,-65);
  criptgr=listcreate(len);
  for(k=1,len,listput(criptgr,(vtxt[k]-vchv[(k-1)%b+1])%26));
  criptgr=Vec(criptgr); len=#criptgr;
  criptgr=criptgr+vector(len,i,65);
  return(Strchr(criptgr));
  }

/* -------------------------------------------------------------------- */
/* Criptanalise da cifra de Vigenere */

/* A funcao seguinte extrai de um texto o subtexto formado pelas
letras nas posicoes i, i+e, i+2*e, i+3*e, i+4*e, etc... ('i' de
inicial e 'e' de espacamento */

SubText(txt,i,e)={
  local(len,stxt,vt,k);
  txt=LimpaT(txt);
  len=#txt;
  stxt=listcreate(len);
  vt=Vecsmall(txt);
  k=0;
  while(i+k*e<=len,listput(stxt,vt[i+k*e]);k=k+1);
  stxt=Strchr(Vec(stxt));
  return(stxt)
  }

/* Implementacao do teste de Kasiski */

tKasiski(txt,n)={
  local(len,vtxt,bloco,lenb,i,j,k);
  txt=LimpaT(txt);
  len=#txt;
  vtxt=Vec(Vecsmall(txt));i=3;
  while(i<len-6,bloco=listcreate(len);j=i+3;
    while(j<len-3 && 
         vecextract(vtxt,[i-2,i-1,i])<>vecextract(vtxt,[j-2,j-1,j]),
         j=j+1);
      if(j<len-3,
         listput(bloco,vtxt[i-2]);
         listput(bloco,vtxt[i-1]);
         listput(bloco,vtxt[i]);
         k=1;
         while(vtxt[i+k]==vtxt[j+k],listput(bloco,vtxt[i+k]);k=k+1)); 
    bloco=Vec(bloco);lenb=#bloco;
    if(lenb>n,print(Strchr(bloco)," (",i-2,") : ",divisors(j-i)));i=i+lenb+1)
  }

 ICportugues=0.07813849;
/* ICfrances=0.0778 */
/* ICespanhol=0.0775 */
/* ICalemao=0.0762 */
/* ICitaliano=0.0738 */
/* ICingles= 0.0667 (0.065 e tambem citado...) */
/* ICrusso= 0.0529 (o alfabeto russo tem 30 caracteres...) */

/* Valor aproximado do comprimento da chave para um criptograma obtido
com a cifra de Vigenere... */

tFriedman1(cpt)={
  local(len,indc);
  len=#cpt;
  indc=IndCoinc(cpt);
  return((ICportugues-1/26)*len/(indc*(len-1)+ICportugues-len/26))
  }

tFriedman2(cpt)={
  local(indc);
  indc=IndCoinc(cpt);
  return((ICportugues-1/26)/(indc-1/26))
  }

/* -------------------------------------------------------------------- */

/* CRIPTOGRAFIA MODERNA */

/* Exponenciacao modular: calculo eficiente de a^e mod m */

expmod(a,e,m)={
  local(x,y,s,d); x=a; y=1; s=e;
  while(s,d=s%2;s=(s-d)/2;
  if(d,y=(y*x)%m); x=(x*x)%m);
  return(y)}

/* Diffie-Hellman */

/* 
p=nextprime(10^100);
g=znprimroot(p);

x=random(p-2);
y=random(p-2);

a=expmod(g,x,p);
b=expmod(g,y,p);

k1=expmod(a,y,p);
k2=expmod(b,x,p);

print("p=",p,"\ng=",g,"\na=",a,"\nb=",b,"\n",k1,"\n",k2)
*/

/* Cifra RSA */

/* p=nextprime(199991111111111898798792879763765651291137);
q=nextprime(199991111111111898989762876546165462546513); */

RSA(p,q)={
  local(n,c,d);
  n=p*q; 
  ct=0; while(ct!=1,c=random(10^10);ct=gcd(c,(p-1)*(q-1)));
  d=bezout(c,(p-1)*(q-1))[1];
  return(print("n= ",n,"c= ",c," d= ",d))
}

/* Teste de factorizacao de Fermat:
faz lim tentativas para encontrar um factor de n... */

ffermat(n,lim)={
  local(m,z,r,i);
  m=sqrtint(n); if (n-m*m,1,return(m));
  i=0; z=m*m-n;
  while(lim-i,i=i+1;z=z+2*m+1;r=sqrtint(z); 
    if (z-r*r,1,return(m+1-r));m=m+1);
  return(print("nenhum factor foi encontrado"))
}

/* testemunha: 
n=2^s*t... 
dá 1 se 'a' e uma testemunha para 'n' e 0 se nao for */

testemunha(a,n)={
  local(b,i,s,t);
  s=0;t=n-1;while(t%2==0,t=t/2;s=s+1);
  b=expmod(a,t,n);
  if(b==1 | b==n-1,return(0),
      i=0; while(i<s-1,i=i+1;b=(b*b)%n;if(b==n-1,return(0))));
  return(1)
}

/* Teste de primalidade de Miller:
da 0 se for composto e 1 se for primo ou ERH for falsa... */

miller(n)={
  local(w,s,t,a);
  w=min(floor(2*log(n)^2),n-1);
  a=1;
  while(a<w,a=a+1;if(testemunha(a,n),return(0)));
return(1)}

/* -------------------------------------------------------------------- */
/*                          THE END (for now...)                        */
/* -------------------------------------------------------------------- */