- #1
mtanti
- 172
- 0
How is it that you calculate e and d such that ed=(p-1)(q-1)+1? Isn't this a factoring problem?
How can you be sure that (p-1)(q-1)+1 is not prime?
How can you be sure that (p-1)(q-1)+1 is not prime?
How can you be sure that (p-1)(q-1)+1 is not prime?
- Thread starter mtanti
- Start date
-
- Tags
- Prime
In summary, the conversation is discussing how to calculate the values of e and d in the RSA encryption algorithm, specifically in the equation ed=(p-1)(q-1)+1. There is a concern about whether (p-1)(q-1)+1 could be prime and the importance of finding a value of ed that satisfies ed = 1 (mod phi(N)). The conversation also mentions the use of the programs 'PARI' and Mathematica's 'PowerMod' for working with number theory and implementing RSA encryption.
- #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
- 14,981
- 26
You're interested in ed = k(p-1)(q-1) + 1.
The whole point is that you're looking for ed = 1 (mod phi(N)).
The whole point is that you're looking for ed = 1 (mod phi(N)).
- #3
saltydog
Science Advisor
Homework Helper
- 1,591
- 3
In case you don't already know, the program 'PARI' on the web is nice for working with number theory and some of the algorithms of RSA in general. Anyway, I used it, in conjunction with Mathematica's 'PowerMod' to easily encrypt a paragraph using two 256-digit primes (found by PARI).
Check um' out.
Check um' out.
1. How do you determine if (p-1)(q-1)+1 is prime?
The primality of (p-1)(q-1)+1 can be determined using various methods such as trial division, Fermat's test, and Miller-Rabin test. These tests involve checking if the number is divisible by smaller primes or if it passes certain conditions.
2. Is there a specific formula to prove that (p-1)(q-1)+1 is not prime?
There is no specific formula to prove that (p-1)(q-1)+1 is not prime. However, there are certain patterns and characteristics that can indicate the number is not prime, which can be identified through various primality tests.
3. Can (p-1)(q-1)+1 be prime for certain values of p and q?
Yes, (p-1)(q-1)+1 can be prime for certain values of p and q. For example, when p = 3 and q = 5, (p-1)(q-1)+1 = 11, which is a prime number. However, this is not always the case and the primality of (p-1)(q-1)+1 should be determined through testing.
4. What is the significance of (p-1)(q-1)+1 in prime number theory?
The number (p-1)(q-1)+1 is significant in prime number theory as it is often used in the RSA encryption algorithm. This algorithm relies on the difficulty of factoring large semiprimes, which are numbers of the form (p-1)(q-1)+1, in order to ensure secure communication.
5. Can (p-1)(q-1)+1 be a composite number?
Yes, (p-1)(q-1)+1 can be a composite number. In fact, it is more likely to be composite than prime, especially for large values of p and q. This is why it is important to test for primality rather than assuming the number is prime.
Similar threads
-
Precalculus Mathematics Homework Help
-
Set Theory, Logic, Probability, Statistics
-
Precalculus Mathematics Homework Help
-
Calculus and Beyond Homework Help
-
Precalculus Mathematics Homework Help
-
Precalculus Mathematics Homework Help
-
Calculus and Beyond Homework Help
-
High Energy, Nuclear, Particle Physics
-
Precalculus Mathematics Homework Help
-
Calculus and Beyond Homework Help