import java.awt.event.*;
import javax.swing .*;
import java.awt.*;
import java.math.*;
import java.util.*;
import java.io.*;
//genereaza un numar prim cu un numar de cifra dat 

public class Genereaza extends JApplet implements ActionListener
{
	private JTextField S;//probabilitatea ca numarul generat sa nu fie prim este 1/(2^s)
	private JTextField P;//numarul cifrelor
	private JTextArea NPG;//numarul prim generat
	private JButton btnGen;//butonul de start pt algoritmul efectiv de generare
	private JButton btnInit;//butonul care reinitializeaza p si s		
	public Genereaza()//constructorul clasei	
	{
		super();				
		JPanel p=new JPanel();
		
		JPanel p1=new JPanel();
		p1.add(new JLabel("p="));
		P=new JTextField(10);
		p1.add(P);
		p1.add(new JLabel("s="));
		S=new JTextField(10);
		p1.add(S);
		p1.setPreferredSize(new Dimension(150,50));
		p.add(p1);		
		
		JPanel p2=new JPanel();
		btnGen=new JButton("Genereaza");
		btnGen.addActionListener(this);
		btnInit=new JButton("Initializare");
		btnInit.addActionListener(this);
		p2.add(btnGen);
		p2.add(btnInit);
		p2.setPreferredSize(new Dimension(250,50));			
		p.add(p2);
		
		JPanel p3=new JPanel();
		p3.add(new JLabel("Numarul prim generat"));
		NPG=new JTextArea("",3,25);
		JScrollPane jsp=new JScrollPane(NPG);
		p3.add(jsp);		
		p3.setPreferredSize(new Dimension(300,200));
		p.add(p3);
		
		p.setPreferredSize(new Dimension(300,300));			
		getContentPane().add(p);	
		
		initializari();	
	}	
	private void initializari()//metoda de initializare
	{
		P.setText("5");
		S.setText("5");
		NPG.setText("");
	}
	private BigInteger random(BigInteger N)
	//genereaza un numar aleator cuprins intre 1 si N
	{
		String SN=N.toString();
		String SRet="";
		int n=SN.length();
		int i,j;		
		while(((j=(int)(Math.random()*10))==0)||(j>Integer.parseInt(SN.substring(0,1))));
		//prima cifra trebuie sa fie diferita de 0
		//si mai mica sau egala cu prima cifra a lui n		
		SRet=SRet+j;	
		for(i=1;i<n;i++)
		{
			while((j=(int)(Math.random()*10))>Integer.parseInt(SN.substring(i,i+1)));
			SRet=SRet+j;			
		}		
		return new BigInteger(SRet);
	}
	private int[] reprBinara(BigInteger N)
	{
		BigInteger zero=new BigInteger("0");
		BigInteger doi=new BigInteger("2");
		Vector V=new Vector();
		int ret[];
		int n=0;
		while (!N.equals(zero))
		{
			V.add(N.mod(doi));
			N=N.divide(doi);
			n++;
		}
		ret=new int[n];
		Object retObj[]=V.toArray();
		for(n=0;n<retObj.length;n++)
			ret[n]=((BigInteger)retObj[n]).intValue();
		return ret;
	}
	private boolean Test(BigInteger a,BigInteger N)
	/*returneaza adevarat daca a ridicat la puterea
  	  n-1 modulo n este egal cu 1 si fals altfel*/
	{
		
		int b[]=reprBinara(N.subtract(new BigInteger("1")));
		BigInteger d=new BigInteger("1");
		BigInteger x=new BigInteger("1");
		BigInteger unu=new BigInteger("1");		
		int i;
		for(i=b.length-1;i>=0;i--)
		{
			x=new BigInteger(d.toString());
			d=d.pow(2).mod(N);
			if(d.equals(unu)&&(!x.equals(unu))&&(!x.equals(N.subtract(new BigInteger("1")))))
				return true;//caz 1
			if (b[i]==1)
				d=d.multiply(a).mod(N);
		}
		if(!d.equals(unu))
			return true;//caz 2
		return false;
	}
	private String Miller_Rabin(BigInteger N,int s)	
	/*testeaza daca n este prim prin alegerea la intamplare a s numere 
	intre 1 si n-1 care sa fie baza in apelul functiei Test*/
	{
		int i,j;
		BigInteger a=new BigInteger("0");
		String numar=N.toString();
		String numar1="";
		for(j=1;j<s;j++)
		{
			a=random(N.subtract(new BigInteger("1")));
			if (Test(a,N))
				return "compus";//sigur
		}
		return "prim";//aproape sigur
	}
	private String genereaza(int p,int s)//metoda propriuzisa de generare
	throws ArithmeticException
	/*returneaza un numar prim de p cifre cu o probabilitate de 2-s
  	returneaza -1 daca nu reuseste sa genereze un astfel de numar*/
	{
		if(s<=0)
				throw new ArithmeticException("S este mai mic sau egal cu 1");
		if(p<=0)
				throw new ArithmeticException("P este mai mic sau egal cu 1");
		String numar="";
		long i;
		while((i=(int)(Math.random()*10))==0);//prima cifra trebuie sa fie diferita de 0
		numar=numar+i;
		for(i=1;i<p;i++)		
		//generam o cifra aleatoare si o alipim la numar
			numar=numar+(int)(Math.random()*10);
		BigInteger N=new BigInteger(numar);//numere foarte mari
		long LN = 4*numar.length();//ln(n)=ln(10^p)<ln((2^4)^p)=ln(2^4p)=4p
		for(i=0;i<LN;i++)
		{			
			if(Miller_Rabin(N,s)=="prim")
				return N.toString();
			N=N.add(new BigInteger("1"));
			if(N.toString().length()==p+1)
			{
				BigInteger b=new BigInteger("10");
				N=b.pow(p);				
			}
		}
		return "-1";
	}	
	public void actionPerformed(ActionEvent e)//tratarea evenimentelor
	{
		if(e.getSource()==btnInit)
			initializari();else
		if(e.getSource()==btnGen)
			{
				int p,s;
				try
				{
					p=Integer.parseInt(P.getText());
					s=Integer.parseInt(S.getText());
				}
				catch(NumberFormatException NFE)
				{
					JOptionPane.showMessageDialog(this,"P sau S nu sunt numere !!!"
					,"Eroare",JOptionPane.ERROR_MESSAGE);
					return;
				}
				try
				{
					NPG.setText(genereaza(p,s));
					if(NPG.getText().equals("-1"))
						JOptionPane.showMessageDialog(this,"Nu s-a reusit generarea unui astfel de numar"
						,"Eroare",JOptionPane.ERROR_MESSAGE);						
				}
				catch(ArithmeticException AE)
				{
					JOptionPane.showMessageDialog(this,AE.getMessage()
					,"Eroare",JOptionPane.ERROR_MESSAGE);
					return;
				}
			}
	}
}