Wang, Xingbo (2023) Densification of Witnesses for Randomized Algorithm Design. Journal of Advances in Mathematics and Computer Science, 38 (10). pp. 44-69. ISSN 2456-9968
Wang38102023JAMCS106765.pdf - Published Version
Download (879kB)
Abstract
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.
Item Type: | Article |
---|---|
Subjects: | Science Global Plos > Computer Science |
Depositing User: | Unnamed user with email support@science.globalplos.com |
Date Deposited: | 27 Sep 2023 05:47 |
Last Modified: | 27 Sep 2023 05:47 |
URI: | http://ebooks.manu2sent.com/id/eprint/1558 |