Tuesday, March 15, 2016

Using the ABC-Conjecture in Cryptography

The ABC-Conjecture is a very famous conjecture in Number Theory which is perhaps not a conjecture anymore if it the proof of Shinichi Mochizuki will turn out to be correct. I can not say anything useful about proving this conjecture, but i thought about its application for a while. Let me state the stronger version of the conjecture due to Baker [1];

ABC-Conjecture (strong, explicit version)
Given co-prime integers $a,b,c$ with $a + b = c$ then $$ c < (\text{rad}(abc))^{1.75}$$

The operator $\text{rad}$ (=radical) means the product of the distinct prime numbers dividing $n$. The version was derived from the (following) explicit ABC-Conjecture, also due to Baker:


ABC-Conjecture (explicit version)
Given co-prime integers $a,b,c$ with $a + b = c$ and let $\omega(n)$ be the number of distinct prime factors of $n$ then $$c < \frac{6}{5}\text{rad}(abc)\frac{(\log(\text{rad}(abc)))^{\omega(abc)}}{\omega(abc)!}$$

Assume you have co-prime integers $a,b,c$, wlog $a < b < c$, with $\text{rad}(a) < a^{1/6}$,  $\text{rad}(b) < b^{1/6}$ and $\text{rad}(c) < c^{1/6}$, then it is
\begin{align*}
 c &\leq \text{rad}(abc)^{1.75} = (\text{rad}(a)\text{rad}(b)\text{rad}(c))^{1.75}\\
 &< (a^{1/6}b^{1/6}c^{1/6})^{1.75} < (c^{1/2})^{1.75} = c^{15/16}\\
& < c
\end{align*} which is a contradiction and hence such integers can not exists. That's also the reason, why the even more famous Fermat Last Theorem follows from the ABC-Conjecture, which shows how deep the ABC-Conjecture is.

Observe the following simple Heuristic: