Bagaimana komputer dapat menghitung matematika eksponensial tanpa kesalahan melimpah?

Mempelajari beberapa metode enkripsi / dekripsi RSA, saya menemukan artikel ini: Contoh Algoritma RSA

Ini mengharuskan ini untuk mendekripsi pesan ini

Hasil totalnya sangat besar, untuk mesin 64-bit / 32-bit, saya tidak percaya itu bisa menyimpan nilai sebesar itu dalam satu register. Bagaimana cara komputer melakukannya tanpa overflow?

Pertanyaan ini adalah Pertanyaan Pengguna Super Minggu Ini .
Baca entri blog untuk detail lebih lanjut atau berkontribusi pada blog Anda sendiri

Karena operasi modulus integer adalah cincin homomorfisme ( Wikipedia ) dari ℤ -> ℤ / nℤ,

(X * Y) mod N = (X mod N) * (Y mod N) mod N

Anda dapat memverifikasi ini sendiri dengan sedikit aljabar sederhana. (Perhatikan bahwa final moddi sisi kanan muncul karena definisi multiplikasi dalam cincin modular.)

Komputer menggunakan trik ini untuk menghitung eksponensial dalam cincin modular tanpa harus menghitung sejumlah besar digit.

               / 1 I = 0,
               |
(X ^ I) mod N = <(X * (X ^ (I-1) mod N)) mod NI aneh,
               |
               \ (X ^ (I / 2) mod N) ^ 2 mod NI even & I / = 0.

Dalam bentuk algoritmik,

-- compute X^I mod N
function expmod(X, I, N)
    if I is zero
        return 1
    elif I is odd
        return (expmod(X, I-1, N) * X) mod N
    else
        Y <- expmod(X, I/2, N)
        return (Y*Y) mod N
    end if
end function

Anda dapat menggunakan ini untuk menghitung (855^2753) mod 3233hanya dengan register 16-bit, jika Anda mau.

Namun, nilai X dan N di RSA jauh lebih besar, terlalu besar untuk masuk dalam register. Panjang modulus biasanya 1024-4096 bit! Sehingga Anda dapat memiliki komputer melakukan perkalian dengan cara "panjang", cara yang sama kita lakukan perkalian dengan tangan. Hanya alih-alih menggunakan angka 0-9, komputer akan menggunakan "kata-kata" 0-2 ¹⁶ -1 atau sesuatu seperti itu. (Menggunakan hanya 16 bit berarti kita bisa mengalikan dua angka 16 bit dan mendapatkan hasil 32 bit penuh tanpa menggunakan bahasa assembly. Dalam bahasa assembly, biasanya sangat mudah untuk mendapatkan hasil 64 bit penuh, atau untuk komputer 64-bit , hasil 128-bit penuh.)

-- Multiply two bigints by each other
function mul(uint16 X[N], uint16 Y[N]):
    Z <- new array uint16[N*2]
    for I in 1..N
        -- C is the "carry"
        C <- 0
        -- Add Y[1..N] * X[I] to Z
        for J in 1..N
            T <- X[I] * Y[J] + C + Z[I + J - 1]
            Z[I + J - 1] <- T & 0xffff
            C <- T >> 16
        end
        -- Keep adding the "carry"
        for J in (I+N)..(N*2)
            T <- C + Z[J]
            Z[J] <- T & 0xffff
            C <- T >> 16
        end
    end
    return Z
end
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have

Ini akan mengalikan X dengan Y dalam jumlah waktu yang kira-kira sama dengan jumlah kata dalam X dikalikan dengan jumlah kata dalam Y. Ini disebut waktu O (N ² ). Jika Anda melihat algoritme di atas dan membedakannya, itu adalah "perkalian panjang" yang sama dengan yang mereka ajarkan di sekolah. Anda tidak memiliki tabel yang dihafal hingga 10 digit, tetapi Anda masih bisa melipatgandakan 1.926.348 x 8.192.004 jika Anda duduk dan menyelesaikannya.

Perkalian panjang:

    1,234
  x 5,678
---------
    9,872
   86,38
  740,4
6,170
---------
7,006,652

Sebenarnya ada beberapa algoritma yang lebih cepat di sekitar untuk mengalikan ( Wikipedia ), seperti metode cepat Fourier Strassen, dan beberapa metode sederhana yang melakukan penambahan dan pengurangan tambahan tetapi perkalian lebih sedikit, dan akhirnya secara keseluruhan lebih cepat. Perpustakaan numerik seperti GMP mampu memilih algoritma yang berbeda berdasarkan seberapa besar angka-angkanya: Transformasi Fourier hanya yang tercepat untuk angka terbesar, angka yang lebih kecil menggunakan algoritma yang lebih sederhana.

Jawaban sederhananya adalah mereka tidak bisa, tidak sendiri. Memang, jika Anda mengambil konsep mesin x-bit, maka ada jumlah angka yang terbatas yang dapat diwakili oleh jumlah bit yang terbatas, sama seperti ada jumlah angka yang terbatas yang dapat diwakili oleh 2 digit dalam sistem desimal.

Yang sedang berkata, representasi komputer dari angka yang sangat besar adalah komponen besar dari bidang kriptografi. Ada banyak cara untuk mewakili angka yang sangat besar di komputer, masing-masing berbeda seperti yang berikutnya.

Masing-masing metode memiliki kelebihan dan kekurangan yang berbeda, dan sementara saya tidak / tidak bisa mendaftar semua metode di sini, saya akan menyajikan yang sangat sederhana.

Misalkan integer hanya dapat menyimpan nilai dari 0-99. Bagaimana seseorang bisa mewakili angka 100? Ini mungkin tampak tidak mungkin pada awalnya, tetapi itu karena kami hanya mempertimbangkan satu variabel. Jika saya harus integer disebut unitsdan satu disebut hundreds, aku bisa dengan mudah mewakili 100: hundreds = 1; units = 0;. Aku bisa dengan mudah mewakili jumlah yang lebih besar, seperti 9223: hundreds = 92; units = 23.

Meskipun ini adalah metode yang mudah, orang dapat berpendapat bahwa itu sangat tidak efisien. Seperti kebanyakan algoritme yang mendorong batas-batas apa yang dapat dilakukan komputer, biasanya merupakan tarik-menarik antara kekuatan (mewakili jumlah besar) dan efisiensi (pengambilan cepat / penyimpanan). Seperti yang saya katakan sebelumnya, ada banyak cara untuk mewakili jumlah besar di komputer; cukup temukan metode dan coba saja!

Saya berharap ini menjawab pertanyaan Anda!

Bacaan lebih lanjut:Ini artikel dan ini salah satu mungkin berguna untuk informasi lebih lanjut.

Cara ini dapat dilakukan (ada banyak cara yang lebih cepat melibatkan kuadrat berulang dan sejenisnya) adalah dengan mengalikan, dan setelah setiap perkalian mengambil modulus. Selama modulus kuadrat kurang dari 2 ^ 32 (atau 2 ^ 64) ini tidak akan pernah mengalami overflow.

Dengan cara yang sama Anda bisa.

Saya akan menebak bahwa Anda tidak tahu apa itu 342 * 189. Tapi Anda tahu fakta-fakta berikut:

9 * 2 = 18
9 * 4 = 36
9 * 3 = 27
8 * 2 = 16
8 * 4 = 32
8 * 3 = 24
1 * 2 = 2
1 * 4 = 4
1 * 3 = 3

18 + 360 + 2700 + 160 + 3200 + 24000 + 200 + 4000 + 30000 = 64638

Dengan mengetahui fakta-fakta sederhana ini, dan setelah mempelajari teknik untuk memanipulasinya, Anda dapat melakukan aritmatika yang sebenarnya tidak bisa Anda lakukan.

Dengan cara yang sama, sebuah komputer yang tidak dapat menangani lebih dari 64 bit matematika sekaligus dapat dengan mudah memecah masalah yang lebih besar menjadi potongan-potongan kecil, melakukan potongan-potongan yang lebih kecil, dan menyatukannya kembali untuk membentuk jawaban yang lebih besar, sebelumnya masalah tidak terjawab.

Sejauh menyangkut penambahan dan pengurangan, banyak CPU memiliki "carry bit" yang diatur jika operasi aritmatika telah meluap. Jadi jika suatu hasil akan membutuhkan 8 byte untuk disimpan, dan CPU adalah 32-bit (yang setara 4 byte 8-bit), ia dapat melakukan dua operasi tambahan, pertama pada "kata rendah" dan kemudian pada "kata tinggi" dengan membawa sedikit merawat melimpah. Diperlukan untuk menghapus carry bit terlebih dahulu. Ini adalah salah satu alasan mengapa CPU bit yang lebih tinggi meningkatkan kinerja karena ini tidak harus dilakukan sebanyak itu.

Tentu saja ini dari pengalaman assembler terbatas saya dengan CPU 8-bit. Saya tidak tahu bagaimana carry bit bekerja dengan CPU modern dengan instruksi multiply dan divde. CPU RISC Non-Intel juga dapat berperilaku berbeda.

Saya tidak tahu banyak tentang matematika floating point, tetapi pada dasarnya byte mewakili jumlah tempat yang tetap, tetapi bukan tempat yang spesifik. Itu sebabnya disebut titik "mengambang". Jadi, misalnya, angka 34459234 akan mengkonsumsi ruang memori kira-kira sama dengan 3.4459234, atau 3.4459234E + 20 (itu 3.4459234 x 10 ^ 20).