Как искать минимальный п, что 10^п ≡ 1 модам (ая) для данных х

Question

для заданных x, мне нужно вычислить минимальную n, который приравнивает верно для формулы 10^n ≡ 1 (mod 9x)

Моего алгоритм прост. Для i = 1 to inf, я петлю, пока не получаю результат. Всегда есть результат, если gcd(10, x) = 1. Между тем, если я не получу результата, я увеличиваю i на 1.

Это очень медленно для больших чисел или чисел с факторизацией больших значений, поэтому я спрашиваю, есть ли другой способ рассчитать его быстрее. Я пробовал с потоками, получая каждый поток следующим 10^i для расчета. Производительность немного лучше, но большие штрихи все еще не заканчиваются.

Answer 1

Я просто попытался пример, он работает менее чем за одну секунду:

public class Main { 

    public static void main(String[] args) { 
     int n = 1; 
     int x = 954661; 
     int v = 10; 
     while (v != 1) { 
      n++; 
      v = (v * 10) % (9*x); 
     } 
     System.out.println(n); 
    } 
} 

При больших значениях x переменные должны быть типа long.

Answer 2

Как вы указали, вы на самом деле пытаетесь получить модуль с 1, который равен 1mod(9x). Это всегда даст вам информацию.

И вам не нужно вычислять эту деталь точно, что может снизить ваши расчеты.

С другой стороны, для 10^n = 1, это всегда будет 0. Так что вы можете точно определить, что вы пытаетесь сделать

Answer 3

Вы можете использовать Fermat's Little Theorem.

Предполагая, что ваш x взаимно простое с 10, справедливо следующее:

10^φ(9x) ≡ 1 (mod 9x) 

Здесь φ является Euler's totient function. Таким образом, вы можете легко вычислить хотя бы один n (не обязательно самый маленький), для которого выполняется ваше уравнение. Чтобы найти наименьший такой n, просто перейдите по списку n 's divisors.

---

Пример: x = 89 (простое число просто для простоты).

9x = 801 
φ(9x) = 6 * (89 - 1) = 528 (easy to calculate for a prime number) 

Список делители 528:

1 
2 
3 
4 
6 
8 
11 
12 
16 
22 
24 
33 
44 
48 
66 
88 
132 
176 
264 
528 

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

10^44 ≡ 1 (mod 801)