拡張真理値アルゴリズムを使用して、大きな素数の2つの積の因数分解プロセスを1つの共通因子で簡単にすることはできますか？

Question

桁数の多い素数の2つの製品がありますので、その要因を見つけるのに十分なコンピューティングパワーがありません。 これらの製品に共通の主な要素が1つあります。 GCDを見つけるための拡張核種アルゴリズムを使用して、分解プロセスを簡素化し、計算上可能にすることはできますか？

Answer 1

もちろんです。第1の「素因数の大きな積」が3 × 7 = 21であり、第2の「素因数の大きな積」が5 × 7 = 35であると仮定すると、21と35のGCDは7であり、プライムファクタの大きな製品。あなたは拡張アルゴリズムを必要としない、単純なGCDで十分です。

しかし、これはあまり有用ではありません。なぜなら、共通の要素を共有する2つの大きなセミプライムがほとんどないからです。