Computing the period of a fraction polynomial in the number of digits

Question

So I have a fraction a/b that is known to be repeating. How do I compute the period of the repeating decimal in polynomial-time in the number of digits of A and B?

Answer 1

In general I think this will be as hard as factoring.

If $B=pq$ is semiprime and 10 is a primitive root modulo both $p$ and $q$ (according to Artin's conjecture there should be infinitely many such primes), then finding the period $k$ of $\frac{1}{pq}$ lets you factor $B$.

In this case the period is the minimum $k$ such that $pq \mid 10^k-1$, namely $ k=\mathrm{lcm}(p-1,q-1)$.

Assume $p>q$, then either:

Cases 1,2: $k=p-1$ or $k=2(p-1)$, check if $k+1$ or $k/2+1$ divides $B$.

Case 3: $k\ge 3(p-1)>p+q-1$. But $k$ divides $(p-1)(q-1)=pq-(p+q-1)$ so $pq\equiv p+q-1 \pmod{k}$. Once we know $p+q=A$ then we can solve for $p,q$ via $p-q = \sqrt{A^2-4B}$.