Rekonstruksi secret menggunakan ADT point

Latihan membuat instruksi pembelajaran penggunaan ADT Point untuk rekonstruksi secret (polinom derajat 2) dengan implementasi bahasa pemrograman Rust.

Contoh kasus: Tuan Mike membagikan tiga share berupa ADT Point yang merupakan hasil evaluasi polinom derajat dua f(x) = a + b x + c x^2. Tujuan pembelajaran ini adalah memperkenalkan penggunaan ADT Point untuk membaca/manipulasi data titik dan menggunakan sebuah fungsi rekonstruksi (Lagrange / Cramer) sebagai black-box untuk mendapatkan a = f(0) (secret). Pemecahan teori SSS (Shamir Secret Sharing) bukan fokus utama sehingga gunakan saja fungsi rekonstruksi yang tersedia.

Ringkasan Tujuan & Objektif

• Tujuan utama: Mempraktikkan penggunaan ADT Point untuk mewakili share (x,y) dan menghubungkannya dengan fungsi rekonstruksi untuk mengambil secret a.

• Objektif pembelajaran:

  1. Menjelaskan peran ADT Point sebagai struktur data untuk menyimpan share.

  2. Mengimplementasikan operasi dasar Point (konstruktor, getter absis/ordinat, pembacaan interaktif).

  3. Memanggil fungsi rekonstruksi (reconstruct_a) yang mengabstraksi detail Lagrange/Cramer — sehingga siswa bisa fokus pada penggunaan ADT.

  4. Menangani kasus tidak valid (duplikasi x, kesalahan input) dan memahami edge cases numerik.

Prasyarat

• Memahami konsep struct dan metode sederhana di Rust; I/O dasar (stdin).

• Mengetahui bahwa rekonstruksi polinom derajat 2 memerlukan tiga titik (t=3). (Pengetahuan detail Lagrange/Cramer tidak diwajibkan karena kita memperlakukannya sebagai fungsi yang sudah tersedia.)

Pendekatan & Desain

• ADT Point : menampung x: f64 dan y: f64, dengan getter absis() dan ordinat() dan fungsi pembacaan interaktif read_interactive(prompt).

• Fungsi rekonstruksi (reconstruct_a) : fungsi terpisah yang menerima tiga Point dan mengembalikan a sebagai i64. Implementasi di dalamnya memakai Lagrange interpolation pada x=0. Untuk tujuan pembelajaran, anggap fungsi ini sebagai given (black-box); siswa cukup memanggilnya dan memahami input-output-nya.

• Alur program (main) : baca tiga Point via ADT, periksa duplikasi x, panggil reconstruct_a, bulatkan hasil a, cetak.

Implementasi yang mudah dibaca untuk pemula

Simpan dua file: src/point.rs dan src/main.rs. Kode dibuat ringkas dengan komentar singkat.

src/point.rs: ADT Point sederhana

// src/point.rs
// ADT Point: sangat sederhana untuk pemula.
// Menyediakan konstruktor, getter, dan pembacaan interaktif.

use std::io::{self, Write};

#[derive(Debug, Clone, Copy)]
pub struct Point {
    x: f64,
    y: f64,
}

impl Point {
    /// Buat point baru
    pub fn new(x: f64, y: f64) -> Self {
        Point { x, y }
    }

    /// Getter absis (x)
    pub fn absis(&self) -> f64 {
        self.x
    }

    /// Getter ordinat (y)
    pub fn ordinat(&self) -> f64 {
        self.y
    }

    /// Baca satu point interaktif: “Masukkan x y: “
    /// Mengulang jika parsing gagal.
    pub fn read_interactive(prompt: &str) -> Self {
        loop {
            print!(”{}”, prompt);
            let _ = io::stdout().flush();

            let mut line = String::new();
            if io::stdin().read_line(&mut line).is_err() {
                eprintln!(”Gagal membaca. Coba lagi.”);
                continue;
            }

            let mut parts = line.split_whitespace();
            let sx = parts.next();
            let sy = parts.next();

            match (sx, sy) {
                (Some(sx), Some(sy)) => {
                    let px = sx.parse::<f64>();
                    let py = sy.parse::<f64>();
                    match (px, py) {
                        (Ok(x), Ok(y)) => return Point::new(x, y),
                        _ => {
                            eprintln!(”Input harus dua angka, mis. `1 19`”);
                            continue;
                        }
                    }
                }
                _ => {
                    eprintln!(”Masukkan dua angka: x y”);
                }
            }
        }
    }
}

Catatan: fungsi membaca interaktif memudahkan pengguna input manual; untuk pengujian otomatis Anda bisa menulis versi non-interaktif yang membaca dari stdin tanpa prompt.

src/main.rs: Driver & fungsi rekonstruksi (Lagrange)

// src/main.rs
mod point;
use point::Point;

/// Fungsi pembantu: basis Lagrange l_i(0) untuk tiga x, i in {0,1,2}
fn lagrange_basis_at_zero(xs: &[f64; 3], i: usize) -> f64 {
    let mut prod = 1.0_f64;
    for j in 0..3 {
        if j == i { continue; }
        // l_i(0) memiliki bentuk product (-x_j)/(x_i-x_j)
        prod *= -xs[j] / (xs[i] - xs[j]);
    }
    prod
}

/// Fungsi rekonstruksi a = f(0) dari tiga point.
/// Ini adalah bagian “black-box” yang Anda gunakan — detail implementasi
/// (menggunakan Lagrange) disembunyikan di sini sehingga fokus pembelajaran adalah ADT.
fn reconstruct_a(p1: Point, p2: Point, p3: Point) -> f64 {
    let xs = [p1.absis(), p2.absis(), p3.absis()];
    let ys = [p1.ordinat(), p2.ordinat(), p3.ordinat()];

    // Periksa duplikasi absis (x), karena akan membuat denominator nol
    if xs[0] == xs[1] || xs[0] == xs[2] || xs[1] == xs[2] {
        panic!(”Nilai x harus berbeda; duplikasi mendeteksi input tidak valid.”);
    }

    let mut a_val = 0.0_f64;
    for i in 0..3 {
        let li0 = lagrange_basis_at_zero(&xs, i);
        a_val += ys[i] * li0;
    }
    a_val
}

fn main() {
    println!(”Rekonstruksi secret a dari 3 share (x y).”);
    println!(”Contoh polinom: y = 12 + 2x + 5x^2 → shares: (0,12),(1,19),(2,36).”);
    println!(”Masukkan tiga point (x y), satu per baris:”);

    // Baca tiga Point menggunakan ADT Point
    let p1 = Point::read_interactive(”[1] “);
    let p2 = Point::read_interactive(”[2] “);
    let p3 = Point::read_interactive(”[3] “);

    // Panggil fungsi rekonstruksi (black-box)
    let a_float = reconstruct_a(p1, p2, p3);

    // Karena skenario soal menyatakan a bilangan bulat, bulatkan ke integer terdekat
    let a_round = a_float.round();
    let eps = 1e-6_f64;
    if (a_float - a_round).abs() > eps {
        eprintln!(”Peringatan: hasil a = {} tidak dekat integer (ketidakkonsistenan pada input).”, a_float);
    }

    println!(”Hasil rekonstruksi (a): {}”, a_round as i64);
}

Penjelasan ringkas kode:

• Point::read_interactive adalah penggunaan ADT Point — pembaca panggilan program berinteraksi hanya dengan API ADT itu (konstruktor dan getter).

• reconstruct_a memisahkan logika interpolasi sehingga siswa dapat melihat pemanggilan fungsi tanpa harus mengerti semua detailnya. Detail Lagrange dikomentari singkat.

• Rounding & toleransi (eps) disertakan karena kita menggunakan f64.

Catatan pedagogis: mengapa menaruh interpolasi di fungsi terpisah?

• Fokus pembelajaran ADT: siswa bisa berlatih memakai ADT (membuat point, memanggil getter) tanpa tersandung detail numerik yang lebih rumit.

• Modularitas: bagian kompleks (interpolasi) dipisah sehingga bisa diganti nanti (mis. dengan metode lain) tanpa mengubah kode yang memakai ADT.

• Reusability & testing: fungsi reconstruct_a mudah diuji terpisah (unit test).

Kompleksitas Algoritma

• Operasi reconstruct_a untuk t=3 berskala konstan O(1) karena hanya sejumlah operasi tetap (produk + penjumlahan). Dalam kasus general (n titik), Lagrange memerlukan O(n^2) operasi. Untuk pemula cukup tahu bahwa untuk tiga titik ini cepat dan sederhana.

Edge cases yang perlu diajarkan / diuji

1. Duplikasi nilai x (x_i == x_j) — menolak input (panic atau return error). Dalam SSS praktik, pembuat share memastikan x unik.

2. Floating point inaccuracies — setelah rekonstruksi, a mungkin sedikit berbeda dari integer eksak; periksa dengan eps lalu bulatkan.

3. Input non-numerik — pembacaan interaktif meminta ulang; ini memudahkan penggunaan.

4. Shares tidak berasal dari polinom konsisten — program mengeluarkan peringatan jika a tidak dekat integer.

5. Urutan shares — tidak berpengaruh; Lagrange tidak bergantung pada urutan.

Aktivitas & Latihan untuk siswa

1. Ganti reconstruct_a dengan implementasi Cramer (atau eliminasi Gauss) dan bandingkan hasilnya. (Opsional, lanjutan.)

2. Buat versi non-interaktif yang membaca 6 token (x1 y1 x2 y2 x3 y3) dari stdin sehingga cocok untuk testing otomatis.

3. Tambahkan unit test: buat polinom acak a,b,c integer kecil, buat tiga shares, dan pastikan reconstruct_a mengembalikan a.

4. Ubah ADT Point agar field x,y private dan hanya bisa diakses lewat getter (meningkatkan enkapsulasi).

Refleksi dengan clue singkat

• Mengapa ADT berguna? ADT memberikan antarmuka yang jelas (konstruktor + getter) sehingga kode yang memakai data tidak perlu tahu detail representasi.

• Apakah penting mempelajari Lagrange sekarang? Untuk pemula tujuan utama adalah belajar ADT; teknik interpolasi bisa dipelajari terpisah. Oleh karena itu kita sediakan reconstruct_a sebagai fungsi yang dapat dipanggil (given).

• Bagaimana jika shares keliru? Periksa apakah a mendekati integer; jika tidak, kesalahan pada pembuatan share atau data.

Referensi

• Penjelasan dasar Shamir Secret Sharing (SSS) — konsep pembagian secret lewat polinom ber-derajat t-1.

• Contoh soal & latihan: Praktikum Algoritma dan Struktur Data, Institut Teknologi Bandung (sumber soal / contoh msss.c).

• Dokumentasi Rust: f64 dan I/O dasar:

https://doc.rust-lang.org/