Factoring large N into prime factors

In summary, the speaker is looking for help with a project involving factoring large numbers using an algorithm. They have reached a point where they are stuck and need assistance. They have described a method for finding a value for (p-1)(q-1) from N, but now need to recover the values of p and q. They mention a thread they found helpful and explain their method for finding (p-1)(q-1). They are looking for the name of the theorem they are using and a proof for it.
  • #1
bert2612
5
0
Hi, I am writing up a project based on an algorithm for factoring large numbers, I have reached seemingly simple point where I am stuck, I wonder if anyone can help me?

I am trying to factor a large N such that N=pq for unknown primes p and q, I have described a method to find a value for (p-1)(q-1) from N and now have the problem of recovering p and q.

So N is given and (p-1)(q-1) is given, how do I carry on? Thanks
 
Mathematics news on Phys.org
  • #3
thanks, that's perfect.

The way in which i found (p-1)(q-1) is to take a set of sequences of powers of x mod N for x=1,2,...,N-1 and work out their periods, each period turns out to be a divisor of (p-1)(q-1), if a large enough number of divisors is taken, then the value of (p-1)(q-1) can be predicted with high probability. That's basically all I've got, if anyone knows the specific theorem I am exploiting here it would be greatly appreciated as I should include it in my work, I know it's Euler but I'm having trouble finding a specific name so I can reference it and perhaps find a proof.
 

1. What is factoring large N into prime factors?

Factoring large N into prime factors is the process of finding all the prime numbers that, when multiplied together, equal the original number N. This is important in fields such as cryptography, where large numbers need to be broken down into smaller, more manageable numbers for security purposes.

2. Why is factoring large N into prime factors important?

Factoring large N into prime factors is important for various reasons, including encryption and security, as well as in mathematical and scientific research. It allows us to better understand the properties of numbers and solve complex problems in different fields.

3. How is factoring large N into prime factors done?

There are various algorithms and methods for factoring large N into prime factors, such as the trial division method and the quadratic sieve method. These methods involve breaking down the number into smaller factors and repeating the process until all the factors are prime.

4. What are the applications of factoring large N into prime factors?

Factoring large N into prime factors has numerous applications, including in cryptography for secure communication, in mathematics for solving complex problems, and in scientific research for understanding the properties of numbers and their applications.

5. Is factoring large N into prime factors a difficult task?

Factoring large N into prime factors can be a difficult and time-consuming task, especially for very large numbers. However, with the use of efficient algorithms and computer programs, the process has become more manageable and can be done in a reasonable amount of time.

Similar threads

Replies
7
Views
1K
Replies
1
Views
706
Replies
13
Views
1K
Replies
8
Views
1K
Replies
43
Views
5K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • General Math
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
866
Back
Top