Integer Factorization: Help with Pollards P-1 & Quadratic Sieve

In summary, the person is asking for help with factoring the integer 2896753 using Pollard's p-1 method and the quadratic sieve. They are advised to use a large factor base for Pollard's p-1 and to check their implementation for the quadratic sieve. It is suggested to start with trial division and then use ECM for a number of this size.
  • #1
behnazbarzi
1
0
hey guys, I wonder if you could help me... i cannot factor the integer 2896753 by pollards p-1 method and the quadratic sieve .
 
Physics news on Phys.org
  • #2
What factor base are you using for Pollard's p - 1? It will work, though you need a fairly large factor base for such a small input number (primes up to 31) unless you are using the two-step variant.

As for the quadratic sieve, it pretty much always works for sufficiently large numbers (including yours) so obviously the implementation you are using is broken. How are you carrying out the quadratic sieve?

To be fair though for a number of this size I'd start by carrying out trial division up to the first ten thousand primes (which would factor it) and then directly moving on to ECM.
 

FAQ: Integer Factorization: Help with Pollards P-1 & Quadratic Sieve

What is integer factorization?

Integer factorization is the process of breaking down a composite number into its prime factors. This is an important problem in mathematics and computer science, as it is the basis for many encryption algorithms and is used in fields such as cryptography and coding theory.

What is Pollard's P-1 algorithm?

Pollard's P-1 algorithm is a method for finding the prime factors of a composite number. It is based on the concept of Fermat's Little Theorem and uses repeated exponentiation to find a factor of a given number. This algorithm is simple and efficient, but it may not work for all numbers.

How does the Quadratic Sieve algorithm work?

The Quadratic Sieve algorithm is another method for integer factorization. It works by finding smooth numbers, which are numbers that have small prime factors, and then using these numbers to construct a congruence of squares. By solving this congruence, the algorithm can find the prime factors of the original number.

When should I use Pollard's P-1 algorithm?

Pollard's P-1 algorithm is best used for finding factors of numbers that are close to each other in size. This means that the difference between the two factors should not be much larger than the square root of the number itself. Additionally, this algorithm should be used when the number is not too large, as it becomes less efficient for larger numbers.

What are some challenges of integer factorization?

Integer factorization is a difficult problem, and there are a few challenges that make it even more complex. One challenge is finding efficient algorithms that work for all numbers, as different methods may work better for different types of numbers. Additionally, the size of the number can greatly impact the time it takes to factorize it, with larger numbers requiring more computational power and time. Finally, the security of many encryption systems relies on the difficulty of integer factorization, so finding efficient solutions could weaken these systems.

Similar threads

Replies
13
Views
3K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
7
Views
1K
Replies
12
Views
2K
Replies
6
Views
3K
Replies
5
Views
2K
Back
Top