--%>
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 : Budgeted cash disbursements The ABC

    The ABC Company, a merchandising firm, has budgeted its action for December according to the following information: • Sales at $560,000, all for cash. • The invoice cost for goods purc

    		•
  • Q : What is the definition of a group Group

    Group: Let G be a set. When we say that o is a binary operation on G, we mean that o is a function from GxG into G. Informally, o takes pairs of elements of G as input and produces single elements of G as output. Examples are the operations + and x of

    		•
  • Q : Statistics math Detailed explanation of

    Detailed explanation of requirements for Part C-1 The assignment states the following requirement for Part 1, which is due at the end of Week 4: “Choose a topic from your field of study. Keep in mind you will need to collect at least [sic] 3- points of data for this project. Construct the sheet y

    		•
  • Q : Properties of a group How can we say

    How can we say that the pair (G, o) is a group. Explain the properties which proof it.

    		•
  • Q : Research Areas in Medical Mathematical

    Some Research Areas in Medical Mathematical Modelling:1. Modeling and numerical simulations of the nanometric aerosols in the lower portion of the bronchial tree. 2. Multiscale mathematical modeling of

    		•
  • 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 : Maths A cricketer cn throw a ball to a

    A cricketer cn throw a ball to a max horizontl distnce of 100m. If he throws d same ball vertically upwards then the max height upto which he can throw is????

    		•
  • Q : Explain lognormal stochastic

    Explain lognormal stochastic differential equation for evolution of an asset.

    		•
  • Q : Define Well-formed formulas or Wffs

    Wffs (Well-formed formulas): These are defined inductively by the following clauses:    (i) If  P  is an n-ary predicate and  t1, …, tn are terms, then P(t1, …, t

    		•
  • Q : Who firstly discovered mathematical

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

    		•