--%>

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 : Define terms Terms : Terms are defined

    Terms: Terms are defined inductively by the following clauses.               (i) Every individual variable and every individual constant is a term. (Such a term is called atom

  • Q : What is the probability that the film

    T.C.Fox, marketing director for Metro-Goldmine Motion Pictures, believes that the studio's upcoming release has a 60 percent chance of being a hit, a 25 percent chance of being a moderate success, and a 15 percent chance of being a flop. To test the accuracy of his op

  • Q : The mean of the sampling distribution

    1. Caterer determines that 87% of people who sampled the food thought it was delicious. A random sample of 144 out of population of 5000 taken. 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 : Numerical solution of PDE i want you to

    i want you to solve this assignment. this consist of two parts theoretical and coding. the code has to be created by you. no modified or copying code. you have to mention the exact solution and the proportion error. also you have to explain the sketch that you get from the code. these information

  • Q : Problem on Linear equations Anny, Betti

    Anny, Betti and Karol went to their local produce store to bpought some fruit. Anny bought 1 pound of apples and 2 pounds of bananas and paid $2.11.  Betti bought 2 pounds of apples and 1 pound of grapes and paid $4.06.  Karol bought 1 pound of bananas and 2

  • Q : Competitive equilibrium 8. Halloween is

    8. Halloween is an old American tradition. Kids go out dressed in costume and neighbors give them candy when they come to the door. Spike and Cinderella are brother and sister. After a long night collecting candy, they sit down as examine what they have. Spike fi

  • Q : Simulation with Arena An office of

    An office of state license bureau has two types of arrivals. Individuals interested in purchasing new plates are characterized to have inter-arrival times distributed as EXPO(6.8) and service times as TRIA(808, 13.7, 15.2); all times are in minutes. Individuals who want to renew or apply for a new d

  • 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 : How do it? integral e^(-t)*e^(tz) t

    integral e^(-t)*e^(tz) t between 0 and infinity for Re(z)<1

  • Q : Ordinary Differential Equation or ODE

    What is an Ordinary Differential Equation (ODE)?