Factoring Semiprimes Using PG(2N) Prime Graph Multiagent Search.

详细信息   

• 作者：Wilson ; Keith Eirik.
• 学历：Master
• 年：2011
• 导师：York,Bryant,eadvisorMassey,Bartecommittee memberShrimpton,Thomasecommittee member
• 毕业院校：Portland State University
• Department：Computer Science.
• ISBN：9781124785073
• CBH：1496912
• Country：USA
• 语种：English
• FileSize：2535584
• Pages：97

文摘

In this thesis a heuristic method for factoring semiprimes by multiagent depth-limited search of PG2N graphs is presented. An analysis of PG2N 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 N &le； 26. The contribution of this small scale research was to develop heuristics for seed selection that may extrapolate to larger values of N.