--%>
Assignment Help - homework help

State Fermat algorithm

The basic Fermat algorithm is as follows:

Assume that n is an odd positive integer. Set c = [√n] (`ceiling of √n '). Then we consider in turn the numbers

c2 - n; (c+1)2 - n; (c+2)2 - n.....

until a perfect square is found. If this occurs at the term (c+k)2 - n, then putting a = c+k we have

a2 - n = (c+k)2 - n = b2;

say, and then n = a2 - b2, as desired.

This process will terminate in the worst case when a = (n+1)/2, since

n = [(n+1)/2]2 - [(n-1)/2]2
 
In particular, the number of steps taken will be at worst

(n+1)/2 - [√n] +1 = O(n)

   Related Questions in Mathematics

  • Q : Linear programming model of a Cabinet

    A cabinet company produces cabinets used in mobile and motor homes. Cabinets produced for motor homes are smaller and made from less expensive materials than those for mobile homes. The home office in Dayton Ohio has just distributed to its individual manufacturing ce

    		•
  • Q : Problem on Nash equilibrium In a

    In a project, employee and boss are working altogether. The employee can be sincere or insincere, and the Boss can either reward or penalize. The employee gets no benefit for being sincere but gets utility for being insincere (30), for getting rewarded (10) and for be

    		•
  • Q : 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

    		•
  • 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 : Theorem-G satis es the right and left

    Let G be a group. (i) G satis es the right and left cancellation laws; that is, if a; b; x ≡ G, then ax = bx and xa = xb each imply that a = b. (ii) If g ≡ G, then (g-1)

    		•
  • Q : Where would we be without stochastic

    Where would we be without stochastic or Ito^ calculus?

    		•
  • Q : Law of iterated expectations for

     Prove the law of iterated expectations for continuous random variables. 2. Prove that the bounds in Chebyshev's theorem cannot be improved upon. I.e., provide a distribution that satisfies the bounds exactly for k ≥1, show that it satisfies the bounds exactly, and draw its PDF. T

    		•
  • Q : How to get calculus homework done from

    How to get calculus homework done from tutor

    		•
  • Q : Explain trading of call options Explain

    Explain trading of call options.

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

    		•