Hello Codeforces,
I'm interested in integer factorization problem. Is there anyone who works on that problem, or can redirect me to someone who I can ask? I'm interested in following things:
- What are the must-read papers\books on that topic?
- Any particular scientists\groups whose works I should follow?
- What is the most common\popular current approach in attempts to solve this problem?
I want to start gaining overall knowledge about this problem\maybe try to work on it if I can, but don't know how to start (and I got no help from my garbo university), so any advice is appreciated. I have completed 2 semester mandatory university linear algebra course + 1 semester optional basic number theory course + some basic knowledge gained from competitive programming\maths + I have tried to read about known existing algorithms, but got overwhelmed and stuck eventually.
I am most grateful to anyone who will take some time to provide info on that topic.
See these blogs ,they might be helpful to you http://e-maxx.ru/algo/prime_sieve_linear http://codeforces.com/blog/entry/8989 http://e-maxx.ru/algo/euler_function
Have you read about quadratic sieve on Wikipedia? Your completed courses should be enough to understand it. Which part of the algorithm is difficult for you?
There are more advanced factorization algorithms but they are much harder to follow. They are based on elliptic curves and number fields which are not easy subjects. So you might need to read a book on these topics first. This will be well above any university assignment. You don't need this unless you want to do scientific research in number theory.
I have done some digging and it looks like this book is highly recommended on this topic: Prime Numbers: A Computational Perspective. By Richard Crandall and Carl Pomerance.