Mamy dwa produkty liczb pierwszych zduża liczba cyfr, więc nie mamy wystarczającej mocy obliczeniowej, aby znaleźć jej czynniki. Produkty mają jeden wspólny czynnik główny. Czy możemy użyć rozszerzonego algorytmu euklidesowego do znalezienia GCD, aby uprościć proces rozkładu i uczynić go obliczeniowym?
Odpowiedzi:
0 dla odpowiedzi № 1Oczywiście. Załóżmy, że pierwszy "duży iloczyn czynników pierwszych" wynosi 3 × 7 = 21, a drugi "duży iloczyn czynników pierwszych" wynosi 5 × 7 = 35. Następnie GCD 21 i 35 wynosi 7, co jest współczynnikiem obu " duże produkty czynników pierwszych. " Nie potrzebujesz nawet rozbudowanego algorytmu, wystarczy prosty GCD.
Ale to nie jest bardzo przydatne, ponieważ rzadko masz dwa duże półpierwsze, które mają wspólny czynnik.