--%>

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 : What is Non-Logical Vocabulary

    Non-Logical Vocabulary: 1. Predicates, called also relation symbols, each with its associated arity. For our needs, we may assume that the number of predicates is finite. But this is not essential. We can have an infinite list of predicates, P

  • Q : Global And Regional Economic Development

    The Pharmatec Group, a supplier of pharmaceutical equipment, systems and services, has its head office in London and primary production facilities in the US. The company also has a successful subsidiary in South Africa, which was established in 1990. Pharmatec South A

  • Q : Problem on budgeted cash collections

    XYZ Company collects 20% of a month's sales in the month of sale, 70% in the month following sale, and 5% in the second month following sale. The remainder is not collectible. Budgeted sales for the subsequent four months are:     

  • Q : Problem on mixed-strategy equilibrium

    Assume three Offices (A, B, & C) in downtown,  simultaneously decide whether to situate in a new Building. The payoff matrix is illustrated below. What is (are) the pure stratgy Nash equilibrium (or equilibria) and mixed-strtegy equilibrium of the game?

  • Q : Who firstly discovered mathematical

    Who firstly discovered mathematical theory for random walks, that rediscovered later by Einstein?

  • Q : Containee problem For queries Q 1 and Q

    For queries Q1 and Q2, we say Q1 is containedin Q2, denoted Q1 C Q2, iff Q1(D) C Q2

  • Q : Formal logic It's a problem set, they

    It's a problem set, they are attached. it's related to Sider's book which is "Logic to philosophy" I attached the book too. I need it on feb22 but feb23 still work

  • Q : Problem on Prime theory Suppose that p

    Suppose that p and q are different primes and n = pq. (i) Express p + q in terms of Ø(n) and n. (ii) Express p - q in terms of p + q and n. (iii) Expl

  • Q : Probability assignments 1. Smith keeps

    1. Smith keeps track of poor work. Often on afternoon it is 5%. If he checks 300 of 7500 instruments what is probability he will find less than 20substandard? 2. Realtors estimate that 23% of homes purchased in 2004 were considered investment properties. If a sample of 800 homes sold in 2

  • Q : Formal logic2 It's a problem set, they

    It's a problem set, they are attached. it's related to Sider's book which is "Logic to philosophy" I attached the book too. I need it on feb22 but feb23 still work