search

RisenCrypto / RisenCrypto.github.io

Write ups on Mathematical Cryptography
https://risencrypto.github.io/
MIT License
2 stars 4 forks source link

QuadraticSieve/ #5

Open utterances-bot opened 1 year ago

utterances-bot commented 1 year ago

The Quadratic Sieve algorithm for Integer Factorization – Risen Crypto – Cryptography

https://risencrypto.github.io/QuadraticSieve/

maelhos commented 1 year ago

Thank you very much for this awesome explanation. It really helped me make my own implementation, also, I would be really interested in understanding the optimisations such as log approximation and MPQS. Thank you very much for this article

RisenCrypto commented 1 year ago

Thank you very much for this awesome explanation. It really helped me make my own implementation, also, I would be really interested in understanding the optimisations such as log approximation and MPQS. Thank you very much for this article

Thank you for the kind words. About the optimizations, I don't think I understand it well enough as of now to write a post or answer questions about it :-(

x13420x commented 1 year ago

just ask https://chat.openai.com/chat it will explain any optimizations you want to understand. If you dont understand something it can give examples to help you understand.

x13420x commented 1 year ago

This video series explains a lot of the major optimizations with code https://www.youtube.com/playlist?list=PL0OUqr2O9PxLd35SgBiWIxuLgm7mYksfp

Daa52000 commented 1 year ago

Your matrix in SageMath isn’t the same as the matrix in your explanation?

RisenCrypto commented 1 year ago

Your matrix in SageMath isn’t the same as the matrix in your explanation?

It's the transpose of the same matrix.

Daa52000 commented 1 year ago

Your matrix in SageMath isn’t the same as the matrix in your explanation?

It's the transpose of the same matrix.

It’s not, in the example matrix the 7th row doesn’t match the SageMath 7th column and the the same for the 9th row/column.

By the way great explanation and examples though, you have definitely helped me understand the topic.

RisenCrypto commented 1 year ago

By the way great explanation and examples though, you have definitely helped me understand the topic.

Thank you for the kind words.

Also, I think I have fixed the Matrix mismatch now. Thank you for pointing out.

consentsam commented 6 months ago

Please fix the following lines

N^2+b^2=a^2
So N^2=a^2−b^2
N=(a+b)(a−b)

as follows:

N+b^2=a^2
So N=a^2−b^2
N=(a+b)(a−b)

in the starting of the lines

RisenCrypto commented 5 months ago

Please fix the following lines

in the starting of the lines

Done. Thank you for pointing it out.