\documentclass[11pt,a4paper]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setlength{\oddsidemargin}{-0.5cm} \setlength{\textwidth}{ 500pt}
\topmargin = -1cm \headheight = 0cm \headsep = 0cm
%\pagestyle{empty}
\textheight 26cm \textwidth 17.cm


%\usepackage{a4wide}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[isolatin]{inputenc}
\usepackage[portuges]{babel}


\linespread{1.1}
%\textwidth15cm
%\textheight25cm


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\ZZ{{\mathbb{Z}}}
\def\CC{{\mathbb{C}}}
\def\NN{{\mathbb{N}}}
\def\KK{{\mathbb{K}}}
\def\RR{{\mathbb{R}}}
\def\cM{\mathcal{M}}
\def\ben{\begin{enumerate}}
\def\een{\end{enumerate}}
\def\l({\left(}
\def\r){\right)}
\def\lsqbr{\left[}
\def\rsqbr{\right]}
\def\lbr{\left[}
\def\rbr{\right]}
\def\ZZ{{\mathbb{Z}}}
\def\CC{{\mathbb{C}}}
\def\NN{{\mathbb{N}}}
\def\KK{{\mathbb{K}}}
\def\RR{{\mathbb{R}}}
\def\cMmn{\mathcal{M}_{m\times n}}
\def\cMrp{\mathcal{M}_{r\times p}}
\def\cMrn{\mathcal{M}_{r\times n}}
\def\cMm{\mathcal{M}_{m}}
\def\cMn{\mathcal{M}_{n}}
\def\cMp{\mathcal{M}_{p}}
\def\cMq{\mathcal{M}_{q}}
\def\cMk{\mathcal{M}_{k}}
\def\cM{\mathcal{M}}
\def\cLT{\mathcal{LT}}
\def\cLTn{\mathcal{LT}_n}
\def\parR{\left( \RR \right)}
\def\parC{\left( \CC \right)}
\def\parK{\left( \KK \right)}
%\def\epf{\hfill \rule{2mm}{4mm}}
\def\epf{\endproof}
\def\iff{\Leftrightarrow}
\def\imply{\Rightarrow}
\def\beqn{\begin{eqnarray*}}
\def\eeqn{\end{eqnarray*}}
\def\barr{\begin{array}}
\def\earr{\end{array}}
\def\vN{\l(1\r)}
\def\para{\rightarrow}
\def\lin{\langle}
\def\rin{\rangle}

\newtheorem{theorem}{Teorema}[section]
\newtheorem{definition}[theorem]{Defini\c{c}\~{a}o}
\newtheorem{lemma}[theorem]{Lema}
\newtheorem{proposition}[theorem]{Proposi\c{c}\~{a}o}
\newtheorem{corollary}[theorem]{Corol\'{a}rio}
\newtheorem{exemplo}[theorem]{Exemplo}
\newtheorem{obs}[theorem]{Observa\c{c}\~{a}o}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}
\pagestyle{empty}
\noindent
{\sf Universidade do Minho}
\hfill {\sf L.E.M., L.M.C.C. -- 4$^\circ$ ano}

\noindent{\small {\sf Departamento de Matem\'{a}tica}}
\hfill {\sf Mat. (Esp. Ensino), L.C.C. -- 3$^\circ$ ano}


\vskip 0.3cm \centerline{{\Large{\sf Teoria de Números Computacional}}}


\vskip 0.3cm
 \noindent\rule{1.5cm}{0.2mm}
 \raisebox{-0.5ex}[0cm][0cm]{ {\ \small{\sf{folha i}}}} \hrulefill \rule{1.5cm}{0.2mm}
 \raisebox{-0.5ex}[0cm][0cm]{ {\ \small{\sf{$2^\circ$ semestre, 2006/2007}}}} \rule{1.5cm}{0.2mm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ben

\item Introduziram-se os seguintes comandos no \textit{pari/gp}. Repita-os, compare os tempos e interprete os resultados.
\begin{verbatim}
? for (i=1,1000000,i++)
? ##
  ***   last result computed in 265 ms.
? for (i=1,1000000,i+=1)
? ##
  ***   last result computed in 340 ms.
? for (i=1,1000000,i=i+1)
? ##
  ***   last result computed in 413 ms.
\end{verbatim}


\item A cifra \textit{shift} tem como funções de encriptação e decifração, respectivamente, 

$$e_k(x)=x+k \mod n; \, \, \, d_k(y)=y-k\mod n$$
onde $n$ indica a cardinalidade do alfabeto usado. Para $k=3$ obtemos a cifra de César.

Introduza a função seguinte e interprete-a.
\begin{verbatim}
\\ cifra shift
\\ argumentos: frase sequencia de letras do algabeto, incr o shift

cesar(frase,incr=3)=    /* incr=3 e' o valor tomado para incr por defeito*/

{       local(lista, i, tamanho);

        if(type(incr)!="t_INT",
                error("Opcao invalida")
        );
        lista=Vecsmall(frase);
        tamanho=length(lista);
        print("incremento "incr);
        for(i=1,tamanho,
                lista[i]=((lista[i]-32+incr)%91)+32
        );
        print(Strchr(lista));
        return(Strchr(lista));
}
\end{verbatim}

Use um ciclo  \texttt{while} em vez do ciclo \texttt{for}. 

\item A cifra \textit{afim} tem como funções de encriptação e decifração, respectivamente, 

$$e(x)=ax+k \mod n; \, \, \, d_k(y)=a^{-1}(y-k)\mod n$$
onde $n$ indica a cardinalidade do alfabeto usado e $a$ é tal que $(a,n)=1$. Sabendo que o máximo divisor comum de $a$ e $n$ pode ser calculado à custa de \verb#gcd(a,n)# e que o inverso de $a$ em $\ZZ_n$, caso exista, pode ser calculado via \verb#lift(Mod(1/a,n))#, implemente uma função para a cifra \textit{afim}.

\item A \textit{cifra de Vigenère} é uma cifra polialfabética com funções  de encriptação e decifração
$$e_K(x_1, x_2, \dots x_m)=(x_1+k_1,x_2+k_2,\dots x_m+k_m)$$
$$d_K(x_1, x_2, \dots x_m)=(x_1-k_1,x_2-k_2,\dots x_m-k_m)$$
onde $K=(k_1,k_2,\dots,k_m)\in \ZZ_n^m$. Este vector $K$ pode corresponder a uma palavra, Por exemplo, se $A\sim 0,B\sim 1, C\sim 2,\dots$, então se a chave=``BLAISE'' obtemos  $K=(1,11,0,8,18,4)$, $m=6$.  Implemente a \textit{cifra de Vigenère}.

\item A sucessão de Fibonacci está definida recursivamente por $f_1=1,f_2=1, f_n=f_{n-1}+f_{n-2}$, para $n\ge 3$. Construa uma função que calcule os primeiros  $n$ termos da sucessão de Fibonacci.


\item A sucessão de Lucas está definida recursivamente por $L_1=1,L_2=3, L_n=L_{n-1}+L_{n-2}$, para $n\ge 3$. Construa uma função que calcule os primeiros  $n$ termos da sucessão de Lucas.

\item A conjectura dos primos gémeos afirma que existe uma infinidade de pares de números primos $p$ e $p+2$. Escreva uma função que encontre os primos gémeos inferiores a um certo argumento.

\item Teste a Conjectura de Goldbach: todo o natural par pode-se escrever como a soma de dois números primos.



\een

\end{document}