Membandingkan co-bilangan prima

Misalkan kita memiliki dua bilangan yang difaktorkan ke dalam bilangan prianya, direpresentasikan sebagai daftar (p, d), di mana semua p adalah bilangan prima, dan d adalah kekuatan p.

Apakah ada cara untuk membandingkan dua angka seperti itu tanpa mengubahnya menjadi bilangan bulat panjang?

Membandingkan dua angka dapat direduksi menjadi membandingkan dua co-bilangan prima, tetapi kemudian tampaknya keberuntungan habis, dan sepertinya saya perlu melakukan beberapa aritmatika polinomial, yang sama dengan mengubah menjadi bilangan bulat panjang.

Ini pertanyaan yang sangat menarik. Saya tidak dapat melihat cara untuk menggunakan factorisations utama bilangan bulat untuk mempercepat perbandingan wrt <, =,>.

Inilah intuisi saya tentang mengapa harus sulit menghubungkan faktorisasi dengan <, = dan>: faktorisasi utama adalah tentang struktur multiplikasi bilangan bulat, sementara <dan> adalah hal-hal tambahan. Mungkin dengan melihat definisi <dalam aritmetika Peano memperjelas ini: definisi <diberikan oleh (antara lain) klausa berikut.

1. $\forall x.x < x+1$

2. .$\forall xy. x < y \Rightarrow x+1 < y+1$

Yang relevan di sini adalah kasus dasar (1). Diterjemahkan ke dalam factorisation prima, ia mengatakan bahwa Anda perlu tahu sesuatu tentang factorisations dari dan y + 1 dari factorisations dari x dan y . Namun, sejauh yang saya ketahui faktorisasi x dan x +1 pada dasarnya tidak berhubungan.$x+1$$y+1$$x$$y$$x$$x+1$