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:
“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)
“I know that the right kind of leader for the Labour Party is a kind of desiccated calculating machine.”
—Aneurin Bevan (1897–1960)
“... [the] special relation of women to children, in which the heart of the world has always felt there was something sacred, serves to impress upon women certain tendencies, to endow them with certain virtues ... which will render them of special value in public affairs.”
—Mary Putnam Jacobi (1842–1906)
“Mysticism is the mistake of an accidental and individual symbol for an universal one.”
—Ralph Waldo Emerson (1803–1882)