Algoritmos para Teoria dos Números
Alguns algoritmos para estudar a álgebra da teoria dos números, base do sistema de criptografia RSA (e de outros). Contém crivo de Erastótenes, algoritmo euclidiano estendido, Mersenne e o método de Fermat para ver se um número é primo. Qualquer dúvida ou comentários estamos ouvindo.
Descrição
Alguns algoritmos para estudar a álgebra da teoria dos números, base do sistema de criptografia RSA (e de outros). Contém crivo de Erastótenes, algoritmo euclidiano estendido, Mersenne e o método de Fermat para ver se um número é primo. Qualquer dúvida ou comentários estamos ouvindo.
Versões atualizadas deste script
Changelog: Remove código que causa warnings, muda nome da classe pública
/*Interface Grafica para algoritmos de Álgebra
Humberto Henrique */
import javax.swing.*;
import java.awt.event.*;
import java.awt.*;
public class algcalc2 extends JFrame{
private JLabel label;
private JButton euclid, ferm, erastotenes, mers;
private final int x=300;//dimensões
private final int y=200;//
//configura a interface
public algcalc2(){
super("Algoritmos para Álgebra A");
//painel
Container container=getContentPane();
container.setLayout(new FlowLayout());
//botões
euclid=new JButton("Algoritmo Euclidiano Estendido");
euclid.setToolTipText("Calcula o mdc de dois números inteiros");
container.add(euclid);
ferm=new JButton("Algoritmo de Fermat");
ferm.setToolTipText("Informa se um número é primo");
container.add(ferm);
erastotenes=new JButton("Crivo de Erastótenes");
erastotenes.setToolTipText("Mostra todos os primos menores ou iguais ao número dado");
container.add(erastotenes);
mers=new JButton("Número de Mersenne");
mers.setToolTipText("Calcula o número M(n) dado n");
container.add(mers);
Trata_Euclid tb=new Trata_Euclid();
euclid.addActionListener(tb);
Trata_fermat tf=new Trata_fermat();
ferm.addActionListener(tf);
Trata_crivo tc=new Trata_crivo();
erastotenes.addActionListener(tc);
Trata_mers tm=new Trata_mers();
mers.addActionListener(tm);
//centralizado em 800x600
setCursor(new Cursor(CROSSHAIR_CURSOR));
setLocation(400-x/2,300-y/2);
setSize(x, y);
setResizable(false);
setVisible(true);
}
//executa
public static void main(String[] args){
algcalc2 a=new algcalc2();
a.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
//tratamento de eventos do botao
private class Trata_Euclid implements ActionListener{
public void actionPerformed(ActionEvent event){
try{
int a=Integer.parseInt(JOptionPane.showInputDialog("Digite o primeiro número"));
int b=Integer.parseInt(JOptionPane.showInputDialog("Digite o segundo número"));
euclides e=new euclides(a,b);
JOptionPane.showMessageDialog(null, e);
}
catch(NumberFormatException exc){
JOptionPane.showMessageDialog(null,"Formato de Número Incorreto","Erro",
JOptionPane.ERROR_MESSAGE);
actionPerformed(event);
}
}
}
private class Trata_fermat implements ActionListener{
public void actionPerformed(ActionEvent event){
try{
int a=Integer.parseInt(JOptionPane.showInputDialog("Digite o número"));
if (a==1){
JOptionPane.showMessageDialog(null,"O número 1 não é primo nem composto",
":|",JOptionPane.ERROR_MESSAGE);}
else{
fermat f=new fermat(a);
JOptionPane.showMessageDialog(null, f);
}
}
catch(NumberFormatException exc){
JOptionPane.showMessageDialog(null,"Formato de Número Incorreto","Erro",
JOptionPane.ERROR_MESSAGE);
actionPerformed(event);
}
}
}//fim de Trata_fermat
private class Trata_crivo implements ActionListener{
public void actionPerformed(ActionEvent event){
try{
int a=Integer.parseInt(JOptionPane.showInputDialog("Digite o número"));
crivo c=new crivo(a);
JTextArea area=new JTextArea(c.toString(), 10, 20);
area.append("\nEncontrados "+c.quantidade()+" primos");
area.setEditable(false);
JScrollPane scroll=new JScrollPane(area);
JOptionPane.showMessageDialog(null,scroll,"Primos menores ou iguais a "+a,
JOptionPane.INFORMATION_MESSAGE);
}
catch(NumberFormatException exc){
JOptionPane.showMessageDialog(null,"Formato de Número Incorreto","Erro",
JOptionPane.ERROR_MESSAGE);
actionPerformed(event);
}
}
}//fim de Trata_crivo
private class Trata_mers implements ActionListener{
public void actionPerformed(ActionEvent event){
try{
int n=Integer.parseInt(JOptionPane.showInputDialog("Digite o número"));
if(n<64){
long l=(long) Math.pow(2,n)-1;
JOptionPane.showMessageDialog(null,"O número é: "+l,"Número de Mersenne para "+n,
JOptionPane.INFORMATION_MESSAGE);
}
else
JOptionPane.showMessageDialog(null,"O número não pode ser maior que 63 bits","Erro",
JOptionPane.ERROR_MESSAGE);
}
catch(NumberFormatException exc){
JOptionPane.showMessageDialog(null,"Formato de Número Incorreto","Erro",
JOptionPane.ERROR_MESSAGE);
actionPerformed(event);
}
}
}
}
/***************** Algoritmos para Álgebra********************************/
//Algoritmo de Fermat: Determina um fator de um inteiro
class fermat{
private int n, x;
private boolean primo;
public fermat(int a){
this.n=a;
algoritmo(n);
}
public void configNum(int n){
this.n=n;
algoritmo(n);
}
private void algoritmo(int num){
double aux;
int y;
if(num%2==0){primo=false; x=2;}
else{
x=(int) Math.sqrt(n);
while(true){
x++;
aux=Math.sqrt(x*x-n);
y=(int) aux;
if(x==(n+1)/2){primo=true; break;}
if(aux==y){primo=false; x=x+y; break;}
}
}
}
public String toString(){
if(primo) return "O número é primo";
else return "Fator de "+n+" : "+x;
}
}
/*Crivo de Erastótenes
Programador: Humberto Henrique*/
class crivo{
private int contador=0, n;
private String lista;//lista dos primos ímpares<=n
private byte[] v;
public crivo(int m){
if(m<50000){
if (m%2==1) m++;
n=m;
v=new byte[n/2];
for(int i=0; i<v.length; i++) v[i]=1;
algoritmo(n);
}
else lista="O algoritmo é ineficiente para um número tão grande";
}
private void algoritmo(int n){
lista="2\n";
int P=3, T;
do{
if(v[((P-1)/2)]==0) P=P+2;
else{
T=P*P;
while(T<=n){
v[((T-1)/2)]=0;
T=T+2*P;
}
P=P+2;
}
}while(P*P<=n);
int aux;
v[0]=0;
/* Se p*p>n os números primos são
aqueles da forma 2j+1 para os quais
a j-ésima entrada do vetor é 1 */
for(int j=0; j<v.length; j++){
if (v[j]==1 ){
aux=2*j+1;
lista+=aux+"\n";
contador++;
}
}
contador++;//para contar o 2
}//fim do algoritmo
public String toString(){return lista;}
public int quantidade(){return contador;}
}
//Algoritmo Euclidiano Estendido
class euclides{
private int a,b,alfa,beta,mdc;
public euclides(int n, int m){
a=n;
b=m;
calc(a,b);
}
public String toString(){
return new String("mdc("+a+","+b+")="+alfa+"*"+a+"+"+beta+"*"+b+"="+mdc);
}
private void calc(int a, int b){
//obviedades
if (a==b){alfa=0; beta=1; mdc=a;}
else{
int x0, x1, x2, y0, y1, y2, r, q,maior,menor;
if(a>b){maior=a; menor=b;}
else {maior=b; menor=a;}
x0=1;
x1=0;
y0=0;
y1=1;
r=q=alfa=beta=x2=y2=1;
while(r!=0){
r=maior%menor;
q=maior/menor;
x2=x0-q*x1;
y2=y0-q*y1;
x0=x1; x1=x2; y0=y1; y1=y2;
maior=menor;
menor=r;
}
if(a>b){
alfa=x0;
beta=y0;
}
else{
alfa=y0;
beta=x0;
}
mdc=alfa*a + beta*b;
}
}
}