Calculating The Jacobi Symbol
The above formulas lead to an efficient algorithm for calculating the Jacobi symbol, analogous to the Euclidean algorithm for finding the GCD of two numbers. (This should not be surprising in light of rule 3)).
The "numerator" is reduced modulo the "denominator" using rule 2). Any multiples of 2 are pulled out using rule 4) and calculated using rule 8). The symbol is flipped using rule 6), and the algorithm recurses until the "numerator" is 1 (covered by rule 4)) or 2 (covered by rule 8)), or the "numerator" equals the "denominator" (rule 3)).
Read more about this topic: Jacobi Symbol
Famous quotes containing the words calculating the, calculating, jacobi and/or symbol:
“[The] elderly and timid single gentleman in Paris ... never drove down the Champs Elysees without expecting an accident, and commonly witnessing one; or found himself in the neighborhood of an official without calculating the chances of a bomb. So long as the rates of progress held good, these bombs would double in force and number every ten years.”
—Henry Brooks Adams (1838–1918)
“Because relationships are a primary source of self-esteem for girls and women, daughters need to know they will not lose our love if they speak up for what they want to tell us how they feel about things. . . . Teaching girls to make specific requests, rather than being indirect and agreeable, will help them avoid the pitfalls of having to be manipulative and calculating to get what they want.”
—Jeanne Elium (20th century)
“... spinsterhood [is considered to be] an abnormality of small proportions and small consequence, something like an extra finger or two on the body, presumably of temporary duration, and never of any social significance.”
—Mary Putnam Jacobi (1842–1906)
“The glance is natural magic. The mysterious communication established across a house between two entire strangers, moves all the springs of wonder. The communication by the glance is in the greatest part not subject to the control of the will. It is the bodily symbol of identity with nature. We look into the eyes to know if this other form is another self, and the eyes will not lie, but make a faithful confession what inhabitant is there.”
—Ralph Waldo Emerson (1803–1882)