GSOC Project: Expand the number theory class

[Cho Yin Yong]

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!

[Aaron Meurer]

I'm not too familiar with number theory algorithms. How would these
methods compare to the ones that are already implemented?

Aaron Meurer

> --
> 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 sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> 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.

[Cho Yin Yong]

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 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.

[Kalevi Suominen]

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

[Cho Yin Yong]

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.

[Aaron Meurer]

This sounds good. At this point, I would recommend starting work on
your patch requirement.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/9dc61acf-c8e2-42cf-98e6-fbd6b43e67f9%40googlegroups.com.

[Cho Yin Yong]

That's great, thanks!