Mohammed Golam Kaosar, Charles Sturt University, Australia

Breaking a big integer into two factors is a famous problem in the field of Mathematics and Cryptography for years. Many crypto-systems use such a big number as their key or part of a key with the assumption - it is too big that the fastest factorisation algorithms running on the fastest computers would take impractically long period of time to factorise. Hence, many efforts have been provided to break those crypto-systems by finding two factors of an integer for decades. In this paper, a new factorisation technique is proposed which is based on the concept of backtracking. Binary bit by bit operations are performed to find two factors of a given integer. This proposed solution can be applied in computing square root, primality test, finding prime factors of integer numbers etc. If the proposed solution is proven to be efficient enough, it may break the security of many crypto-systems. Implementation and performance comparison of the technique is kept for future research.

Information Security, Crypto-system, Factorization, Primality test, Backtracking.