Factoring semiprimes by searching Fibonacci ranges

24 Views Asked by At

Suppose we have a semiprime $n=pq$.

Question 1: Consider $n$ itself is a Fibonacci number (Fibonacci semiprime). These exist. For e.g., $$F_8 = 21 = 7\cdot 3,\\ F_9 = 34 = 17 \cdot 2\,\\ F_{10} = 55 = 11 \cdot 5,\\ \cdots$$

We can then apply the identity $n = F_{k+2} = F_{k+1} + F_k$ and split $n$ into two Fibonacci numbers. We then get two unequal ranges: $(1, F_{k})$ and $(F_k+1, n-1)$. What can we say about the distribution of the integers $x$ such that $\gcd(x,n) \ne 1$ in these ranges? i.e., Can we determine whether one range is better than the other in terms of the density of the integers $x$ contained in it that share a non-trivial divisor with $n$?

Question 2: Consider $n$ is not a Fibonacci number.

  • An edge case occurs when $n = F_k + 1, k\ge 2$. Again, we can split $F_k$ into $F_{k-1} + F_{k-2}$ using the Fibonacci identity and then review three ranges $(1, F_{k-2}), (F_{k-2}+1, F_{k-1})$ and $(F_{k-1}+1, n-1)$. Which of these ranges has a higher probability of finding an $x$ with $\gcd(x,n) \ne 1$?

  • Let $\zeta_n = \{F_{c_i} : c_i c_{i+1} = 0, c_i\ge 2\}$ be the set of non-consecutive Fibonacci numbers in the Zeckendorf representation of $n$. $|\zeta_n| \ge 2$. Which of the three or more disjoint ranges has the highest probability of finding an $x$ with $\gcd(x,n) \ne 1$?

Example:

$$ 7919 \times 7829 = \\ \sum \left( 2, 8, 21, 55, 144, 987, 4181, 17711, 75025, 2178309, 5702887, 14930352, 39088169\right) $$

Consider the range $(4182, 17711)$.

$$7919, 7829, \\ 15838, 15658$$ lie within this range. This gives probability

$$ \frac{4}{17711-4182+1} = 2.956 \times 10^{-4} $$

Consider the next range $(17712, 75025)$.

$$23757, 23487, \\ 31676, 31316, \\ 39595, 39145, \\ 47514, 46974, \\ 55433, 54803, \\ 63352, 62632, \\ 71271, 70461 $$

lie within this range. This gives probability

$$ \frac{14}{75025-17712+1} = 2.443 \times 10^{-4} $$

Therefore, the first range is better than the second range.