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)
“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)
“... 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)
“In a symbol there is concealment and yet revelation: here therefore, by silence and by speech acting together, comes a double significance.... In the symbol proper, what we can call a symbol, there is ever, more or less distinctly and directly, some embodiment and revelation of the Infinite; the Infinite is made to blend itself with the Finite, to stand visible, and as it were, attainable there. By symbols, accordingly, is man guided and commanded, made happy, made wretched.”
—Thomas Carlyle (1795–1881)