How can you be sure that (p-1)(q-1)+1 is not prime?

  • Thread starter Thread starter mtanti
  • Start date Start date
  • Tags Tags
    Prime
Click For Summary
SUMMARY

The discussion focuses on the mathematical expression (p-1)(q-1)+1 and its implications in RSA encryption. Users clarify that the goal is to ensure ed = k(p-1)(q-1) + 1 does not yield a prime number, emphasizing the importance of modular arithmetic in this context. The tools mentioned include 'PARI' for number theory computations and 'Mathematica's PowerMod' for encryption tasks involving large primes. These tools facilitate the manipulation of RSA algorithms and enhance understanding of their underlying principles.

PREREQUISITES
  • Understanding of RSA encryption and its components, specifically e, d, p, and q.
  • Familiarity with modular arithmetic and its applications in cryptography.
  • Basic knowledge of number theory, particularly prime factorization.
  • Experience with the 'PARI' software for number theory calculations.
NEXT STEPS
  • Explore the functionalities of 'PARI' for advanced number theory applications.
  • Learn about modular arithmetic in depth, focusing on its role in cryptography.
  • Investigate the use of 'Mathematica's PowerMod' for efficient encryption processes.
  • Study the implications of prime numbers in RSA and how to verify their properties.
USEFUL FOR

This discussion is beneficial for cryptographers, mathematicians, and software developers involved in encryption technologies, particularly those working with RSA and large prime numbers.

mtanti
Messages
172
Reaction score
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?
 
Computer science news on Phys.org
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)).
 
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.:smile:
 

Similar threads

Find all pairs of primes ## p ## and ## q ## satisfying ## p-q=3 ##.
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
6K
Undergrad Infinitely many primes of the form p² + nq² -- really?
  • · Replies 8 ·
Replies
8
Views
3K
Prove that there are infinitely many primes of the form ## 8k-1 ##
  • · Replies 4 ·
Replies
4
Views
3K
If ## p\geq q\geq 5 ## and ## p ## and ## q ## are both primes ....
  • · Replies 30 ·
2
Replies
30
Views
3K
Undergrad Logical representation of prime numbers
  • · Replies 19 ·
Replies
19
Views
5K
For ## n>1 ##, show that every prime divisor of ## n+1 ## is an odd integer
  • · Replies 9 ·
Replies
9
Views
3K
Prove that there are infinitely many primes of the form ## 6k+1 ##?
  • · Replies 12 ·
Replies
12
Views
4K
If ## p\neq5 ## is an odd prime, prove that either ## p^{2}-1 ## or....
  • · Replies 15 ·
Replies
15
Views
4K
Prove that if ## n>2 ##, then there exists a prime ## p ## satisfying....
  • · Replies 8 ·
Replies
8
Views
4K