Gsoc 2020 : Implementing better integer factorization algorithms

[ABHINAV ANAND]

Hey sympy community, my name is Abhinav and i am from India. I have posted a rough draft of gsoc proposal earlier and i need to confirm that if this can be a Gsoc proposal.

Currently sympy uses special case factorization algorithms like pollard rho etc. for integer factorization which works well if the number is made of small factors or the number is limited to 10-15 digits long.

I propose to implement two new algorithms:

(1) Lenstra elliptic-curve factorization

(2) Self initializing multiple polynomial quadratic sieve

Currently the fastest known algorithm for factorization is General number field sieve but its efficiency is seen when the numbers are more than 100 digits long and in general impractical as it takes hours to factorize those. Instead the algorithms that i proposed are used to factorize integers in the range of 20 - 60 digits long. 

Quadratic sieve is the second fastest known algorithm and elliptic-curve factorization is the third fastest known algorithm. 

So, i was wondering if this is relevant to Sympy and can this be a proposal for this year Gsoc. Looking forward to hear from the community. 

[Kalevi Suominen]

Hi,

Yes, those algorithms are relevant to SymPy. For the first one, you might be interested in completing this PR:

https://github.com/sympy/sympy/pull/2449. It should be possible to make it work also with finite fields and rings.

Kalevi Suominen

[ABHINAV ANAND]

Hey, i hope the work done on the referenced pr is good. I wanted to confirm that the idea that i gave can be part of Gsoc this year. I mean if it is enough work for the summer and withn the scope of sympy. If yes then i will start making a formal proposal and improve it based on your opinions, before the application period begins. Moreover as this idea is not on the ideas page of sympy, i was wondering if any mentor is interested in this.

Best,

Abhinav Anand

[Kalevi Suominen]

Hi,

I think that it is enough work for a summer of code (maybe even more than enough). It would be a good addition to the prime testing and factorization modules of SymPy.

Kalevi Suominen

[ABHINAV ANAND]

I have started making my proposal for the GSOC. This is the link https://docs.google.com/document/d/1y_kLou7NwodV75puX88Lihdkx63sw5aQEc1zVuh8_NM/edit?usp=sharing

Please review my proposal and suggest any improvements.

[ABHINAV ANAND]

Greetings,

I have uploaded the final proposal. Here is the link

https://docs.google.com/document/d/1y_kLou7NwodV75puX88Lihdkx63sw5aQEc1zVuh8_NM/edit?usp=sharing

But Google allows us to edit them before the deadline. If you have any suggestions and improvements please let me know.

[ABHINAV ANAND]

I have submitted my proposal, but since the deadline is tomorrow and google allows edition the proposal, so i humbly request the mentors to please review my proposal and if there are any improvements that might be needed please let me know.

https://docs.google.com/document/d/1y_kLou7NwodV75puX88Lihdkx63sw5aQEc1zVuh8_NM/edit?usp=sharing