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)
“What our children have to fear is not the cars on the highways of tomorrow but our own pleasure in calculating the most elegant parameters of their deaths.”
—J.G. (James Graham)
“... the most important effect of the suffrage is psychological. The permanent consciousness of power for effective action, the knowledge that their own thoughts have an equal chance with those of any other person ... this is what has always rendered the men of a free state so energetic, so acutely intelligent, so powerful.”
—Mary Putnam Jacobi (1842–1906)
“Dylan is to me the perfect symbol of the anti-artist in our society. He is against everything—the last resort of someone who doesn’t really want to change the world.... Dylan’s songs accept the world as it is.”
—Ewan MacColl (1915–1989)