Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Backtracking based integer factorisation, primality testing and square root calculation

Kaosar, M.G. (2014) Backtracking based integer factorisation, primality testing and square root calculation. In: CCSIT 2014 : The Fourth International Conference on Computer Science and Information Technology, 21 - 22 February 2014, Sydney, Australia

Link to Published Version:
*Subscription may be required


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.

Item Type: Conference Paper
Item Control Page Item Control Page


Downloads per month over past year