Ich würde ein Datenformat wählen, welches Zahlen beliebiger Größe handhaben kann. Dann tauschst Du das aus und solltest zufrieden(er) sein.
Hier ist ein Datentyp für 512-bit Integer.
Und
Hier sogar für beliebig große Zahlen (bis 2 Mio Stellen).
Ich fände es interessant, Deine Ergebnisse zu sehen.
Klar ist aber auch: Ein Algorithmus vom Aufwand O(n^3) wird bei großen n immer langsam.