GCD sepasang produk

Saya memiliki dua angka, yang masing-masing merupakan produk dari sejumlah besar angka yang lebih kecil yang saya tahu. Saya ingin mencari GCD (Pembagi umum terbesar) dari dua angka ini. Apakah ada cara saya dapat memanfaatkan faktorisasi parsial yang saya harus mempercepat prosesnya?

Secara khusus, setiap angka yang lebih besar adalah produk $2^{15}$ angka yang lebih kecil, masing-masing sesuai urutan $2^{4000}$. Saya tidak tahu apa-apa tentang faktorisasi angka yang lebih kecil.

Sunting: Sementara angka input sekitar 120.000.000 bit, GCD adalah sekitar 500.000 bit. Faktor-faktor angka khususnya dalam urutan. Mereka semua bilangan bulat dalam rentang yang berurutan.

Semua algoritme GCD yang saya lihat memanfaatkan angka-angka secara langsung, bukan dalam bentuk sebagian atau apa pun. Apakah ada algoritma yang dapat memasukkan informasi ini untuk mempercepat?

Anda dapat menghitung GCD berpasangan dari faktor-faktor tersebut. Anda harus membagi GCD dari faktor-faktor untuk menghindari menemukan faktor GCD yang sama dua kali:

a[1...m] = [given factors of A]
b[1...n] = [given factors of B]
g = 1
for i from 1 to m do
    c = a[i]
    for j from 1 to n do
        d = gcd(c, b[j])
        g = g * d
        c = a[i] / d
        b[j] = b[j] / d
return g

Sayangnya, saya tidak berpikir bahwa ini tidak terlalu cepat daripada perhitungan GCD dari dua angka A dan B.

Ada masalah serupa yang telah diselesaikan dengan cukup efisien: Asumsikan Anda menggunakan RSA yang semuanya dibangun pada produk dari dua bilangan prima besar, di mana produk tidak dapat diperhitungkan dalam waktu yang wajar. Tetapi jika Anda memiliki dua produk pq dan p'q 'dan p = p' atau q = q 'maka Anda dapat menghitung gcd mereka dan mendapatkan p = p' atau q = q 'dan faktor lainnya sepele. Tentu saja jika p = p 'dan juga q = q' maka ini tidak membantu.

Tidak ada yang membayangkan seseorang menghasilkan satu miliar produk seperti itu dan sedikit ceroboh. Seorang hacker menemukan bahwa beberapa angka identik, jadi p = p 'dan q = q', jadi itu adalah dugaan yang baik bahwa beberapa pasangan memiliki gcd ≠ 1. Dan itu telah terjadi dalam kehidupan nyata dengan router yang enkripsi yang dapat retak sebagai hasilnya.

Maaf, saya tidak punya referensi dan ceritanya agak lama, tetapi Anda harus dapat menemukannya. Beberapa tahun yang lalu, mungkin sekitar enam tahun.