Result: Densification of Witnesses for Randomized Algorithm Design

This paper investigates the densification of witnesses for randomized algorithm design and its application in factoring integers. By defining a set operation named with Cartesian subtraction on two countable sets and proving several properties of the operation, it is shown that the Cartesian subtraction can densify certain elements in a countable set so as to promote the abundance of witnesses for the randomized algorithm design. It is also proven that the Cartesian subtraction of two sets containing consecutive integers can form a triangular lattice zone that has a higher density of witnesses. Through designing an algorithm of a two-dimensional simple random walk on the triangular lattice zone, it is demonstrated that composite integers can be factored by means of the random walk. The study of the paper explores a pathway feasible and workable to densify the small witnesses in a countable set for randomized algorithm designs.