В математике существуют разные подходы к делению длинных чисел, потому что деление длинного числа на другое длинное реализуется достаточно сложно. 2 Деление на короткое число (меньше размера разряда), напротив, реализуется очень просто: по очереди делят каждый разряд длинного числа на короткое, сохраняют целую часть, а остаток переносят в предыдущий (младший) разряд. 2

Некоторые подходы к делению длинных чисел:

• Классическая длинная арифметика. 3 Число хранится в виде массива его цифр. 3 Операции над числами в этом виде длинной арифметики производятся с помощью «школьных» алгоритмов сложения, вычитания, умножения, деления столбиком. 3
• Длинная арифметика в факторизованном виде. 3 Идея заключается в том, чтобы хранить не само число, а его факторизацию, то есть степени каждого входящего в него простого. 3 Этот метод значительно экономит память в сравнении с «классическим» подходом и позволяет производить умножение и деление значительно (асимптотически) быстрее. 3
• Длинная арифметика по системе простых модулей. 3 Суть в том, что выбирается некоторая система модулей (обычно небольших, помещающихся в стандартные типы данных), и число хранится в виде вектора из остатков от его деления на каждый из этих модулей. 3