Sponsor
Portland State University. Department of Computer Science
First Advisor
Bryant York
Term of Graduation
2021
Date of Publication
1-1-2011
Document Type
Thesis
Degree Name
Master of Science (M.S.) in Computer Science
Department
Computer Science
Language
English
Subjects
Computational search, Factoring, Prime number graph, Prime Numbers, Trees (Graph theory), Factorization (Mathematics)
DOI
10.15760/etd.219
Physical Description
1 online resource (x, 85 p.) : ill. (some col.)
Abstract
In this thesis a heuristic method for factoring semiprimes by multiagent depth-limited search of PG2N graphs is presented. An analysis of PG2Nn graph connectivity is used to generate heuristics for multiagent search. Further analysis is presented including the requirements on choosing prime numbers to generate 'hard' semiprimes; the lack of connectivity in PG1N graphs; the counts of spanning trees in PG2N graphs; the upper bound of a PG2N graph diameter and a conjecture on the frequency distribution of prime numbers on Hamming distance. We further demonstrated the feasibility of the HD2 breadth first search of PG2N graphs for factoring small semiprimes. We presented the performance of different multiagent search heuristics in PG2N graphs showing that the heuristic of most connected seedpick outperforms least connected or random connected seedpick heuristics on small PG2N graphs of size NN.
Rights
In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
Persistent Identifier
http://archives.pdx.edu/ds/psu/7009
Recommended Citation
Wilson, Keith Eirik, "Factoring Semiprimes Using PG2N Prime Graph Multiagent Search" (2011). Dissertations and Theses. Paper 219.
https://doi.org/10.15760/etd.219
Comments
Portland State University. Dept. of Computer Science