//UKのδ方式の検証
//4403 is written
//080211 初版
//080214 第2版 mod φ(n)

import java.io.*;
import java.math.*;
import java.util.*;

class uk
{
  public static void main(String args[]) throws IOException
  {
    System.out.print("何ビットでやるよ？:");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int x = Integer.parseInt(br.readLine());
    
    Random r = new Random();
    //BigInteger p = new BigInteger(x,5,r);
    BigInteger p = new BigInteger("647");
    System.out.println("素数pとして" + p + "が選択されました");
    //BigInteger q = new BigInteger(x,5,r);
    BigInteger q = new BigInteger("691");
    System.out.println("素数qとして" + q + "が選択されました");
    System.out.println();
    p = p.subtract(BigInteger.ONE); q = q.subtract(BigInteger.ONE);
    BigInteger phi_n;
    phi_n = p.multiply(q);
    System.out.println("φ(n)=(p-1)×(q-1)=" + phi_n);
    System.out.println();
    
    System.out.println("δを決定します");
    //BigInteger d1 = new BigInteger(x,r);
    BigInteger d1 = new BigInteger("339");
    BigInteger d2 = d1.add(BigInteger.ONE);
    System.out.println("δとして" + d1 + "がδ+1として"+d2+"が決定されました");
    System.out.println("H(m)を決定します");
    BigInteger hm = new BigInteger(x,r);
    System.out.println("H(m)として" + hm + "が決定されました");
    
    System.out.println();
    System.out.println("では総なめにしたいと思います");
    System.out.println();
    
    BigInteger e;
    BigInteger i = new BigInteger("2");
    BigInteger hb;
    i = i.pow(x);
    for (hb=BigInteger.ONE; hb.compareTo(i)<0; hb=hb.add(BigInteger.ONE)) {
    	e=(d2.multiply(hb)).subtract(d1.multiply(hm)).mod(phi_n);
    	if(e.isProbablePrime(5))
    		System.out.println("素数っぽいe="+e);
	}
  }
}