Large Integer Computing - Introduction to Cryptography with Java Applets - page 47

Number the position of each digit:

19276 273

54321 321

First, attempt to divide 1 by 2; if this fails, incorporate another digit. Here we divide 19
by 2, which yields 9. Produce the first value for the quotient:

90.

The number of zeros to add is clear when you note the position of the 9 in the dividend
is 4, and the position of the 2 in the divisor is 3. Thus, we add 4 3 = 1 zero. Now, sub-

tract 90 273 from 19276:

·

19276
-24570
-5294

Now, attempt to divide 2 into 5; this yields 2. Since the 5 is at position 4, and 2 is
still at position 3, we add a zero to get

-20

We now modify the quotient value:

90 + -20 = 70.

Now, subtract 20 273 from 5294; this gives us

·

-5294
--5460
166

Note now that the value remaining is smaller than the divisor 273; thus, we have

quotient = 70, and
remainder = 166.

Here is the whole process written out; the only difference between this and the way we
normally do division is that negative quantities appear in the quotient:

70
-20
90
273 ) 19276
-24570
-5294
--5460
166