Часть I. Конечные автоматы

Речь пойдет об универсальном способе построения конечных автоматов делимости. Он основывается на двух простых мыслях: число m делится на число n без остатка, тогда и только тогда, когда запись числа m в системе счисления по основанию n оканчивается нулем; когда мы дописываем к записи числа цифру, это равносильно умножению этого числа на основание системы счисления и последующему прибавлению числа, выраженного дописанной цифрой (например, к числу 1001 в двоичной системе счисления [1001₂=9₁₀] мы дописываем цифру 1, это значит что данное число мы умножаем на два и прибавляем 1 [10011₂=9₁₀*2₁₀+1]).

Другими словами, запись числа m в системе счисления по основанию n есть запись в обратном порядке остатков при последовательном делении на n (см. ниже пример перевода числа 384 в систему счисления по основанию 7 и код на python перевода числа m в систему счисления по основанию n):

(384-6)/7=54
(54-5)/7=7
(7-0)/7=1
(1-1)/7=0

Теперь запишем остатки в обратном порядке: 1056₇=384₁₀

Код на python

m=int(input('A number: '))
n=int(input('A numeral system: '))
l=[]
while(m>0):
  l.append(int(m%n))
  m=m-(m%n)
  m=m/n
print(l[::-1])

Но вернемся к конечным автоматам. Для удобства я возьму в качестве примера построение конечного автомата делимости на 13, но алгоритм построения будет аналогичен для любого другого числа. Систему счисления возьмем троичную, но — аналогично — для любой другой системы счисления алгоритм будет тот же.

Итак, для того, чтобы построить конечный автомат делимости нужно:

1. выделить n состояний автомата (в данном случае 13), каждое из которых соответствует остатку от деления на n (от 0 до n-1);
2. для каждого состояния прописать переходы по следующему принципу (допустим, мы прописываем переходы для состояния 5):

   если цифра 0, то (5*основание системы счисления)%n, где в нашем случае 
основание системы счисления равно 3, а n=13. Получается: (5*3)%13=2, то есть 
из состояния 5 по цифре 0 автомат переходит в состояние 2
   если цифра 1, то (5*основание системы счисления+1)%n. Получается: (5*3+1)%13=3
   если цифра 2, то (5*основание системы счисления+2)%n. Получается: (5*3+2)%13=4

Таким образом, будет получен автомат делимости на число n.

Как это работает? Возьмем наугад вот такое число: 20101221₃. Теперь начинаем движение по конечному автомату: состояние 2 -> состояние 6 [2*3+0] -> состояние 6 [(6*3+1)%13] -> состояние 5 [(6*3+0)%13] -> состояние 3 [(5*3+1)%13] -> состояние 11 [3*3+2] -> состояние 9 [(11*3+2)%13] -> состояние 2 [(9*3+1)%13]. Следовательно, остаток числа 20101221₃ от деления на 13₁₀ равен 2.

Часть II. Сразу две делимости

До этого мы строили автоматы делимости на одно число, но аналогично можно создавать автоматы делимости сразу для нескольких чисел. Тогда количество состояний будет равняться произведению чисел, на делимость которых мы рассматриваем.

Для простоты рассмотрим конечный автомат делимости на числа 2 и 3. Он имеет следующие состояния: 00 (число делится и на 2, и на 3), 01 (делится на 2, остаток деления на 3 равен 1), 02 (делится на 2, остаток деления на 3 равен 2), 10 (нечетное и делится на 3), 11 (остатки от деления на 2 и 3 равны по 1), 12 (нечетное, остаток от деления на 3 равен 2). Систему счисления возьмем двоичную.



Строя автомат делимости для двух чисел 2 и 3, мы также неизбежно построили автомат делимости на число 6 (их произведение). Действительно, состояние 00 это состояние 0 автомата делимости на 6; 01 — состояние 4; 02 — 2; 10 — 3; 11 — 1; 12 — 5.

Иными словами, за каждым автоматом делимости полупростого числа стоит автомат делимости его простых множителей. Этот факт я хотел использовать при факторизации чисел.

Часть III. Отважная попытка

Итак, у нас есть число s, которое является произведением двух простых чисел p и q. Так как число s является большим, автомат делимости с s состояниями практически построить невозможно из-за физических ограничений, но мы можем рассуждать, как будто он у нас есть и перемещаться по нему как нам вздумается. Сразу скажу, что решить проблему факторизации мне не удалось. Было несколько разных подходов к «вытаскиванию» из автомата делимости на число s автомат делимости на числа p и q (из части II мы знаем что это «две стороны одной и той же медали»), но я опишу лишь тот, который, похоже, ближе всех подошел к истине.

Для примера возьмем s=15707. Действовать будем в двоичной системе.

Шаг 1. (s-1)/2=7853. Рассуждаем, какое состояние скрыто в состояние 7853 с точки зрения автомата делимости на числа p и q. Нетрудно догадаться, что s-1 соответствует состояние p-1|q-1, а (s-1)/2 — соответствует состояние (p-1)/2|(q-1)/2. Говоря другим языком, 7853%p=(p-1)/2

Шаг 2. (7853-1)/2=3926. Какое же состояние стоит за числом 3926? Первое, что напрашивается на мысль это то, что нужно из предыдущего остатка также вычесть 1 и поделить все на два. ((p-1)/2-1)/2=(p-3)/4. Но не все так просто, выражение (p-3)/4 имеет право на существование только в том случае, если p%4=3. Обратимся к числу s: s%4=3, следовательно у одного из его делителей остаток от деления на 4 равен 3, а у другого — равен 1. Поэтому выражение (p-3)/4 можно считать справедливым, но что тогда произошло с q в состоянии 3926?

Благодаря тому, что мы выбрали двоичную систему счисления, мы можем записать следующее равенство: (q-1)/2=2*x-q+1, где x=3926%q. Решив равенство, получим x=(3q-3)/4. Таким образом, за числом 3926 скрыто состояние (p-3)/4|(3q-3)/4.

Как видите, если бы мы могли двигаться дальше, рано или поздно мы бы пришли к тому состоянию, когда число будет меньше p, и тогда наш остаток на тот момент можно будет приравнять к числу, благодаря чему можно будет легко найти p. Но двигаться дальше (во всяком случае, двигаться детерминировано) мы можем только до тех пор, пока цифра перемещения по автомату не равна 0 (см. шаг 3).

Шаг 3. s/2=1963. Чтобы сказать какое состояние скрыто за числом 1963 нужно знать p%8 и q%8.
s%8=3, а это значит что p%8=3 и q%8=1 или же p%8=7 и q%8=5.

Если мы примем, что p%8=7, то получим остаток (5p-3)/8 [(p-3)/4=2*x-p, где x=1963%p]. 5*7-3 делится на 8, следовательно предположение может быть верным. Тогда как если p%8=3, то 1963%p=(p-3)/8, что тоже может быть верным. Таким образом, каждый встречающийся ноль [шаг (s-0)/2] раздваивает наши предположения.

Но если бы всегда только ноль, данный способ годился бы для чисел Мерсенна. Однако это не так, так как единицы порой тоже рождают неопределенность.

Итог

Полезно может быть использовано то, что содержится в первых двух частях.

Автор: Руслан Фаткуллин