Advertisements
Archive | Algoritma RSS feed for this section

Goldreich-Goldwasser Halevi (GGHAlgorithm) Cryptosystem

5 Oct

Salah satu aspek penting dalam kriptografi adalah menjamin kerahasiaan (confidentiality) suatu pesan. Untuk menjamin bahwa suatu pesan hanya dibaca oleh pihak-pihak yang berkepentingan saja, perlu dilakukan proses enkripsi-dekripsi terhadap pesan tersebut. Enkripsi merupakan proses mengubah teks pesan menjadi teks pesan baru yang tidak mudah dikenali lagi makna aslinya (ciphertext). Dekripsi adalah proses menerjemahkan ciphertext menjadi teks pesan awal.

Dalam kriptografi, terdapat beberapa jenis teknik enkripsi-dekripsi yang dapat digunakan. Pada tugas ini, teknik enkripsi-dekripsi yang digunakan adalah block cipher. Dalam block cipher, teks pesan akan dipotong menjadi beberapa block sebesar n karakter. Setiap block yang terbentuk akan dienkrip dengan suatu algoritma tertentu menggunakan key yang telah dibuat. Kemudian untuk setiap block yang telah dienkrip, digabungkan secara terurut menjadi sebuah ciphertext.

Tidak jauh berbeda dengan proses enkripsi, proses dekripsi dalam block cipher juga akan memotong ciphertext ke dalam block dengan ukuran yang sama ketika proses enkripsi. Setiap block didekrip dengan suatu algoritma menggunakan sebuah key. Teks pesan awal akan terbentuk setelah hasil dekripsi dari setiap block digabung.

Class GGHAlgorithm menyediakan method-method untuk menjalankan proses enkripsi-dekripsi GGH cryptosystem (yang disederhanakan). Menggunakan bantuan class LUDecomposition untuk menyelesaikan sistem persamaan pada proses dekripsi.

Pada kesempatan ini, kita akan membahas algoritma Goldreich-Goldwasser Halevi atau GGHAlgorithm. Lihat di bawah ini:

import java.util.Random;

public class GGHAlgorithm {
/* ------------------------
 Class variables
 * ------------------------ */

 /**
 private key dengan dimensi 20 dengan range nilai -200 s/d 200
 Hadamard ratio sekitar 0.8
 */
 private double[][] privateKey = {
 {17, -6, 2, -1, -7, -2, -8, -7, 1, -3, 0, 6, -4, -3, 2, 3, -1, -7, -7, 0},
 {0, -21, 21, -7, 12, -1, -1, 10, -5, -5, 0, 7, 11, -12, -2, 7, -19, 8, -8, 2},
 {0, -13, -26, 0, 11, -25, -5, 22, -27, -5, -25, 16, 13, 12, 2, -17, -15, 5, 14, -8},
 {0, -1, -2, -9, 54, 6, 9, 6, -13, -13, -3, 0, -21, 18, -21, 21, -10, -16, 21, 22},
 {0, 9, 18, 8, 9, -54, 23, 16, -15, -32, 2, 9, 8, 22, 1, 9, -22, 11, 7, 35},
 {0, -4, -8, -28, -4, 24, 32, -6, 8, -4, 4, -7, -9, 4, -7, -1, 22, 9, 17, 10},
 {0, 0, 0, 3, 0, 0, 3, 7, -48, 36, 22, 2, -25, 0, 0, -26, 37, -16, 31, -5},
 {0, 0, 0, 17, 0, 0, 17, -3, -22, 7, 18, 52, -23, 7, -12, 31, -15, 6, -16, 11},
 {0, 0, 0, 1, 0, 0, 1, -3, -34, 19, -11, -1, 2, -6, -14, 4, 19, -31, -63, -23},
 {0, 0, 0, 13, 0, 0, 13, -35, 10, -18, -3, -13, 4, -26, -11, -4, 2, 21, 4, 2},
 {0, 0, 0, -12, 0, 0, -12, 8, 21, 1, -49, 12, 28, -4, 20, 2, 6, -8, 19, 13},
 {0, 0, 0, 12, 0, 0, 12, -18, 15, 45, 33, -12, 18, 1, -10, -15, -7, -8, 4, -25},
 {0, 0, 0, 16, 0, 0, 16, 16, 0, 0, -16, -16, 8, 24, -17, 8, 23, 17, 9, 14},
 {0, 0, 0, 12, 0, 0, 12, 12, 0, 0, -12, -12, -33, -40, 22, 23, -21, 4, 19, -1},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -5, 48, -17, 43, 9, 20, -12, -8},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 48, 4, -12, -6, -30, -12},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 43, 0, 0, 43, -23, 22, 1, -24},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 55, -15, -40, -16},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 62, -62, -28},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 195}
 };

 /* ------------------------
 Constructor
 * ------------------------ */
 public GGHAlgorithm() {

 }

 /** Mengakses privateKey
 @return private key
 */
 public double[][] getPrivateKey() {
 return this.privateKey;
 }

 /** Memberi nilai pada privateKey
 @param privateKey matriks 20x20 yang ingin dijadikan private key
 */
 public void setPrivateKey(double[][] privateKey){
 this.privateKey = privateKey;
 }

 /** Membuat public key
 @param g private key
 @param imax range nilai public key (imax, berarti antara -imax s/d imax, inclusive)
 @param hrat batas atas hadamard ratio untuk public key yang ingin dibuat
 @return public key
 */
 public double[][] generatePublicKey(double[][] g, int imax, double hrat)
 {
 LUDecomposition copyarray = new LUDecomposition();
 double[][] b = copyarray.array2DCopy(g);
 int dim = b.length;
 double[][] v = new double[dim][dim];

 //CONSTRUCT StrassensAlgorithm OBJECT
 StrassensAlgorithm multiply = new StrassensAlgorithm();

 //randomunimodmatrix
 double[][] u = this.generateUnimodularMatrix(dim,imax);

 while(this.hadamardRatio(b) > hrat)
 {
 //B = G*U
 //USING STRASSENS
 b = multiply.strassenMatrixMulti(g,u);

//generate randomunimodmatrix, save to V
 v = this.generateUnimodularMatrix(dim,imax);

 //U = U*V
 //USING STRASSENS
 u = multiply.strassenMatrixMulti(u,v);
 }

 return b;
 }

 /** Mendapatkan public key, menggunakan generatePublicKey untuk membuat public key
 @param privateKey private key
 @return public key
 */
 public double[][] getPublicKey(double[][] privateKey){
 //hadamard ratio of 0.5 is already "bad"
 return this.generatePublicKey(privateKey,200,0.5);
 }

 /** Melakukan proses enkripsi sesuai langkah-langkah pada GGH cryptosystem
 @param blockAscii array yang berisi bagian pesan yang ingin di-enkripsi
 @param publicKey public key
 @return array hasil enkripsi
 */
 public double[] encryptGGH(double[] blockAscii, double[][] publicKey){
 double[] cipherMatrix = new double[blockAscii.length];

 double[] perturbationVector, multMatrix;
 perturbationVector = this.generatePerturbationVector(publicKey.length);
 multMatrix = this.matrixVectorMul(publicKey, blockAscii);

 for(int j = 0; j < multMatrix.length; j++){
 cipherMatrix[j] = multMatrix[j] + perturbationVector[j];
 }

 return cipherMatrix;
 }

/** Melakukan proses dekripsi sesuai langkah-langkah pada GGH cryptosystem
 @param privateKey private key
 @param publicKey public key
 @param cipherText array yang berisi cipher text
 @return array hasil dekripsi
 */
 public double[] decryptGGH(double[][] privateKey, double[][] publicKey, double[] cipherText) {

 //CONSTRUCTING OBJECT FROM LUDecomposition
 LUDecomposition priv = new LUDecomposition(privateKey);

 //SOLVE (privateKey)(cipherLinearCombination) = (cipherText)
 double[] cipherLinearCombination = priv.solveLSE(cipherText);

double[] closestVertex = babaiClosestVertexAlgorithm(
 cipherLinearCombination, privateKey);

//CONSTRUCTING OBJECT FROM LUDecomposition
 LUDecomposition pub = new LUDecomposition(publicKey);

 //SOLVE (publicKey)x = (privateKey*closestVertex)
 return pub.solveLSE(matrixVectorMul(privateKey, closestVertex));
 }

/** Membuat matriks dimensi dimxdim yang diisi dengan integer (random)
 @param imax nilai maksimum elemen matriks
 @param dim dimensi matriks persegi
 @return matriks dimxdim
 */
 public double[][] randomMatrix(int imax, int dim)
 {
 double m[][] = new double[dim][dim];
 Random random = new Random();

for(int i = 0; i < dim; i++) {
 for(int j = 0; j < dim; j++) {
 m[i][j] = (double)(random.nextInt(imax - 1) + 1);
 }
 }

//System.out.println("in randomMatrix");
 //this.printMatrix(m);

return m;
 }

 /** Implementasi proses derangement
 @param n ukuran array (jumlah posisi yang ingin dipermutasi)
 @return array hasil derangement
 */
 public int[] derangement(int n)
 {
 int m[] = new int[n];

for(int i = 0; i < n; i++) {
 m[i] = i;
 }

return this.randperm(m);
 }

 /** Membantu proses derangement, permutasi dimana di hasil akhir tidak ada posisi isi array yg sama dengan posisi awal, e.g 1 != 1'
 @param a array yang ingin di-derangement
 @return array hasil dekripsi
 */
 public int[] randperm(int[] a)
 {
 int m[] = new int[a.length];

for(int i = 0; i < a.length; i++) {
 m[i] = a[i];
 }

Random random = new Random();

for(int i = 0; i < m.length; i++) {
 int rand = random.nextInt(a.length - 1) + 1;

while (rand == i) {
 rand = random.nextInt(a.length - 1) + 1;
 }

int temp = m[i];
 m[i] = m[rand];
 m[rand] = temp;
 }

return m;
 }

/** Membuat perturbation vector
 @param dim ukuran vektor
 @return perturbation vector
 */
 public double[] generatePerturbationVector(int dim) {
 double[] v = new double[dim];

for(int i = 0; i < dim; i++) {
 v[i] = Math.round((Math.random() * 10) - 5);
 }

while(vectorNorm(v) == 0) {
 for(int i = 0; i < dim; i++) {
 v[i] = Math.round((Math.random() * 10) - 5);
 }
 }

 /*
 System.out.println();
 System.out.println("perturbation Vector");
 for(int i = 0; i < dim; i++) {
 System.out.println(v[i]);
 }
 */
 //System.out.println("\nPerturbation Vector");
 //this.printVector(v);
 //System.out.println();
 return v;
 }

 /** Membuat matriks unimodular
 @param dim ukuran matriks, dimxdim
 @param intMax nilai maksimum matriks
 @return matriks unimodular
 */
 public double[][] generateUnimodularMatrix(int dim, int intMax)
 {

 double u[][] = new double[dim][dim];

double A[][] = this.randomMatrix(intMax, dim);
 double Atriangular[][] = new double[dim][dim];

for(int i = 0; i < dim; i++) {
 for(int j = 0; j < dim; j++) {
 if (i>j) {
 Atriangular[i][j] = (double)0;
 }
 else if (i == j) {
 Atriangular[i][j] = (double)1;
 }
 else {
 Atriangular[i][j] = (double)A[i][j];
 }
 }
 }

//System.out.println("in generateUnimodularMatrix, Atriangular:");
 //this.printMatrix(Atriangular);
 //System.out.println();

int p[] = this.derangement(dim);

//System.out.println("in generateUnimodularMatrix, derangement:");
 //this.printVector(p);
 //System.out.println();

for(int i = 0; i < dim; i++) {
 for(int j = 0; j < dim; j++) {
 u[j][i] = Atriangular[j][p[i]];
 }
 }

 //System.out.println("in generateUnimodularMatrix, final matrix:");
 //this.printMatrix(u);

return u;
 }

/** Operasi inner product antara dua vektor
 @param u vektor
 @param v vektor
 @return hasil inner product
 */
 public double innerProduct(double[] u, double[] v) {
 double w = 0;
 for(int i = 0; i < u.length; i++) {
 w += u[i] * v[i];
 }

return w;
 }

/** Perkalian skalar dengan vektor
 @param scalar skalar
 @param v vektor
 @return hasil perkalian skalar dengan vektor
 */
 public double[] scalarVectorMul(double scalar, double[] v) {
 for(int i = 0; i < v.length; i++) {
 v[i] += scalar * v[i];
 }

return v;
 }

/** Penjumlahan antara dua vektor
 @param u vektor
 @param v vektor
 @return vektor hasil penjumlahan
 */
 public double[] vectorAddition(double[] u, double[] v) {
 double[] newVector = new double[u.length];
 for(int i = 0; i < u.length; i++) {
 newVector[i] = u[i] + v[i];
 }

return newVector;
 }

/** Perkalian antara matriks dengan vektor (matriks * vektor = vektor)
 @param a matriks
 @param b vektor
 @return hasil perkalian (vektor)
 */
 public double[] matrixVectorMul(double a[][], double b[]) {
 double c[] = new double[a.length];

for(int i = 0; i < a.length; i++) {
 for(int j = 0; j < b.length; j++) {
 c[i] += a[i][j] * b[j];
 }
 }

return c;
 }

/** Menghitung norm-2 sebuah vektor
 @param v vektor
 @return norm-2 vektor
 */
 public double vectorNorm(double[] v) {
 double norm = 0;

for(int i = 0; i < v.length; i++) {
 norm += Math.pow(v[i], 2);
 }

return Math.sqrt(norm);
 }

/** Meyelesaikan closest vertex problem (CVP) dengan algoritma Babai
 @param w vektor (jadi, solusi CVP adalah vektor terdekat dengan w)
 @param baseVectors matriks yang berisi basis
 @return solusi CVP
 */
 public double[] babaiClosestVertexAlgorithm(double[] w, double[][] baseVectors) {
 double wLinearCombination[] = new double[w.length];
 System.arraycopy(w, 0, wLinearCombination, 0, w.length);

for(int i = 0; i < w.length; i++) {
 wLinearCombination[i] = Math.round(wLinearCombination[i]);
 }

return wLinearCombination;
 }

/** Menghitung hadamard ratio dari key
 @param m matriks/key yang ingin dicari hadamard ratio-nya
 @return hadamard ratio
 */
 public double hadamardRatio(double m[][]) {
 LUDecomposition lu = new LUDecomposition(m);

double detL = Math.abs(lu.computeDeterminant());
 double[] firstVector = new double[m.length];

for(int i = 0; i < firstVector.length; i++) {
 firstVector[i] = m[i][0];
 }

double norms = vectorNorm(firstVector);

for(int i = 1; i < m.length; i++) {
 double baseVector[] = new double[m.length];

for(int j = 0; j < m.length; j++) {
 baseVector[j] = m[j][i];
 }

norms *= vectorNorm(baseVector);
 }
 return Math.pow(detL/norms, (double)1.0/m.length);
 }

/** Mencetak matriks ke output
 @param m matriks
 */
 public static void printMatrix(double m[][]) {
 for(int i = 0; i < m.length; i++) {
 for(int j = 0; j < m[0].length; j++) {
 System.out.print(m[i][j] + " |");
 }
 System.out.println();
 }
 }

 /** Mencetak vektor ke output (dengan isi elemen adalah integer)
 @param m vektor
 */
 public static void printVector(int[] m) {
 for(int i = 0; i < m.length; i++) {
 System.out.print(m[i] + " ");
 System.out.println();
 }
 }

 /** Mencetak vektor ke output (dengan isi elemen adalah double)
 @param m vektor
 */
 public static void printVector(double[] m) {
 for(int i = 0; i < m.length; i++) {
 System.out.print(m[i] + " ");
 System.out.println();
 }
 }
}
Advertisements

Struktur data dan algoritma Tree pada ML (Meta Language)

26 Sep

Konsep struktur data Tree telah dipelajari pada kuliah struktur data dan algoritma. Soal-soal pada latihan tutorial kali ini adalah soal-soal yang relatif pernah dikerjakan secara imperatif. Peserta diharapkan memahami bagaimana algoritma tree direpresentasi dalam pemrograman fungsional. Peserta juga diharapkan dapat membandingkan penyelesaian imperatif dengan fungsional pada setial soal yang diberikan. Tuliskan analisa perbandingan dalam komentar program. Analisa perbandingan dapat meliputi: kompleksitas running time dan alokasi memory, kemudahan pembuatan/perbaikan/modifikasi program, dan kemudahan membaca program. Gunakan sebisa mungkin higher order function pada setiap soal. Bila ada yang kurang jelas pada soal, silahkan tambahkan asumsi anda.

1. Buatlah sebuah fungsi bernama “soal1”. Fungsi tersebut menerima sebuah string, dan menghasilkan list of pair, yang tiap pairnya menyatakan karakter dan jumlah kemunculan karakter tersebut pada string input. Urutan pada pair output tidak penting.

soal1 :  string → (char * int) list

Contoh:

– soal1 “saya makan”

> val it = [(#”s”, 1), (#”a”,4), (#”y”,1), (#”m”,1), (#”k”,1), (#”n”,1)]

(Catatan: soal ini terkait dengan penerapan huffman code untuk kompresi,  harap melanjutkan lagi pengerjaannya hingga sampai encoding dan decoding, tidak perlu  dikumpulkan pada tutorial, tapi sebagai bagian persiapan ujian)

2. Buatlah sebuah fungsi bernama “soal2”. Fungsi tersebut membaca sebuah input dengan struktur data tree dan memeriksa apakah input tree tersebut merupakan binary search tree atau tidak. Struktur data tree didefinisikan dengan:

datatype bst = Leaf | Node of int * bst * bst

soal2 : bst → bool

Contoh:

– val t1 = Node(6, Node(4,Leaf,Leaf),
Node(15, Node(11,Leaf,Leaf), Node(24,Leaf,Leaf)));
– soal2 t1;
> val it = true : bool

3. Buatlah sebuah fungsi bernama “soal3” yang menerima satu argument tree. Fungsi ini akan mencetak isi tree yang diberikan secara inorder. (hint: gunakan perintah “print”);

soal3 : bst → unit

4. Buatlah sebuah fungsi bernama “soal4” yang memiliki dua argumen. Argumen pertama adalah sebuah list bilangan dan argumen kedua adalah sebuah tree. Fungsi ini akan memasukan argumen pertama kedalam tree satu persatu mulai dari elemen pertama pada list, dengan tetap mempertahankan struktur binary search tree namun tidak perlu balance.

soal4 : int list → bst → bst

5. Buatlah sebuah fungsi bernama “soal5”. Fungsi ini serupa dengan “soal4” namun dengan mengimplementasikan AVL Tree. Input tree yang diberikan bila bukan merupakan AVL Tree maka soal5 memberikan output berupa exception “Input bukan AVL Tree”. (hint: gunakan
“raise”)
soal5 : int → bst → bst

JAWABAN:

load "List";
load "Int";

datatype bst = Leaf | Node of int * bst * bst;

val tr = Node (4,
Node (2,
Node (1, Leaf, Leaf),
Node (3, Leaf, Leaf)
),
Node (6,
Node (5, Leaf, Leaf),
Node (7, Leaf, Leaf)
)
);

val ntr = Node (4,
Node (2,
Node (3, Leaf, Leaf),
Node (1, Leaf, Leaf)
),
Node (6,
Node (5, Leaf, Leaf),
Node (7, Leaf, Leaf)
)
);

val soal1 = let
fun calc [] = []
| calc (c::cs)= let
val next = List.filter (fn x => x <> c) cs
in (c,length cs - length next + 1) :: (calc next) end
in calc o explode end;

fun inorder Leaf = []
| inorder (Node (k,l,r)) = inorder l @ [k] @ inorder r;

val soal2 = let
fun sorted [] = true
| sorted [_] = true
| sorted (x1::x2::xs) = x1 <= x2 andalso sorted (x2::xs)
in sorted o inorder end;

val soal3 = (map (print o Int.toString)) o inorder

fun insert (k,Leaf) = Node (k, Leaf, Leaf)
| insert (k, Node (x,l,r))= if k < x
then Node (x, insert (k,l), r)
else Node (x, l, insert (k,r))

exception NotBST;
fun soal4 ls tree = if soal2 tree
then foldl insert tree ls;
else raise NotBST

fun rotateR Leaf = Leaf
| rotateR (Node (k,Leaf,r)) = Node (k,Leaf,r)
| rotateR (Node (k,Node (l,ll,lr),r)) = Node (l,ll,Node (k,lr,r));

fun rotateL Leaf = Leaf
| rotateL (Node (k,l,Leaf)) = Node (k,l,Leaf)
| rotateL (Node (k,l,(Node (r,rl,rr)))) = Node (r,Node (k,l,rl),rr);

fun height Leaf = 0
| height (Node (_,l,r)) = Int.max (height l, height r) + 1

fun balance Leaf = Leaf
| balance (Node (k,l,r)) = if height l > height r
then let
fun rotate' tree = case tree of Leaf => Leaf
| (Node (x,xl,xr)) => if height xr > height xl
then rotateL tree
else tree
val subtree = (k,rotate' l,r)
in rotateR (Node subtree) end
else let
fun rotate' tree = case tree of Leaf => Leaf
| (Node (x,xl,xr)) => if height xl > height xr
then rotateR tree
else tree
val subtree = (k,l,rotate' r)
in rotateL (Node subtree) end;

fun isBalanced Leaf = true
| isBalanced (Node (k,l,r)) = Int.abs (height l - height r) <= 1
andalso isBalanced l
andalso isBalanced r;

fun rebalance Leaf = Leaf
| rebalance (Node (k,l,r)) = let
val tree = Node (k,rebalance l, rebalance r)
in if isBalanced tree
then tree
else balance tree
end;

exception NotAVL;
fun soal5 k tree = if soal2 tree andalso isBalanced tree
then rebalance (insert (k,tree))
else raise NotAVL;

Solusi: Struktur Data dan Algoritma – Sortie si Pengurut Email

3 Jun

Deskripsi

Sortie adalah sebuah program yang akan dikembangkan untuk mengurutkan email seseorang. Sortie digunakan terutama untuk membantu orang-orang yang sibuk supaya terbantu dalam membaca email mereka. Diharapkan dengan menggunakan Sortie, orang-orang dapat lebih mudah dalam membaca email yang mereka anggap lebih penting untuk diproses. Setiap email yang diproses oleh Sortie memiliki nama pengirim, waktu, dan subjek email. Sortie memiliki cara kerja yang cukup fleksibel, karena memiliki fitur untuk mengurutkan email sesuai dengan permintaan dari pengguna Sortie. Cara kerja dari Sortie adalah sebagai berikut.

 Pada suatu saat, seorang pengguna Sortie hanya ingin melihat email yang diterimanya pada hari itu, jadi email yang akan diurutkan adalah email-email pada hari yang sama.
 Pengaturan urutan email dilakukan sesuai dengan permintaan pengguna. Ada tiga (3) mekanisme pengurutan email yang dapat dilakukan:

o Nama pengirim. Email dapat diurutkan berdasarkan nama pengirim yang dapat berupa sebuah String nama ataupun String email. Pengurutan berdasarkan nama pengirim email dilakukan berdasarkan abjad.
o Waktu. Email juga dapat diurutkan berdasarkan waktu ketika email diterima oleh pengguna Sortie.
o Subjek Email. Ketika melakukan pengurutan berdasarkan subjek email, maka pengurutan dilakukan berdasarkan abjad.

 Setiap kali melakukan pengurutan, pengguna dapat memberikan prioritas pengurutan yang diinginkan. Misalnya, apabila pengguna memutuskan untuk mengurutkan berdasarkan [nama pengirim, subjek, waktu], maka apabila ada email dari seorang pengirim yang sama, email akan diurutkan berdasarkan subjek, lalu jam.

Format Masukan

Masukan dibaca dari masukan standar. Masukan terdiri dari 2 bagian. Bagian pertama berisi mengenai keterangan prioritas pengurutan email. Bagian kedua berisi data-data email yang masuk di dalam kotak surat pengguna Sortie.

Bagian pertama terdiri dari satu baris string yang terdiri dari tiga buah kata yaitu “[prioritas] [prioritas] [prioritas]”, dimana prioritas menandakan jenis pengurutan yang ingin dilakukan, dan nilai dari ketiganya berbeda, terdiri atas [pengirim], [waktu], dan [subjek]. String menandakan prioritas urutan email yang diinginkan oleh pengguna Sortie.

Bagian kedua berisi data-data email yang masuk ke dalam inbox pengguna Sortie. Bagian ini terdiri dari beberapa baris informasi data-data email yang masuk. Setiap baris terdiri dari tiga bagian yaitu “[pengirim] [waktu] [subyek]”. Data inilah yang nantinya kemudian akan diolah kembali dan akan diurutkan sesuai keinginan pengguna Sortie.

Keterangan:
Dalam mengerjakan tugas ini, Anda sebagai tim pengembang aplikasi Sortie diminta menggunakan metode pengurutan merge sort untuk mengurutkan masukan email untuk Sortie (Anda diharuskan untuk melakukan implementasi merge sort pada masalah ini!). Merge sort diajukan karena memiliki running time yang tidak eksponensial sehingga resource yang digunakan oleh Sortie tidak akan terlalu besar.

Contoh masukan / input:

pengirim waktu subjek
ido@yahuu.com 11:22 laporan penjualan telor ayam
agung@yahuu.com 20:00 astaga!!!
ido@gahoel.com 11:22 saya mau kasih hadiah
mandala@ngemail.com 09:00 minta uang
adi@chanek.com 10:11 penting
agung@yahuu.com 20:03 tolong bantu saya

Contoh keluaran / output:

adi@chanek.com 10:11 penting
agung@yahuu.com 20:00 astaga!!!
agung@yahuu.com 20:03 tolong bantu saya
ido@gahoel.com 11:22 saya mau kasih hadiah
ido@yahuu.com 11:22 laporan penjualan telor ayam
mandala@ngemail.com 09:00 minta uang
Nah, berikut adalah solusi yang bisa kita buat:
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Comparator;
import java.util.Collections;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

/**
Class SDA11111 merupakan class utama dalam program ini
*/
public class SDA11111 {
 /**
 * Method main bertipe static void merupakan method utama yang dipanggil untuk menjalankan program
 * Method ini akan menghandle exception yang mungkin terjadi melalui throws IOException
 * @param args yang bertipe array of String
 */
 public static void main(String args[]) throws IOException {
 //tuliskan program anda disini
 InputOutput io = new InputOutput(); // Membuat objek baru bertipe InputOutput bernama io
 io.bacaFile(); // Memanggil method baca File() pada objek io
 io.sort(); // Memanggil method sort() pada objek io
 io.cetakFile(); // Memanggil method cetakFile() pada objek io
 }
 //buatlah method tambahan yang diperlukan disini
}

/**
Class InputOutput merupakan class untuk menerima input, mengolah data, dan menghasilkan output
Class ini mengimplementasi Comparator yang akan digunakan untuk membandingkan email-email yang ada
*/
class InputOutput implements Comparator<Email> {
 ArrayList<Email> arr = new ArrayList<Email>();
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 String priority1, priority2, priority3;

 /**
 Method bacaFile() bertipe void digunakan untuk melakukan pembacaan file
 */
 public void bacaFile () {
 StringTokenizer input; // Variabel input bertipe StringTokenizer
 try {
 input = new StringTokenizer(br.readLine(), " ");
 priority1 = input.nextToken();
 priority2 = input.nextToken();
 priority3 = input.nextToken();
 while (br.ready()) {
 input = new StringTokenizer(br.readLine(), " ");
 String sender = input.nextToken();
 String clock = input.nextToken();
 String subject = input.nextToken();
 // Jika token lebih dari 3 bagian, akan ditambahkan di Subjek (sesuai soal)
 while (input.hasMoreTokens()) {
 subject += " ";
 subject += input.nextToken();
 }
 arr.add(new Email(sender, new Clock (clock), subject)); //Menambahkan Email baru ke ArrayList arr
 }
 }
 catch (IOException ioe) {}

 }

 /**
 Method sort() bertipe void dan bersifat public untuk melakukan pemanggilan method mergeSort bertipe private
 */
 public void sort () {
 mergeSort(0, arr.size() - 1); // Memanggil method mergeSort
 }

 /**
 * Method mergeSort
 * @param low
 * @param high
 */
 private void mergeSort (int low, int high) {
 if (low < high) {
 // Get the index of the element which is in the middle
 int middle = (low + high) / 2;
 // Sort the left side of the array
 mergeSort(low, middle);
 // Sort the right side of the array
 mergeSort(middle + 1, high);
 // Combine them both
 merge(low, middle, high);
 }
 }

 /**
 * Method merge
 * @param low
 * @param middle
 * @param high
 */
 private void merge (int low, int middle, int high) {
 ArrayList<Email> help = new ArrayList<Email>(arr.size());
 for(Email item: arr) help.add(item);

int i = low;
 int j = middle + 1;
 int k = low;
 // Copy the smallest values from either the left or the right side back
 // to the original array
 while (i <= middle && j <= high) {
 if (compare((help.get(i)), (help.get(j))) <= 0) {
 arr.set(k, help.get(i));
 i++;
 } else {
 arr.set(k, help.get(j));
 j++;
 }
 k++;
 }

 // Copy the rest of the left side of the array into the target array
 while (i <= middle) {
 arr.set(k, help.get(i));
 k++;
 i++;
 }
 help = null;
 }

 /**
 * Method compare merupakan method yang harus dioverride dari Interface Comparator
 * @param email1 bertipe Email
 * @param email2 bertipe Email
 * @return result bertipe int
 */
 public int compare (Email email1, Email email2){
 int result = 0;
 // Jika prioritas yang diinginkan pengguna berupa pengirim waktu subjek
 if ((priority1.startsWith("p")) && (priority2.startsWith("w")) && (priority3.startsWith ("s"))) {
 result = email1.getSender().compareTo(email2.getSender());
 if (result == 0) {
 result = email1.olahClock(email1.getClock()) - email2.olahClock(email2.getClock());
 if (result == 0) {
 result = email1.getSubject().compareTo(email2.getSubject());
 }
 }
 }
 // Jika prioritas yang diinginkan pengguna berupa pengirim subjek waktu
 else if ((priority1.startsWith("p")) && (priority2.startsWith("s")) && (priority3.startsWith ("w"))) {
 result = email1.getSender().compareTo(email2.getSender());
 if (result == 0) {
 result = email1.getSubject().compareTo(email2.getSubject());
 if (result == 0) {
 result = email1.olahClock(email1.getClock()) - email2.olahClock(email2.getClock());
 }
 }
 }
 // Jika prioritas yang diinginkan pengguna berupa subjek pengirim waktu
 else if ((priority1.startsWith("s")) && (priority2.startsWith("p")) && (priority3.startsWith ("w"))) {
 result = email1.getSubject().compareTo(email2.getSubject());
 if (result == 0) {
 result = email1.getSender().compareTo(email2.getSender());
 if (result == 0) {
 result = email1.olahClock(email1.getClock()) - email2.olahClock(email1.getClock());
 }
 }
 }
 // Jika prioritas yang diinginkan pengguna berupa subjek waktu pengirim
 else if ((priority1.startsWith("s")) && (priority2.startsWith("w")) && (priority3.startsWith ("p"))) {
 result = email1.getSubject().compareTo(email2.getSubject());
 if (result == 0) {
 result = email1.olahClock(email1.getClock()) - email2.olahClock(email2.getClock());
 if (result == 0) {
 result = email1.getSender().compareTo(email2.getSender());
 }
 }
 }
 // Jika prioritas yang diinginkan pengguna berupa waktu pengirim subjek
 else if ((priority1.startsWith("w")) && (priority2.startsWith("p")) && (priority3.startsWith ("s"))) {
 result = email1.olahClock(email1.getClock()) - email2.olahClock(email2.getClock());
 if (result == 0) {
 result = email1.getSender().compareTo(email2.getSender());
 if (result == 0) {
 result = email1.getSubject().compareTo(email2.getSubject());
 }
 }
 }
 // Jika prioritas yang diinginkan pengguna berupa waktu subjek pengirim
 else if ((priority1.startsWith("w")) && (priority2.startsWith("s")) && (priority3.startsWith ("p"))) {
 result = email1.olahClock(email1.getClock()) - email2.olahClock(email2.getClock());
 if (result == 0) {
 result = email1.getSubject().compareTo(email2.getSubject());
 if (result == 0) {
 result = email1.getSender().compareTo(email2.getSender());
 }
 }
 }

 return result;
 }
 /** Method cetakFile() untuk mencetak output */
 public void cetakFile () throws IOException{
 for(Email item: arr) {
 bw.write(""+item);
 bw.newLine();
 }
 bw.flush();
 bw.close();
 }

}

/**
Class Email merupakan class representasi dari objek Email
Class ini memiliki field berupa sender, subject, dan clock.
berturut-turut masing-masing field tersebut menandakan informasi mengenai
pengirim dari email, subject dari email, dan waktu dari email
*/
//notes : lakukan perubahan terhadap class ini jika perlu!!
class Email{
 private String sender;
 private String subject;
 private Clock clock;

 Email(String sender, Clock clock, String subject){
 this.sender = sender;
 this.clock = clock;
 this.subject = subject;
 }

 String getSender(){
 return sender;
 }

 void setSender(String sender){
 this.sender = sender;
 }

 String getSubject(){
 return subject;
 }

 void setSubject(String subject){
 this.subject = subject;
 }

 Clock getClock(){
 return clock;
 }

 void setClock(Clock clock){
 this.clock = clock;
 }

 /** Method olahClock digunakan untuk mengolah waktu dalam bentuk menit agar dapat dibandingkan pada untuk melakukan pengurutan
 * @param clock bertipe Clock
 * @return hasil bertipe int
 */
 int olahClock (Clock clock) {
 int hasil = clock.getHour()*60 + clock.getMinute();
 return hasil;
 }

 public String toString(){
 return sender + " " + clock + " " + subject;
 }
}
/**
Class Clock merupakan class representasi dari objek waktu (Clock)
Class ini memiliki field hour dan minute yang menandakan jam dan menit
*/
//notes : lakukan perubahan terhadap class ini jika perlu!!
class Clock{
 private Integer hour;
 private Integer minute;

 Clock(String time){
 StringTokenizer tok = new StringTokenizer(time, ":");
 hour = Integer.parseInt(tok.nextToken());
 minute = Integer.parseInt(tok.nextToken());
 }

 Integer getHour(){
 return hour;
 }

 void setHour(Integer hour){
 this.hour = hour;
 }

 Integer getMinute(){
 return minute;
 }

 void setMinute(Integer minute){
 this.minute = minute;
 }

 public String toString(){
 String out = "";
 if (hour < 10){
 out += "0" + hour;
 } else {
 out += hour;
 }
 out += ":";
 if (minute < 10) {
 out += "0" + minute;
 } else {
 out += minute;
 }
 return out;
 }
}

Algoritma Fibonaci Menggunakan Bahasa C

2 Jun

Kali ini saya akan membahas Algoritma Fibonaci dan tentunya saya ada source code yang dapat kalian coba menggunakan bahasa C. Udah tidak sabar kan?

Okey, langsung ke materi..

Algoritma Fibonaci merupakan deret hitung dengan penulisan seperti berikut:

1 1 2 3 5 8 13 21 34 55 89 dst…

Ada yang bisa melihat polanya? Kalau bagi saya, deret Fibonaci adalah deret hitung yang dimulai dari 1. Tetapi, sebenarnya sebelum angka 1, ada angka bayangan (itu menurut saya :D), yaitu 0 (nol). Mengapa? Ilustrasi di bawah mungkin bisa menjelaskan.

algoritma fibonaci

Selanjutnya, algoritma fibonaci 4

Mau lebih jelas lagi?
algoritma fibonaci 2

Dan sekarang kita masuk ke dalam koding C untuk membuat deret fibonaci, penasaran bagaimana saya membuatnya? Berikut ini adalah kodingnya..

#include
 using namespace std;
 void fibonaci (int n) {
 int num1 = 0, num2 = 1, temp;
 cout << num2 << " ";
 for (int i = 1; i < n; ++i) {
 //temp untuk menyimpan sementara nilai dari num2
 temp = num2;
 //num2 kemudian ditambahkan
 num2 += num1;
 cout << num2 << " ";
 //nilai dari num2 yang sebelumnya di pindahkan ke num1
 num1 = temp;
 }
 cout << "\n";
 }
 void main () {
 int jumlah;
 cout <> jumlah;
 fibonaci (jumlah);
 }

Berdasarkan kode di atas, nilai yang akan dihasilkan adalah deret Fibonaci sesuai dengan jumlah deret yang diminta oleh user. Misalkan, jika deret yang diminta oleh user adalah 2, maka yang tercetak adalah

1   1

Jika user memasukkan 10, maka outputnya akan seperti berikut ini :

algoritma fibonaci 3

Kriptografi enkripsi-dekripsi algoritma Goldreich-Goldwasser Halevi (GGH) Cryptosystem

24 May

Salah satu aspek penting dalam kriptografi adalah menjamin kerahasiaan (confidentiality) suatu pesan. Untuk menjamin bahwa suatu pesan hanya dibaca oleh pihak-pihak yang berkepentingan saja, perlu dilakukan proses enkripsi-dekripsi terhadap pesan tersebut. Enkripsi merupakan proses mengubah teks pesan menjadi teks pesan baru yang tidak mudah dikenali lagi makna aslinya (ciphertext). Dekripsi adalah proses menerjemahkan ciphertext menjadi teks pesan awal.

Teknik Enkripsi-Dekripsi
Dalam kriptografi, terdapat beberapa jenis teknik enkripsi-dekripsi yang dapat digunakan. Pada tugas ini, teknik enkripsi-dekripsi yang digunakan adalah block cipher. Dalam block cipher, teks pesan akan dipotong menjadi beberapa block sebesar n karakter. Setiap block yang terbentuk akan dienkrip dengan suatu algoritma tertentu menggunakan key yang telah dibuat. Kemudian untuk setiap block yang telah dienkrip, digabungkan secara terurut menjadi sebuah ciphertext.
Tidak jauh berbeda dengan proses enkripsi, proses dekripsi dalam block cipher juga akan memotong ciphertext ke dalam block dengan ukuran yang sama ketika proses enkripsi. Setiap block didekrip dengan suatu algoritma menggunakan sebuah key. Teks pesan awal akan terbentuk setelah hasil dekripsi dari setiap block digabung.

Algoritma Enkripsi-Dekripsi Goldreich-Goldwasser Halevi (GGH) Cryptosystem

Dalam menggunakan algoritma GGH, pesan tidak bisa langsung dienkrip. Pesan yang memiliki tipe string perlu diubah ke dalam nilai ASCII-nya (encoding) dan dienkrip dengan teknik enkripsi block cipher sebesar n, dan  pada kesempatan ini coba dijelaskan untuk n = 20. Begitu juga dengan proses dekripsi, hasil enkripsi didekrip dengan teknik yang sama, block cipher dengan n = 20. Hasil dekripsi merupakan ASCII dari teks pesan awal, sehingga perlu dilakukan proses decoding dari ASCII ke karakter.

Berikut algoritma Goldreich-Goldwasser Halevi (GGH) Cryptosystem dalam Class GGHAlgorithm:


import java.util.Random;

/**

*/
/**
 Class GGHAlgorithm
 Menyediakan method-method untuk menjalankan proses enkripsi-dekripsi
 GGH cryptosystem (yang disederhanakan). Menggunakan bantuan class
 LUDecomposition untuk menyelesaikan sistem persamaan pada proses dekripsi.
 @author Ikhsanul Habibie
*/

public class GGHAlgorithm {
/* ------------------------
 Class variables
 * ------------------------ */

 /**
 private key dengan dimensi 20 dengan range nilai -200 s/d 200
 Hadamard ratio sekitar 0.8
 */
 private double[][] privateKey = {
 {17, -6, 2, -1, -7, -2, -8, -7, 1, -3, 0, 6, -4, -3, 2, 3, -1, -7, -7, 0},
 {0, -21, 21, -7, 12, -1, -1, 10, -5, -5, 0, 7, 11, -12, -2, 7, -19, 8, -8, 2},
 {0, -13, -26, 0, 11, -25, -5, 22, -27, -5, -25, 16, 13, 12, 2, -17, -15, 5, 14, -8},
 {0, -1, -2, -9, 54, 6, 9, 6, -13, -13, -3, 0, -21, 18, -21, 21, -10, -16, 21, 22},
 {0, 9, 18, 8, 9, -54, 23, 16, -15, -32, 2, 9, 8, 22, 1, 9, -22, 11, 7, 35},
 {0, -4, -8, -28, -4, 24, 32, -6, 8, -4, 4, -7, -9, 4, -7, -1, 22, 9, 17, 10},
 {0, 0, 0, 3, 0, 0, 3, 7, -48, 36, 22, 2, -25, 0, 0, -26, 37, -16, 31, -5},
 {0, 0, 0, 17, 0, 0, 17, -3, -22, 7, 18, 52, -23, 7, -12, 31, -15, 6, -16, 11},
 {0, 0, 0, 1, 0, 0, 1, -3, -34, 19, -11, -1, 2, -6, -14, 4, 19, -31, -63, -23},
 {0, 0, 0, 13, 0, 0, 13, -35, 10, -18, -3, -13, 4, -26, -11, -4, 2, 21, 4, 2},
 {0, 0, 0, -12, 0, 0, -12, 8, 21, 1, -49, 12, 28, -4, 20, 2, 6, -8, 19, 13},
 {0, 0, 0, 12, 0, 0, 12, -18, 15, 45, 33, -12, 18, 1, -10, -15, -7, -8, 4, -25},
 {0, 0, 0, 16, 0, 0, 16, 16, 0, 0, -16, -16, 8, 24, -17, 8, 23, 17, 9, 14},
 {0, 0, 0, 12, 0, 0, 12, 12, 0, 0, -12, -12, -33, -40, 22, 23, -21, 4, 19, -1},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -5, 48, -17, 43, 9, 20, -12, -8},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 48, 4, -12, -6, -30, -12},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 43, 0, 0, 43, -23, 22, 1, -24},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 55, -15, -40, -16},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 62, -62, -28},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 195}
 };

 /* ------------------------
 Constructor
 * ------------------------ */
 public GGHAlgorithm() {

 }

 /** Mengakses privateKey
 @return private key
 */
 public double[][] getPrivateKey() {
 return this.privateKey;
 }

 /** Memberi nilai pada privateKey
 @param privateKey matriks 20x20 yang ingin dijadikan private key
 */
 public void setPrivateKey(double[][] privateKey){
 this.privateKey = privateKey;
 }

 /** Membuat <a class="zem_slink" title="Public-key cryptography" href="http://en.wikipedia.org/wiki/Public-key_cryptography" target="_blank" rel="wikipedia">public key</a>
 @param g private key
 @param imax range nilai public key (imax, berarti antara -imax s/d imax, inclusive)
 @param hrat batas atas hadamard ratio untuk public key yang ingin dibuat
 @return public key
 */
 public double[][] generatePublicKey(double[][] g, int imax, double hrat)
 {
 LUDecomposition copyarray = new LUDecomposition();
 double[][] b = copyarray.array2DCopy(g);
 int dim = b.length;
 double[][] v = new double[dim][dim];

 //CONSTRUCT StrassensAlgorithm OBJECT
 StrassensAlgorithm multiply = new StrassensAlgorithm();

 //randomunimodmatrix
 double[][] u = this.generateUnimodularMatrix(dim,imax);

 while(this.hadamardRatio(b) > hrat)
 {
 //B = G*U
 //USING STRASSENS
 b = multiply.strassenMatrixMulti(g,u);

//generate randomunimodmatrix, save to V
 v = this.generateUnimodularMatrix(dim,imax);

 //U = U*V
 //USING STRASSENS
 u = multiply.strassenMatrixMulti(u,v);
 }

 return b;
 }

 /** Mendapatkan public key, menggunakan generatePublicKey untuk membuat public key
 @param privateKey private key
 @return public key
 */
 public double[][] getPublicKey(double[][] privateKey){
 //hadamard ratio of 0.5 is already "bad"
 return this.generatePublicKey(privateKey,200,0.5);
 }

 /** Melakukan proses enkripsi sesuai langkah-langkah pada GGH cryptosystem
 @param blockAscii array yang berisi bagian pesan yang ingin di-enkripsi
 @param publicKey public key
 @return array hasil enkripsi
 */
 public double[] encryptGGH(double[] blockAscii, double[][] publicKey){
 double[] cipherMatrix = new double[blockAscii.length];

 double[] perturbationVector, multMatrix;
 perturbationVector = this.generatePerturbationVector(publicKey.length);
 multMatrix = this.matrixVectorMul(publicKey, blockAscii);

 for(int j = 0; j < multMatrix.length; j++){
 cipherMatrix[j] = multMatrix[j] + perturbationVector[j];
 }

 return cipherMatrix;
 }

/** Melakukan proses dekripsi sesuai langkah-langkah pada GGH cryptosystem
 @param privateKey private key
 @param publicKey public key
 @param cipherText array yang berisi cipher text
 @return array hasil dekripsi
 */
 public double[] decryptGGH(double[][] privateKey, double[][] publicKey, double[] cipherText) {

 //CONSTRUCTING OBJECT FROM LUDecomposition
 LUDecomposition priv = new LUDecomposition(privateKey);

 //SOLVE (privateKey)(cipherLinearCombination) = (cipherText)
 double[] cipherLinearCombination = priv.solveLSE(cipherText);

double[] closestVertex = babaiClosestVertexAlgorithm(
 cipherLinearCombination, privateKey);

//CONSTRUCTING OBJECT FROM LUDecomposition
 LUDecomposition pub = new LUDecomposition(publicKey);

 //SOLVE (publicKey)x = (privateKey*closestVertex)
 return pub.solveLSE(matrixVectorMul(privateKey, closestVertex));
 }

/** Membuat matriks dimensi dimxdim yang diisi dengan integer (random)
 @param imax nilai maksimum elemen matriks
 @param dim dimensi matriks persegi
 @return matriks dimxdim
 */
 public double[][] randomMatrix(int imax, int dim)
 {
 double m[][] = new double[dim][dim];
 Random random = new Random();

for(int i = 0; i < dim; i++) {
 for(int j = 0; j < dim; j++) {
 m[i][j] = (double)(random.nextInt(imax - 1) + 1);
 }
 }

//System.out.println("in randomMatrix");
 //this.printMatrix(m);

return m;
 }

 /** Implementasi proses derangement
 @param n ukuran array (jumlah posisi yang ingin dipermutasi)
 @return array hasil derangement
 */
 public int[] derangement(int n)
 {
 int m[] = new int[n];

for(int i = 0; i < n; i++) {
 m[i] = i;
 }

return this.randperm(m);
 }

 /** Membantu proses derangement, permutasi dimana di hasil akhir tidak ada posisi isi array yg sama dengan posisi awal, e.g 1 != 1'
 @param a array yang ingin di-derangement
 @return array hasil dekripsi
 */
 public int[] randperm(int[] a)
 {
 int m[] = new int[a.length];

for(int i = 0; i < a.length; i++) {
 m[i] = a[i];
 }

Random random = new Random();

for(int i = 0; i < m.length; i++) {
 int rand = random.nextInt(a.length - 1) + 1;

while (rand == i) {
 rand = random.nextInt(a.length - 1) + 1;
 }

int temp = m[i];
 m[i] = m[rand];
 m[rand] = temp;
 }

return m;
 }

/** Membuat perturbation vector
 @param dim ukuran vektor
 @return perturbation vector
 */
 public double[] generatePerturbationVector(int dim) {
 double[] v = new double[dim];

for(int i = 0; i < dim; i++) {
 v[i] = Math.round((Math.random() * 10) - 5);
 }

while(vectorNorm(v) == 0) {
 for(int i = 0; i < dim; i++) {
 v[i] = Math.round((Math.random() * 10) - 5);
 }
 }

 /*
 System.out.println();
 System.out.println("perturbation Vector");
 for(int i = 0; i < dim; i++) {
 System.out.println(v[i]);
 }
 */
 //System.out.println("\nPerturbation Vector");
 //this.printVector(v);
 //System.out.println();
 return v;
 }

 /** Membuat matriks unimodular
 @param dim ukuran matriks, dimxdim
 @param intMax nilai maksimum matriks
 @return matriks unimodular
 */
 public double[][] generateUnimodularMatrix(int dim, int intMax)
 {

 double u[][] = new double[dim][dim];

double A[][] = this.randomMatrix(intMax, dim);
 double Atriangular[][] = new double[dim][dim];

for(int i = 0; i < dim; i++) {
 for(int j = 0; j < dim; j++) {
 if (i>j) {
 Atriangular[i][j] = (double)0;
 }
 else if (i == j) {
 Atriangular[i][j] = (double)1;
 }
 else {
 Atriangular[i][j] = (double)A[i][j];
 }
 }
 }

//System.out.println("in generateUnimodularMatrix, Atriangular:");
 //this.printMatrix(Atriangular);
 //System.out.println();

int p[] = this.derangement(dim);

//System.out.println("in generateUnimodularMatrix, derangement:");
 //this.printVector(p);
 //System.out.println();

for(int i = 0; i < dim; i++) {
 for(int j = 0; j < dim; j++) {
 u[j][i] = Atriangular[j][p[i]];
 }
 }

 //System.out.println("in generateUnimodularMatrix, final matrix:");
 //this.printMatrix(u);

return u;
 }

/** Operasi inner product antara dua vektor
 @param u vektor
 @param v vektor
 @return hasil inner product
 */
 public double innerProduct(double[] u, double[] v) {
 double w = 0;
 for(int i = 0; i < u.length; i++) {
 w += u[i] * v[i];
 }

return w;
 }

/** Perkalian skalar dengan vektor
 @param scalar skalar
 @param v vektor
 @return hasil perkalian skalar dengan vektor
 */
 public double[] scalarVectorMul(double scalar, double[] v) {
 for(int i = 0; i < v.length; i++) {
 v[i] += scalar * v[i];
 }

return v;
 }

/** Penjumlahan antara dua vektor
 @param u vektor
 @param v vektor
 @return vektor hasil penjumlahan
 */
 public double[] vectorAddition(double[] u, double[] v) {
 double[] newVector = new double[u.length];
 for(int i = 0; i < u.length; i++) {
 newVector[i] = u[i] + v[i];
 }

return newVector;
 }

/** Perkalian antara matriks dengan vektor (matriks * vektor = vektor)
 @param a matriks
 @param b vektor
 @return hasil perkalian (vektor)
 */
 public double[] matrixVectorMul(double a[][], double b[]) {
 double c[] = new double[a.length];

for(int i = 0; i < a.length; i++) {
 for(int j = 0; j < b.length; j++) {
 c[i] += a[i][j] * b[j];
 }
 }

return c;
 }

/** Menghitung norm-2 sebuah vektor
 @param v vektor
 @return norm-2 vektor
 */
 public double vectorNorm(double[] v) {
 double norm = 0;

for(int i = 0; i < v.length; i++) {
 norm += Math.pow(v[i], 2);
 }

return Math.sqrt(norm);
 }

/** Meyelesaikan closest vertex problem (CVP) dengan algoritma Babai
 @param w vektor (jadi, solusi CVP adalah vektor terdekat dengan w)
 @param baseVectors matriks yang berisi basis
 @return solusi CVP
 */
 public double[] babaiClosestVertexAlgorithm(double[] w, double[][] baseVectors) {
 double wLinearCombination[] = new double[w.length];
 System.arraycopy(w, 0, wLinearCombination, 0, w.length);

for(int i = 0; i < w.length; i++) {
 wLinearCombination[i] = Math.round(wLinearCombination[i]);
 }

return wLinearCombination;
 }

/** Menghitung hadamard ratio dari key
 @param m matriks/key yang ingin dicari hadamard ratio-nya
 @return hadamard ratio
 */
 public double hadamardRatio(double m[][]) {
 LUDecomposition lu = new LUDecomposition(m);

double detL = Math.abs(lu.computeDeterminant());
 double[] firstVector = new double[m.length];

for(int i = 0; i < firstVector.length; i++) {
 firstVector[i] = m[i][0];
 }

double norms = vectorNorm(firstVector);

for(int i = 1; i < m.length; i++) {
 double baseVector[] = new double[m.length];

for(int j = 0; j < m.length; j++) {
 baseVector[j] = m[j][i];
 }

norms *= vectorNorm(baseVector);
 }
 return Math.pow(detL/norms, (double)1.0/m.length);
 }

/** Mencetak matriks ke output
 @param m matriks
 */
 public static void printMatrix(double m[][]) {
 for(int i = 0; i < m.length; i++) {
 for(int j = 0; j < m[0].length; j++) {
 System.out.print(m[i][j] + " |");
 }
 System.out.println();
 }
 }

 /** Mencetak vektor ke output (dengan isi elemen adalah integer)
 @param m vektor
 */
 public static void printVector(int[] m) {
 for(int i = 0; i < m.length; i++) {
 System.out.print(m[i] + " ");
 System.out.println();
 }
 }

 /** Mencetak vektor ke output (dengan isi elemen adalah double)
 @param m vektor
 */
 public static void printVector(double[] m) {
 for(int i = 0; i < m.length; i++) {
 System.out.print(m[i] + " ");
 System.out.println();
 }
 }
}

&nbsp;

Ada dua jenis key yang akan digunakan Class GGHAlgorithm melakukan proses enkripsi-dekripsi dengan implementasi algoritma GGH. Class ini juga berisi method-method yang dibutuhkan untuk melakukan proses enkripsi-dekripsi, terutama membuat private key dan public key. Berikut, yaitu private key (kunci rahasia) dan public key (kunci publik).

Ukuran dari private key (kunci rahasia) dan public key (kunci publik) adalah salah satu komponen penting dalam sistem kriptografi karena kedua key tersebut mendukung aspek kerahasiaan (confidentiality) dari suatu pesan yang ingin dikirim. Menurut teori, semakin besar ukuran key yang digunakan, maka keamanan sistem semakin meningkat.
Pembentukan public key dalam Goldreich-Goldwasser Halevi (GGH) cryptosystem menggunakan private key sebagai titik awal pembuatannya. Private key dikalikan dengan jenis matriks tertentu sedemikian sehingga terbentuklah public key yang sesuai dengan standar kriteria GGH cryptosystem. Seperti yang sudah dijelaskan sebelumnya, untuk menjamin kualitas keamanan sistem, key yang digunakan harus cukup besar. Berdasarkan sumber [1], ukuran key setidaknya mencapai ratusan. Bayangkan jika Anda menggunakan teknik perkalian matriks standar yang mempunyai kompleksitas Θ(n^3) untuk key yang mempunyai ukuran 400 ke atas, maka teknik perkalian matriks tersebut tidak layak digunakan pada implementasi GGH cryptosystem. Oleh karena itu, perlu adanya metode alternatif untuk mengalikan matriks, salah satunya adalah Strassen’s Algorithm.

Contoh solusi penggunaan Master Theorem atau Metode Master untuk rekurensi

23 May

Teorema 1 (Metode Master) Diberikan suatu rekurensi T (n) = aT (n/b) + f (n) , jika n ≥ n0, untuk suatu n0 elemen N dan T (n) konstan untuk 0 ≤  n < n0. Apabila a ≥ 1, b > 1 keduanya adalah nilai yang konstan dan f (n) adalah fungsi yang asimtotik positif, maka:

master theorem

Gunakan Teorema 1 untuk mencari solusi dari setiap rekurensi berikut dalam notasi . Jika metode master tidak dapat diterapkan, gunakan metode lain yang Anda ketahui. Asumsikan bahwa T (n) konstan untuk n yang cukup kecil.

(a).  T (n) = 3T (n/2) + n.

Solusi T (n) = 3T (n/2) + n menggunakan master theorem kasus 1.

solusi master theorem 1

(b). T (n) = 2T (n/2) + n^3.

Solusi T (n) = 2T (n/2) + n^3 menggunakan master theorem kasus 3.

solusi master theorem 2

(c). T (n) = 7T (n/3) + n^2.

Solusi T (n) =  7T (n/3) + n^2 menggunakan master theorem kasus 3.solusi master theorem 3

(d).  T (n) = 2T (n/2) + n lg n.

Solusi T (n) =  2T (n/2) + n lg n menggunakan master theorem kasus 2.

solusi master theorem 4

(e). T (n) = 4T (n/2) + n^2 √n.

Solusi T (n) = 4T (n/2) + n^2 √n menggunakan master theorem kasus 3.

solusi master theorem 5

(f). T (n) = T (√n) + 1 (petunjuk: substitusikan n = 2^m).

Solusi T (n) = T (√n) + 1 menggunakan master theorem kasus 2.

solusi master theorem 6

 

(g). T (n) = 2T (n – 1) + 1 (asumsikan T (1) = 1).

Kita tidak dapat menggunakan master theorem untuk kasus ini. Dengan evaluasi iteratif, kita memiliki

solusi master theorem 7

 

(h). T (n) = T (n – 1) + lg n (asumsikan T (1) = 1).

Dengan evaluasi iteratif, kita memiliki

solusi master theorem 8-1

Dengan sifat logaritma lg a + lg b = lg ab, diperoleh

solusi master theorem 8-2

Dengan aproksimasi Stirling,  lg (n!) = Θ(n lg n). Akibatnya T (n) = 1 +Θ (n lg n) = Θ(n lg n)

(i). T (n) = T (n – 2) + 2 lg n (asumsikan T (0) = 2).

Karena paritas (genap-ganjil) dari n tidak berpengaruh pada nilai T (n) secara asimtotik, kita boleh mengasumsikan n genap. Dengan evaluasi iteratif, kita memiliki

solusi master theorem 9-1 solusi master theorem 9-2

(j). T (n) = √n T (√n) + 2013 n (petunjuk: misalkan T (n) = nS (n) dengan S (n) adalah fungsi yang asimtotik positif).

Misalkan T (n) = nS (n), maka T (√n) = √n S (√n). Akibatnya rekurensi pada soal setara dengan

solusi master theorem 10-1 solusi master theorem 10-2Demikianlah contoh penggunaan master theorem dalam masalah rekurensi, semoga bermanfaat!

 

Growth function question and solution

23 May

Misalkan f (n) dan g (n) keduanya adalah fungsi bernilai real yang asimtotik positif dengan domain N. Buktikan atau sangkal pernyataan-pernyataan berikut:

1). Jika f (n) = O(g (n)) maka 2^f(n) = O(2^g(n))

Solusi: Karena f (n) dan g (n) keduanya asimtotik positif, maka f (n), g (n) ≥ 0

Pernyataan salah. Karena jika kita pilih f (n) = 2n dan g (n) = n. Jelas bahwa 2n = O(n).
Akan tetapi tinjau bahwa

2^(2n) =(2^2)^n = 4^n ≠ O(2^n) .

Andaikan 4^n = O(2^n), maka kita memiliki

growth function

2). f (n) = θ(f (n/2))

Solusi: Karena f (n) dan g (n) keduanya asimtotik positif, maka f (n), g (n) ≥ 0

Pernyataan salah. Jika f (n) = θ(f (n/2)) maka haruslah f (n) = O(f (n/2)).  Jika kita pilih f (n) = 2^n. Akan dibuktikan bahwa 2^n ≠ O (2^(n/2))


Andaikan 2^n = O (2^(n/2)), maka kita memiliki

growth function2