/****************************  RSA.java  *************************************/

import java.util.Random;

/**  Routinen fuer das public key system */

public class RSA {
    
    static Random r = new Random((long)42);
    
    public static long zufall (long n) {   // wuerfelt Zahl zwischen 2 und n-1
        long w  = (r.nextLong() % (n-2));
        if (w<0) return 2-w ; else return 2+w;
    }
    
    public static long mult (long a, long b, long n) { // liefert a * b mod n
        if (b <= 1)     return (a*b) % n; else
        if (b % 2 == 1) return (((mult(a, b/2, n) * 2) % n) + a) % n; else
                        return  ((mult(a, b/2, n) * 2) % n);
    }
    
    public static long potenz (long x, long e, long n) { // liefert x hoch e mod n
        long ergebnis = 1;
        do {
            if (e % 2 ==1) ergebnis = mult(ergebnis, x, n);
            x = mult(x, x, n);
            e = e / 2;
        } while (e > 0);
        return ergebnis;
    }
  
    public static long invers (long d, long fi) {  // liefert inverses zu d mod fi
        long t,u,v,w,x,y,z;
        t = fi;
        u = d;
        v = 0;
        w = 1;
        do {
            x = t / u;
            y = t % u;
            z = v - x*w;
            t = u;
            u = y;
            v = w;
            w = z;
        } while (u != 1);
        if (z < 0) return fi+z; else return z;
    }
  
    public static long ggt (long a, long b) {// liefert den groes. gemeins. Teiler
        if (b==0) return a; else
                  return ggt(b, a % b);
    }
  
    public static boolean zeuge (long x, long n) { // liefert true, falls x die     
                                                 // Zusammengesetztheit von n
                                                 // dokumentiert
        long u, k, j;

        if (ggt(x,n) != 1) return true; else {
            k = 0;
            u = n-1;
            while (u % 2 == 0) {                 // zunaechst wird n zerlegt
                u = u / 2;                       // in n = 1+u*2**k
                k++;
            }
            x = potenz (x, u, n);
            if (x == 1) return false; else {
                j = 0;
                while ((x != n-1) && (x != 1) && (j < k-1)){
                    x = mult(x,x,n);
                    j++;
                }
                if (x == n-1) return false; else return true;
            }
        }
    }

    public static boolean probprim (long n) { // liefert true wenn n Primzahl
        long x, z;
        z = 0;
        do {
            z++;
            x = zufall(n);
        } while ((!zeuge(x,n)) && (z<50));
        return (z==50);
    }
 
}