šŸ–Šļø
Crypto
  • Crypto
  • Fundamentals
    • Divisibility, Factors and Euclid's Algorithms
    • Modular Arithmetic
    • Rings, Fields and Euler's Totient Function
  • Further Maths
    • Continued Fractions
  • RSA
    • Overview
    • Public Exponent Attacks
      • e=1
      • Small e
      • Multi-party RSA with Small e
      • Wiener's Attack
    • Choice of Primes
      • N is prime
      • Mersenne Primes
      • P=Q
      • Fermat Factorisation
    • Factorisation Methods
      • Pollard's p-1
  • Diffie-Hellman Key Exchange
    • Overview
    • Solving the DLP
      • Baby Step, Giant Step
Powered by GitBook
On this page

Was this helpful?

  1. RSA
  2. Choice of Primes

P=Q

PreviousMersenne PrimesNextFermat Factorisation

Last updated 3 years ago

Was this helpful?

If p=qp = qp=q then N=pq=p2N = pq = p^2N=pq=p2 and you can use function such as isqrt in Python to retrieve ppp.

Note that in the situation N=p2N=p^2N=p2, Ļ•(N)≠(pāˆ’1)2\phi(N) \neq (p-1)^2Ļ•(N)=(pāˆ’1)2 due to the full definition of Euler's totient function:

Ļ•(n)=nāˆp∣n(1āˆ’1p)\phi(n) = n \prod_{p|n} (1-\frac{1}{p})Ļ•(n)=np∣nāˆā€‹(1āˆ’p1​)

The key here is that p∣np \mid np∣n are distinct prime factors, so we would only use ppp once in the equation:

Ļ•(n)=n(1āˆ’1p)=nāˆ’p\phi(n) = n(1-\frac{1}{p}) = n - pĻ•(n)=n(1āˆ’p1​)=nāˆ’p