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
AI Thread Summary
To calculate e and d in RSA encryption such that ed = (p-1)(q-1) + 1, it is essential to understand that this equation is not a straightforward factoring problem. The focus is on ensuring that ed is congruent to 1 modulo phi(N), where phi(N) is the product of (p-1)(q-1). There is a concern regarding whether (p-1)(q-1) + 1 can be prime, as this impacts the selection of e and d. The discussion highlights the utility of the PARI program for number theory and RSA algorithms, along with Mathematica's PowerMod for practical encryption tasks, such as encrypting text using 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:
 

Thread 'Is AI hype?'

In my discussions elsewhere, I've noticed a lot of disagreement regarding AI. A question that comes up is, "Is AI hype?" Unfortunately, when this question is asked, the one asking, as far as I can tell, may mean one of three things which can lead to lots of confusion. I'll list them out now for clarity. 1. Can AI do everything a human can do and how close are we to that? 2. Are corporations and governments using the promise of AI to gain more power for themselves? 3. Are AI and transhumans...
View full post »

Thread 'MS 365 Profile Badge colour'

Sorry if 'Profile Badge' is not the correct term. I have an MS 365 subscription and I've noticed on my Word documents the small circle with my initials in it is sometimes different in colour document to document (it's the circle at the top right of the doc, that, when you hover over it it tells you you're signed in; if you click on it you get a bit more info). Last night I had four docs with a red circle, one with blue. When I closed the blue and opened it again it was red. Today I have 3...
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top