I know of two methods for prime decomposition of a given integer:
Method One: We find all prime factors by starting with the smallest prime number.
Method two: We split the number as the product of two integers not necessarily primes and continue splitting each factor into further factors until all factors are primes.
My first question is how can I prove that any of these methods will give the correct prime decomposition? (no full solution is required as a hint is more than enough)
My second question is that what algorithm do computers use for decomposing a very large number into its prime factors?
For very small numbers, trial division is the best. If the number is somewhat larger, the usual procedure is as follows :
Trial division upto some limit, depending on the size of the number, $10^4$ to $10^6$ are typical treash-holds.
Applying a fermat-pseudoprime-test
Elliptic curve method (ECM) if the number is composite to find factors upto $20-40$ digits. More digits is also possible but usually time-consuming.
Number field sieve (The best known general method upto about $120$ digits)
Sometimes, the pollard-rho-method or the p-1-method or the p+1-method finds non-trivial factors.
If the number has a special form, there might exist better methods and the trial division can be made with a larger treash-hold.