1
edit
Changes
no edit summary
= Project Name Goes here PP Rocks =
== Team Members ==
# [mailto:rlanderson@myseneca.ca?subject=DPS915 Rene Anderson], researchingRSA factorization# [mailto:ftchau1@myseneca.ca?subject=GPU610?subject=gpu610 Francis Chau], researching on Image Processing, namely CImg
# [mailto:yliu332@myseneca.ca?subject=DSP915 Yiqi Liu], Researching on DCRaw — a commonly used open source RAW image processing library
[mailto:rlanderson@myseneca.ca,ftchau1@myseneca.ca,yliu332@myseneca.ca?subject=dps901-gpu610 Email All]
=== Assignment 1 ===
<u>'''Francis' discoveries'''</u>
After doing some research and going through the trouble of building through windows command-line on the latest GNU compiler, I've managed to compile it.
I 've downloaded and chose one of the sample projects that CImg carries, "tutorial.cpp"from http://cimg.eu/. Based on my observations through running it, it measures the amount of Red, Green and Blue values (RGB, primary colours) of a picture; there is one window displaying an image in this case a parrot and the other window to measure RGB values.
Here's the flat diagram:
</pre>
<u>'''Rene's Findings'''</u>
I decided to pursue an old project of mine RSA factorization. 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 noticeable gain, vs better algorithms, from this prallelization.
I decided to 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 factored easily by a given factor Base i.e. {2,3,5,7} .
2) Take the 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 matrices and solve them using Dixton's factorization method.
3) loading the result back to the host and processing the results.
Initial candidate for parallelization (Brute force):
[[File:brute.jpg]]
Fermat factorization:
[[File:fermat.jpg]]
Brute force vs Fermat factorization:
[[File:bruteVSfermat.jpg]]
=== Assignment 2 ===
=== Assignment 3 ===
