1
edit
Changes
no edit summary
I decided to pursue an old project of mine RSA factorizer. The old version was a simple brute force attack which I initially planned to parallelize because of the nature of this algorithm(Try every possible value starting from
(1-->N). What changed my mind was that this brute force process was already reasonable for small prime numbers and would not see any noticable noticeable gain, vs better algorithms, from this prallelization.
I decided to impliment implement a new algorithm(Fermat factorization) and library(Mpir/GMP) to handle larger numbers >20 digits. The Fermat factorization algorithm worked fine for small numbers and numbers that had prime factors near it's roots. Problems arose when numbers >20 did not have prime factors near their roots and the algorithm failed to factor these(I assume because I eventually run out of memory after many hours of running). I looked at ways that this could be improved while also having the ability to be parallelized.
I found through research that the Quadratic sieve method would be a perfect candidate for this but unfortunately I am still in the process of understading the math behind it. What I did gather from this research is that the method to go about parallelizing it would have been:
1) collect a dictionary of possible factor candidates that can be fatored factored easily by a given factor Base i.e. {2,3,5,7} .
2) Take the exponet exponent values mod 2 of all the collected numbers' factor base and store them in a matrix. At this point CUDA could be used to process these matricies matrices and solve them using Dixton's factorization method.
3) loading the resulty result back to the host and processing the results.
Initial candidate for parallelization (Brute force):