'Why some Large number (around 100 digit) can factor out very fast?
I am new to number theory, I am trying to prime factor large numbers in around 100 digit numbers.
like my program factor out a 93 digit number in 30min while a 116 digit number that took computer few days.
however, there is a 104 digit number i work on 13270693758489295980223043261833153409168505210538146384653262578584663296471619841442958585315929292397
the result come out instantly
I wonder why this number able to factor out so fast. what condition it must satisfy to able to factor out very fast and easy.
Solution 1:[1]
The 47-digit factor 15630142427492468388372081926250991439041076399 is smooth and easily found by Pollard's p ? 1 method with B = 2000; the remaining cofactor is prime.
Solution 2:[2]
Some primes have lots of small factors so they get eliminated fast, then our new number is a lot smaller and that gets factored quickly so...
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | user448810 |
| Solution 2 | Anonymous |