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

  • Context: MHB 
  • Thread starter Thread starter behnazbarzi
  • Start date Start date
  • Tags Tags
    Factorization Integer
Click For Summary
SUMMARY

The discussion focuses on integer factorization techniques, specifically Pollard's P-1 method and the quadratic sieve, for the integer 2896753. It is established that a large factor base, including primes up to 31, is necessary for Pollard's P-1 method to be effective. The quadratic sieve is noted to be reliable for sufficiently large numbers, indicating that the user's implementation may be flawed. The recommended approach for factoring this number includes performing trial division up to the first ten thousand primes before utilizing Elliptic Curve Method (ECM).

PREREQUISITES
  • Understanding of Pollard's P-1 method
  • Familiarity with the quadratic sieve algorithm
  • Knowledge of trial division techniques
  • Experience with Elliptic Curve Method (ECM)
NEXT STEPS
  • Research the implementation of Pollard's P-1 method with a focus on factor base selection
  • Study the quadratic sieve algorithm and common pitfalls in its implementation
  • Learn about trial division and its efficiency for integer factorization
  • Explore the Elliptic Curve Method (ECM) for advanced factorization techniques
USEFUL FOR

Mathematicians, cryptographers, and software developers interested in integer factorization techniques and optimization strategies for algorithms like Pollard's P-1 and the quadratic sieve.

behnazbarzi
Messages
1
Reaction score
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
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.
 

Similar threads

High School Calculating the coprime probability of two integers in a different way
  • · Replies 13 ·
Replies
13
Views
2K
An integer n>1 is square-free if and only if?
  • · Replies 13 ·
Replies
13
Views
4K
Graduate Exercise on (ir)rational numbers
  • · Replies 1 ·
Replies
1
Views
1K
Graduate The Last Occurrence of any Greatest Prime Factor
  • · Replies 7 ·
Replies
7
Views
2K
Finding Integer Solutions to Polynomial Equations: Can it be Done Easily?
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad How Does the Equation D x E mod Φ(N) = 1 Relate to RSA Encryption?
  • · Replies 1 ·
Replies
1
Views
1K
Quadratic equation with no rational roots
  • · Replies 12 ·
Replies
12
Views
3K
MHB What is the probability of a password containing exactly 1 or 2 integers?
  • · Replies 6 ·
Replies
6
Views
10K
MHB (2+sqrt(3))^50 close to being an integer
  • · Replies 6 ·
Replies
6
Views
4K
MHB Total no. of positive integer ordered pairs (n,r)
  • · Replies 5 ·
Replies
5
Views
2K