--%>

Explain Factorisation by trial division

Factorisation by trial division: The essential idea of factorisation by trial division is straightforward. Let n be a positive integer. We know that n is either prime or has a prime divisor less than or equal to √n. Therefore, if we divide n in turn by the primes 2, 3, 5,..., going possibly as far as [√n], we will either encounter a prime factor of n or otherwise be able to infer that n is prime. Repeating this process as often as necessary we will be able to nd all the prime
factors of n.

We can re fine this idea a little. If we fi nd on division by the prime p that p is a factor of n, then we can recommence trial divisions, but now dividing into the integer n/p rather than n. Also, the divisions can start with the prime p rather than restarting with 2, since we know that n, and hence n/p, has no prime factors smaller than p.

Further, we now need only carry out trial divisions by primes up to [√n/p]. Similarly for later steps.

An obvious difficulty with trial division is that we need either to store or to generate the primes up to [√n], and it may be better simply to divide by all the integers from 2 up to [√n], or, for example, by 2 and then all the odd numbers up to [√n].

Other improvements are possible too, but even with a few improvements the trial division algorithm is inefficient , and the algorithm is unsuitable for all but fairly small initial values of n.

Despite this, the trial division algorithm is in practical use. It is often used as a preliminary phase in a factorisation algorithm to nd the `small' prime factors of a number, and the remaining unfactorised part, containing all the `large' prime factors, is left to later phases.

Most numbers have some small prime factors. For example, it is not hard to show that about 88% of positive integers have a prime factor less than 100 and that about 91% have a prime factor less than 1000, and trial division will be good at finding these factors.

On the other hand, most numbers also have large prime factors. It can be shown (though not so easily) that a random positive integer n has a prime factor greater than √n with probability ln 2, or about 69% of the time, and of course if n is large, then trial division will not be of any help in nding such a factor.

   Related Questions in Mathematics

  • Q : Explain lognormal stochastic

    Explain lognormal stochastic differential equation for evolution of an asset.

  • Q : Numerical solution of PDE this

    this assignment contains two parts theoretical and coding the code has to be a new. old code and modified code will appear in the university website .

  • Q : Ordinary Differential Equation or ODE

    What is an Ordinary Differential Equation (ODE)?

  • Q : Who derived the Black–Scholes Equation

    Who derived the Black–Scholes Equation?

  • Q : Formulating linear program of an oil

    An oil company blends two input streams of crude oil products alkylate and catalytic cracked to meet demand for weekly contracts for regular (12,000 barrels) mind grade ( 7,500) and premium ( 4,500 barrels) gasoline’s . each week they can purchase up to 15, 000

  • Q : Profit-loss based problems A leather

    A leather wholesaler supplies leather to shoe companies. The manufacturing quantity requirements of leather differ depending upon the amount of leather ordered by the shoe companies to him. Due to the volatility in orders, he is unable to precisely predict what will b

  • Q : What is limit x tends to 0 log(1+x)/x

    What is limit x tends to 0  log(1+x)/x to the base a?

  • Q : Theorem-Group is unique and has unique

    Let (G; o) be a group. Then the identity of the group is unique and each element of the group has a unique inverse.In this proof, we will argue completely formally, including all the parentheses and all the occurrences of the group operation o. As we proce

  • Q : Statistics Caterer determines that 37%

    Caterer determines that 37% of people who sampled the food thought it was delicious. A random sample of 144 out of population of 5000. The 144 are asked to sample the food. If P-hat is the proportion saying that the food is delicious, what is the mean of the sampling distribution p-hat?

  • Q : Pig Game Using the PairOfDice class

    Using the PairOfDice class design and implement a class to play a game called Pig. In this game the user competes against the computer. On each turn the player rolls a pair of dice and adds up his or her points. Whoever reaches 100 points first, wins. If a player rolls a 1, he or she loses all point