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

Click For Summary
The integer 2896753 can be factored using Pollard's p-1 method, but a large factor base, specifically primes up to 31, is necessary for effective results. The quadratic sieve is generally reliable for numbers of this size, indicating potential issues with the current implementation being used. It is recommended to perform trial division up to the first ten thousand primes before attempting more complex methods like ECM. The discussion emphasizes the importance of the right approach and tools for successful integer factorization. Proper implementation and method selection are crucial for effective factorization of integers.
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.
 

Thread 'A variant of the Monty Hall problem'

There is a nice little variation of the problem. The host says, after you have chosen the door, that you can change your guess, but to sweeten the deal, he says you can choose the two other doors, if you wish. This proposition is a no brainer, however before you are quick enough to accept it, the host opens one of the two doors and it is empty. In this version you really want to change your pick, but at the same time ask yourself is the host impartial and does that change anything. The host...
View full post »

Similar threads

An integer n>1 is square-free if and only if?
  • · Replies 13 ·
Replies
13
Views
4K
Exercise on (ir)rational numbers
  • · Replies 1 ·
Replies
1
Views
1K
B Calculating the coprime probability of two integers in a different way
  • · Replies 13 ·
Replies
13
Views
2K
A The Last Occurrence of any Greatest Prime Factor
  • · Replies 7 ·
Replies
7
Views
1K
Finding Integer Solutions to Polynomial Equations: Can it be Done Easily?
  • · Replies 9 ·
Replies
9
Views
2K
Quadratic equation with no rational roots
  • · Replies 12 ·
Replies
12
Views
3K
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
MHB How many edges does the graph have?
  • · Replies 4 ·
Replies
4
Views
2K
I Two integers and thus their squares have no common factors
  • · Replies 43 ·
2
Replies
43
Views
6K