--%>

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 : 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 : Probability and Stochastic assignment

    Introduction to Probability and Stochastic Assignment 1: 1. Consider an experiment in which one of three boxes containing microchips is chosen at random and a microchip is randomly selected from the box.

  • Q : Mean and standard deviation of the data

    Below is the amount of rainfall (in cm) every month for the last 3 years in a particular location: 130 172 142 150 144 117 165 182 104 120 190 99 170 205 110 80 196 127 120 175

  • Q : Explain Factorisation by Fermats method

    Factorisation by Fermat's method: This method, dating from 1643, depends on a simple and standard algebraic identity. Fermat's observation is that if we wish to nd two factors of n, it is enough if we can express n as the di fference of two squares.

  • Q : Define Big-O notation Big-O notation :

    Big-O notation: If f(n) and g(n) are functions of a natural number n, we write f(n) is O(g(n)) and we say f is big-O of g if there is a constant C (independent of n) such that f

  • 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 : Abstract Boolean Algebra I. Boolean

    I. Boolean Algebra Define an abstract Boolean Algebra, B,  as follows:  The three operations are:  +   ( x + y addition) ( x y multiplic

  • Q : Examples of groups Examples of groups:

    Examples of groups: We now start to survey a wide range of examples of groups (labelled by (A), (B), (C), . . . ). Most of these come from number theory. In all cases, the group axioms should be checked. This is easy for almost all of the examples, an

  • 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?<