I would prioritise myself with the Quadratic Sieve, as it is more practical (fastest general method for digits under 100 decimal places). This is indeed an ambitious project, however, I've gained a head start with the mathematical side of these algorithms, having researched on RSA, and Fermat's factorization algorithm, the basis for quadratic sieve, I am confident that at least one complex factorisation algorithm can be implemented into Sympy.
The quadratic sieve is also separated into many different steps, instead of one big problem. These different steps also reduce the complexity of the code. Due to my high interest in these algorithms, I would be more than willing to continue working on implementing the remaining sieve methods after the three month period. On Thursday, March 2, 2017 at 1:23:07 PM UTC-5, Kalevi Suominen wrote: > > > > On Thursday, March 2, 2017 at 12:23:30 AM UTC+2, Cho Yin Yong wrote: >> >> The algorithms currently implemented have the following best case >> scenarios for factorizing: >> >> - Fermat's Test (When two prime numbers are close to each other) >> - Pollard's Rho (When one prime factor is much smaller than the other) >> - Pollard's p-1 (p&q are prime factors -> p-1 divisble by r!, q-1 not >> divisible by r!, for all r) >> >> These are common methods used to test if a randomly generated RSA public >> key with two prime numbers is secure enough in today's standards. >> >> Compared to the implemented algorithms, the algorithms I propose to be >> added to sympy are the general methods that are considered the fastest >> known to factor a RSA public key. >> > > I think this would be a good addition to SymPy, but the plan is fairly > ambitious. Have you considered how much you would be able to implement in > three months? > > Kalevi Suominen > >> >> I believe it is a great addition to Sympy as it would definitely serve as >> a complement to the current crypto module, specifically the RSA method. >> >> >> On Tuesday, February 28, 2017 at 6:11:25 PM UTC-5, Aaron Meurer wrote: >>> >>> I'm not too familiar with number theory algorithms. How would these >>> methods compare to the ones that are already implemented? >>> >>> Aaron Meurer >>> >>> On Tue, Feb 28, 2017 at 4:29 PM, Cho Yin Yong <[email protected]> wrote: >>> > I am extremely intrigued to work with SymPy for the upcoming Google >>> Summer >>> > of Code. I have particular interest in number theory and its methods >>> for >>> > semiprime factorization. Right now, sympy has pho rollard, pho's p-1 >>> and >>> > fermat's test for semiprime factorization. >>> > >>> > http://docs.sympy.org/dev/_modules/sympy/ntheory/factor_.html >>> > >>> > I would like to expand sympy's number theory class with more integer >>> > factorization methods: >>> > - General Number Field Sieve >>> > - Special Number Field Sieve >>> > - Quadratic Sieve >>> > etc. >>> > >>> > I would love to know if this is a possible idea to work on this summer >>> for >>> > sympy! >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups >>> > "sympy" group. >>> > To unsubscribe from this group and stop receiving emails from it, send >>> an >>> > email to [email protected]. >>> > To post to this group, send email to [email protected]. >>> > Visit this group at https://groups.google.com/group/sympy. >>> > To view this discussion on the web visit >>> > >>> https://groups.google.com/d/msgid/sympy/1d227040-7594-4f7a-881e-8830d2e2ae2a%40googlegroups.com. >>> >>> >>> > For more options, visit https://groups.google.com/d/optout. >>> >> -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/9dc61acf-c8e2-42cf-98e6-fbd6b43e67f9%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
