Concept icon
Concept

Computing an inverse by doubling its modular precision

For a scalar unit x in O, start with an inverse y modulo two, found in the residue field. Repeatedly set y_new=y(2-xy), reducing at the desired higher precision. The identity 1-xy_new=(1-xy)^2 shows that an error divisible by 2^q becomes divisible by 2^(2q): each step doubles the number of correct binary digits. Stop at the requested precision p and reduce modulo 2^p. All computations use exact extension-coordinate arithmetic. An element divisible by two has no inverse modulo 2^p, so the initial unit check cannot be skipped.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math