--%>

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 : Formulating linear program of a

    A software company has a new product specifically designed for the lumber industry. The VP of marketing has been given a budget of $1,35,00to market the product over the quarter. She has decided that $35,000 of the budget will be spent promoting the product at the nat

  • 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 : Problem on sales and budget XYZ Farm

    XYZ Farm Supply data regarding the store's operations follow: • Sales are budgeted at $480,000 for November, $430,000 for December, and $340,000 for January. • Collections are expected

  • 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 : Properties for polynomial Specify the

    Specify the important properties for the polynomial.

  • Q : Mathematical Method for Engineers The

     The function is clearly undefined at , but despite all of this the function does have a limit as approaches 0. a) Use MATLAB and ezplot to sketch for , and use the zoom on facility to guess the . You need to include you M-file, outp

  • Q : Explain a rigorous theory for Brownian

    Explain a rigorous theory for Brownian motion developed by Wiener Norbert.

  • Q : What is Big-O hierarchy The big-O

    The big-O hierarchy: A few basic facts about the big-O behaviour of some familiar functions are very important. Let p(n) be a polynomial in n (of any degree). Then logbn is O(p(n)) and p(n) is O(an<

  • 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 : Where would we be without stochastic

    Where would we be without stochastic or Ito^ calculus?