•  
  •  
 

Journal of Undergraduate Research

Keywords

SAT, prime factorization, algorithm, modular factorial

College

Physical and Mathematical Sciences

Department

Computer Science

Abstract

Prime factorization is the breaking down of a composite number into prime numbers that, when multiplied together, equal the number. There is not a known algorithm that accomplishes this task in sub-exponential time. For my ORCA project, I worked with Dr. Dan Ventura and sought to develop a polynomial-time prime factorization algorithm. The development of such an algorithm would have revolutionized computer security and oered new insight to even more di‑cult problems. I rst approached the task as a boolean constraint satisfaction problem, but after running out of ideas, I tried coming at it from a more number theoretic standpoint. I studied multiplication and division algorithms immensely (prime factorization is just these in reverse), found a closed form solution to prime factorization that requires a modular factorial, and tried to develop a polynomial-time modular factorial algorithm. In the end I was not successful in creating a fast prime factorization algorithm, but did have a lot of success in other areas.

Download

Share

COinS