RSA加密实现仅返回0问题排查：新增素数校验与互质逻辑

I recently hit a roadblock where my encryption function kept returning 0 no matter the input, but after re-examining the problem, I realized I’d missed a key requirement—one of the example test cases where encoding 99 18 108 45 returns Nothing is actually correct, because 99 and 18 aren’t primes. To resolve this, I added validation functions to ensure the inputs meet the encryption scheme’s prerequisites.

Here’s the updated code:

-- Check if two numbers are coprime (gcd is 1)
coprime :: Int -> Int -> Bool
coprime a b = gcd a b == 1

-- Verify both p and q are prime numbers
check :: Int -> Int -> Bool
check p q = (isPrime p) && (isPrime q)

-- Calculate Euler's totient function for two primes p and q
phi :: Int -> Int -> Int
phi p q = (p - 1) * (q - 1)

-- Core encryption function using modular exponentiation
encrypt :: Int -> Int -> Int -> Int -> Int
encrypt p q m e = powmod m e (p * q)

Key Details: #

• Coprimality Check: The coprime function ensures the public exponent e is valid (it must share no common factors with phi(p*q) for RSA-like encryption).
• Prime Validation: The check function confirms that p and q are primes—this is non-negotiable for the totient function calculation and valid encryption. (Note: isPrime assumes an existing helper function that correctly identifies prime numbers.)
• Modular Exponentiation: The encrypt function uses powmod (an efficient modular exponentiation function) to compute (m^e) mod (p*q) without overflow, which is the core of the encryption step.

For the encode function (not fully provided here), I added logic to first run these checks: if check p q fails (either p or q isn’t prime) or coprime e (phi p q) fails, it returns Nothing as expected. This fixes the earlier issue where invalid inputs were leading to incorrect 0 results.

内容的提问来源于stack exchange，提问作者CB17