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)
“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)
“... 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)
“The symbol of perpetual youth, the grass-blade, like a long green ribbon, streams from the sod into the summer, checked indeed by the frost, but anon pushing on again, lifting its spear of last year’s hay with the fresh life below. It grows as steadily as the rill oozes out of the ground.... So our human life but dies down to its root, and still puts forth its green blade to eternity.”
—Henry David Thoreau (1817–1862)